14
$\begingroup$

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.

$\endgroup$

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Lagerbaer
    Jul 31, 2011 at 16:47
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are you including $\{0,7\}$ as a partition of $7$ with $2$ summands? Because wouldn't $P_2(7) = 3 (\{1,6\}, \{2,5\}, \{3,4\})$? $\endgroup$
    – Roskiller
    Mar 30, 2020 at 11:49
  • $\begingroup$ The question was about non-negative solutions, not positive solutions, so $\{0,7\}$ would be included. $\endgroup$
    – robjohn
    Mar 30, 2020 at 12:35
  • $\begingroup$ Is there a way of manipulating this to give only positive solutions? I'm being rather thick at the moment, sorry. $\endgroup$
    – Roskiller
    Mar 30, 2020 at 13:01
  • $\begingroup$ Subtracting $P_3(M)-P_2(M)$ should give the number of partitions with no zeros. This ends up multiplying $g_n(x)$ by $x^n$, which essentially subtracts $1$ for each partition and computes the number of ways to get the desired number minus $n$. $\endgroup$
    – robjohn
    Mar 30, 2020 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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