Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For a fixed $n$ and $M$, I am interested in the number of unordered non-negative integer solutions to $$\sum_{i = 1}^n a_i = M$$

Or, in other words, I am interested in the number of solutions with distinct numbers. For $n = 2$ and $M = 5$, I would consider solutions $(1,4)$ and $(4,1)$ equivalent, and choose the solution with $a_1 \ge a_2 \ge ... \ge a_n \ge 0$ as the representative of the class of equivalent solutions.

I know how to obtain the number of total, ordered, solutions with the "stars and bars" method. But unfortunately, I cannot just divide the result by $n!$ since that would only work if all the $a_i$ are distinct.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

You want to know the number of partitions of $M$ into at most $n$ parts. A standard bijection (transposing the Young diagram) shows that this is equal to the number of partitions of $M$ into parts of size at most $n$. This number $p_n(M)$ has, for fixed $n$, generating function

$$\sum_{M \ge 0} p_n(M) t^M = \frac{1}{(1 - t)(1 - t^2)...(1 - t^n)}.$$

By computing the partial fraction decomposition of this rational function, you can write down a closed form for $p_n(M)$ (again, for fixed $n$). This is efficient in the regime where $M$ is large compared to $n$. I don't know what regime you care about.

For what it's worth, the dominant term (for fixed $n$ as $M \to \infty$) is easy to extract: it's given by

$$p_n(M) \approx \frac{1}{n!} {M+n-1 \choose n-1}$$

which follows from the fact that the dominant pole at $t = 1$ has multiplicity $n$ and from a computation of the coefficient of the corresponding term in the partial fraction decomposition. In other words, dividing the number you get from stars-and-bars by $n!$ is approximately correct (for fixed $n$ as $M \to \infty$) because in this regime the probability of any two of the numbers being the same becomes negligible. There is also a nice geometric way to see this, as $p_n(M)$ is just the number of non-negative integer solutions $x_2, ... x_n$ to

$$2x_2 + 3x_3 + ... + nx_n \le M$$

and this approximates the volume of the corresponding simplex in $\mathbb{R}^{n-1}$.

See Wilf's generatingfunctionology for general background about generating functions and, for very powerful methods for extracting asymptotics, see Flajolet and Sedgewick's Analytic Combinatorics.

share|improve this answer
    
The dominant term is actually quite easy to see: The combinatorial gives you the number of ordered integer partitions. If all $n$ integers were different, dividing by $n!$ would give you exactly the amount of unordered partitions, but since integers can also be the same, it is just an approximation. As $M \rightarrow \infty$, most solutions will have different integers, so it comes closer to the truth. –  Lagerbaer Jul 31 '11 at 16:47

Let the number of partitions be $P_n(M)$. By looking at the smallest number in the partition, $a_n$, we get a recurrence for $P_n(M)$: $$ P_n(M) = P_{n-1}(M) + P_{n-1}(M-n) + P_{n-1}(M-2n) + P_{n-1}(M-3n) + ... $$ Where $P_n(0)=1$ and $P_n(M)=0$ for $M<0$. The first term in the sum above comes from letting $a_n=0$, the second term from $a_n=1$, the third from $a_n=2$, etc.

Now lets look at $g_n$, the generating function for $P_n$: $$ g_n(x) = \sum_{M=0}^\infty P_n(M)\;x^M $$ Plugging the recurrence above into this sum yields a recurrence for $g_n$: \begin{align} g_n(x)&=\sum_{M=0}^\infty P_n(M)\;x^M\\ &=\sum_{M=0}^\infty (P_{n-1}(M) + P_{n-1}(M-n) + P_{n-1}(M-2n) + P_{n-1}(M-3n) + ...)\;x^M\\ &=\sum_{M=0}^\infty P_{n-1}(M)\;(1+x^n+x^{2n}+x^{3n}+...)\\ &=g_{n-1}(x)/(1-x^n) \end{align} Note that $P_0(0)=1$ and $P_0(M)=0$ for $M>0$. This means that $g_0(x)=1$. Combined with the recurrence for $g_n$, we get that $$ g_n(x)=1/(1-x)/(1-x^2)/(1-x^3)/.../(1-x^n) $$ For example, if $n=1$, we get $$ g_1(x) = 1/(1-x) = 1+x+x^2+x^3+... $$ Thus, $P_1(M) = 1$ for all $M$. If $n=2$, we get \begin{align} g_2(x) &= 1/(1-x)/(1-x^2)\\ &= 1+x+2x^2+2x^3+3x^4+3x^5+4x^6+4x^7+5x^8+5x^9+6x^{10}+... \end{align} Thus, $P_2(7)=4$, $P_2(10)=6$, etc.

share|improve this answer
    
Replied to your email (about something much more serious than what you presumed) –  Bill Dubuque Jun 28 at 0:04

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.