Combinatorics – Number of Ways to Write n as a Sum of k Nonnegative Integers

combinatorics

How many ways can I write a positive integer $n$ as a sum of $k$ nonnegative integers up to commutativity?

For example, I can write $4$ as $0+0+4$, $0+1+3$, $0+2+2$, and $1+1+2$.

I know how to find the number of noncommutative ways to form the sum: Imagine a line of $n+k-1$ positions, where each position can contain either a cat or a divider. If you have $n$ (nameless) cats and $k-1$ dividers, you can split the cats in to $k$ groups by choosing positions for the dividers: $\binom{n+k-1}{k-1}$. The size of each group of cats corresponds to one of the nonnegative integers in the sum.

Best Answer

As Brian M. Scott mentions, these are partitions of $n$. However, allowing $0$ into the mix, makes them different to the usual definition of a partition (which assumes non-zero parts). However, this can be adjusted for by taking partitions of $n+k$ into $k$ non-zero parts (and subtracting $1$ from each part).

If $p(k,n)$ is the number of partitions of $n$ into $k$ non-zero parts, then $p(k,n)$ satisfies the recurrence relation \begin{align} p(k,n) &= 0 & \text{if } k>n \\ p(k,n) &= 1 & \text{if } k=n \\ p(k,n) &= p(k+1,n)+p(k,n-k) & \text{otherwise}. \\ \end{align} (this recurrence is explained on Wikipedia). Note: in the above case, remember to change $n$ to $n+k$. This gives a (moderately efficient) method for computing $p(k,n)$.

The number of partitions of $n$ into $k$ parts in $\{0,1,\ldots,n\}$ can be computed in GAP using:

NrPartitions(n+k,k);

Some small values are listed below:

$$\begin{array}{c|ccccccccccccccc} & k=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 3 & 1 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 4 & 1 & 3 & 4 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ 5 & 1 & 3 & 5 & 6 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\ 6 & 1 & 4 & 7 & 9 & 10 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ 7 & 1 & 4 & 8 & 11 & 13 & 14 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 \\ 8 & 1 & 5 & 10 & 15 & 18 & 20 & 21 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 \\ 9 & 1 & 5 & 12 & 18 & 23 & 26 & 28 & 29 & 30 & 30 & 30 & 30 & 30 & 30 & 30 \\ 10 & 1 & 6 & 14 & 23 & 30 & 35 & 38 & 40 & 41 & 42 & 42 & 42 & 42 & 42 & 42 \\ 11 & 1 & 6 & 16 & 27 & 37 & 44 & 49 & 52 & 54 & 55 & 56 & 56 & 56 & 56 & 56 \\ 12 & 1 & 7 & 19 & 34 & 47 & 58 & 65 & 70 & 73 & 75 & 76 & 77 & 77 & 77 & 77 \\ 13 & 1 & 7 & 21 & 39 & 57 & 71 & 82 & 89 & 94 & 97 & 99 & 100 & 101 & 101 & 101 \\ 14 & 1 & 8 & 24 & 47 & 70 & 90 & 105 & 116 & 123 & 128 & 131 & 133 & 134 & 135 & 135 \\ 15 & 1 & 8 & 27 & 54 & 84 & 110 & 131 & 146 & 157 & 164 & 169 & 172 & 174 & 175 & 176 \\ \hline \end{array}$$

If you want a list of the possible partitions, then use:

RestrictedPartitions(n,[0..n],k);

Comment: In the latest version of GAP,

NrRestrictedPartitions(n,[0..n],k);

does not seem to work properly here, since it does not match

Size(RestrictedPartitions(n,[0..n],k));

when $k>n$. I emailed the support team about this, and they said that NrRestrictedPartitions and RestrictedPartitions are only intended to be valid for sets of positive integers. (I still think the above is a bug, but let's let that slide.) This means that NrPartitions(n+k,k); is the technically correct choice, and, strictly speaking, we shouldn't use RestrictedPartitions(n,[0..n],k);, but judging from the source code, it will work as expected.

Related Question