Integer partition with fixed number of summands but without order

Question

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.

Answer 1

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.

Answer 2

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.