Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
add comment

4 Answers 4

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.

share|improve this answer
    
+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? –  B Rivera Jul 10 '10 at 1:45
    
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. –  Qiaochu Yuan Jul 10 '10 at 1:58
add comment

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.

share|improve this answer
    
+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? –  B Rivera Jul 10 '10 at 1:50
    
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)$ –  falagar Jul 10 '10 at 5:22
add comment

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.

share|improve this answer
add comment

For fixed k

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

Maybe this limitingform will be of some use to you.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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