3
$\begingroup$

Let me motivate my general question with an explicit example:

Suppose I am looking for all unique combinations of exactly three non-negative integers that sum to five. The solutions are 005, 014, 023, 113, and 122. Which means that there are five unique combinations.

Is there a way to find the $\textit{number}$ of unique combinations of exactly $k$ non-negative integers that sum to $n$? I'd rather not generate all the unique combinations and then count. I am hoping that there is a straightforward combinatoric solution to this.

Please let me know if more clarification is needed.

Thanks!

$\endgroup$
0

4 Answers 4

7
$\begingroup$

For fixed $k$ and large $n$ this is pretty doable. You want to find solutions to

$$x_1 + x_2 + ... + x_k = n$$

where $x_1 \ge x_2 \ge ... \ge x_k$. Letting $y_i = x_i - x_{i+1}$ and $y_k = x_k$, this is equivalent to finding solutions to

$$y_1 + 2y_2 + ... + ky_k = n$$

where $y_i \ge 0$. If $p_k(n)$ denotes the number of ways to do this, it follows by a standard generating function trick that

$$\sum_{k \ge 0} p_k(n) x^n = \frac{1}{(1 - x)(1 - x^2)...(1 - x^k)}.$$

In principle one can find the partial fraction decomposition of the RHS, allowing us to write $p_k(n)$ as a quasi-polynomial.

$\endgroup$
2
  • $\begingroup$ +1 thanks for the answer. perhaps i should have given my actual numerical constraints. i was looking for some type of method that would allow me to solve for cases of $n > 10^{6}$ and $k > 1000$ in a reasonable amount of time. perhaps it is not possible? $\endgroup$
    – B Rivera
    Jul 10, 2010 at 1:45
  • $\begingroup$ It's always a good idea to give your actual numerical constraints. It is actually quite feasible to read off the leading terms of p_k(n) in terms of n from the generating function; the leading term is something like 1/k! {n+k-1 choose k} and this should give a pretty reasonable approximation. $\endgroup$ Jul 10, 2010 at 1:58
7
$\begingroup$

If you need an algorithm to calculate this number, you can use the following. Let $a_{nk}$ be an answer to your question, then it's not hard to prove that $a_{nk} = a_{n,k-1} + a_{n - k, k}$. So you can fill in the table of all $a_{nk}$ using this formulae.

$\endgroup$
2
  • $\begingroup$ +1 thanks for the answer. but if, say, $n = 10^{7}$ and $k = 2000$, i fear that i'd be sitting around for quite a while for the recursion to finish or i might reach the recursion depth of my programming language. do you know of any asymptotic results? maybe along the lines of hardy-ramanujan? $\endgroup$
    – B Rivera
    Jul 10, 2010 at 1:50
  • $\begingroup$ For those $n$n and $k$ I can suggest the following. Start with the approach suggested by Qiaochu Yuan. Take polynomial $f(x) = (1-x)(1-x^2)\cdots(1-x^k)$ and calculate it as $f(x) = f_0 + f_1 x + \cdots + f_{k(k+1)/2} x^{k(k+1)/2}$. Now you need coefficient with $x^n$ in $1/f(x)$. To calculate it apply Fast Fourier Transform to inverse polynomial $f(x)$. This works in $O(n \log n)$ basic operations (multiplications and additions). So the overall complexity is $O(n \log n)$ $\endgroup$
    – falagar
    Jul 10, 2010 at 5:22
5
$\begingroup$

Nothing wrong with Qiaochu Yuan's answer, but here's an orthogonal approach; for fixed $k$, calculate the first 5 or 10 $n$ values and then look up the resulting sequence at the Online Encyclopedia of Integer Sequences.

$\endgroup$
1
$\begingroup$

For fixed k

$p_k(n) \sim {n^{k-1} \over k!(k-1)!}.$

Maybe this limitingform will be of some use to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.