Number of ways to write n as a sum of k nonnegative integers

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.

Solution 1:

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.

Solution 2:

If you are only interested in a small:ish number of $k$ then this is most easily solved by thinking recursively and using induction. First some notation. Let $F_k(n)$ be the number of ways to sum $k$ natural numbers so the sum is $n$.

The generic reasoning can be inferred from a small example.

Assume we have three numbers we want to sum to 4. The number of ways to do this is the same as setting the first digit to $k=4,3,2,1,0$ in turn and then using the remaining digits to sum up to $k-1$.

number of ways to write 4 with three digits =

{4 + {number of ways to write 0 with two digits}} +

{3 + {number of ways to write 1 with two digits}} +

{2 + {number of ways to write 2 with two digits}} +

{1 + {number of ways to write 3 with two digits}} +

{0 + {number of ways to write 4 with two digits}}

(You might want to convince yourself that this is the case and there is no need to assume the set digit in different positions)

Which is the same as writing (in our notation)

$F_3(4) = F_2(0) + F_2(1) + F_2(2) + F_2(3) + F_2(4)$

For the general case we have

$F_k(n) = \sum_{l=0}^n F_{k-1}(l)$

it is also easily seen that $F_1(n)=1$ and $F_k(0)=1$. This now allows us to expand the first few relations as

$$F_1(n) = 1$$ $$F_2(n) = \sum_{l=0}^n F_1(l) = \frac{(n+1)}{1!}$$ $$F_3(n) = \sum_{l=0}^n F_2(l) = \sum_{l=0}^n n+1 = \frac{(n+1)^2+(n+1)}{2!}$$ $$F_4(n) = \sum_{l=0}^n F_3(l) = \frac{(n+1)^3+3(n+1)^2+2(n+1)}{3!}$$ $$F_5(n) = \sum_{l=0}^n F_4(l) = \frac{(n+1)^4 + 6(n+1)^3+11(n+1)^2+6(n+1)}{4!}$$

... and so on

Unfortunately there isn't any "nice" generic expression for the coefficients in the numerator. Its a good exercise to find it but be warned; it gets quite messy apart from the two highest and the lowest coefficients in the numerator polynomial which you probably can spot by inspection.

Addendum:

By factoring the numerator and recognizing the Gamma function the expression can be written in semi-closed form as:

$$F_k(n) = \frac {\Gamma \left( n+k \right) }{\Gamma \left( n+1 \right) \left( k-1 \right) !}$$