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.
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) &amp;= 0 &amp; \text{if } k&gt;n \\
p(k,n) &amp;= 1 &amp; \text{if } k=n \\
p(k,n) &amp;= p(k+1,n)+p(k,n-k) &amp; \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}
&amp; k=1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11 &amp; 12 &amp; 13 &amp; 14 &amp; 15 \\
\hline
1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\
2 &amp; 1 &amp; 2 &amp; 2 &amp; 2 &amp; 2 &amp; 2 &amp; 2 &amp; 2 &amp; 2 &amp; 2 &amp; 2 &amp; 2 &amp; 2 &amp; 2 &amp; 2 \\
3 &amp; 1 &amp; 2 &amp; 3 &amp; 3 &amp; 3 &amp; 3 &amp; 3 &amp; 3 &amp; 3 &amp; 3 &amp; 3 &amp; 3 &amp; 3 &amp; 3 &amp; 3 \\
4 &amp; 1 &amp; 3 &amp; 4 &amp; 5 &amp; 5 &amp; 5 &amp; 5 &amp; 5 &amp; 5 &amp; 5 &amp; 5 &amp; 5 &amp; 5 &amp; 5 &amp; 5 \\
5 &amp; 1 &amp; 3 &amp; 5 &amp; 6 &amp; 7 &amp; 7 &amp; 7 &amp; 7 &amp; 7 &amp; 7 &amp; 7 &amp; 7 &amp; 7 &amp; 7 &amp; 7 \\
6 &amp; 1 &amp; 4 &amp; 7 &amp; 9 &amp; 10 &amp; 11 &amp; 11 &amp; 11 &amp; 11 &amp; 11 &amp; 11 &amp; 11 &amp; 11 &amp; 11 &amp; 11 \\
7 &amp; 1 &amp; 4 &amp; 8 &amp; 11 &amp; 13 &amp; 14 &amp; 15 &amp; 15 &amp; 15 &amp; 15 &amp; 15 &amp; 15 &amp; 15 &amp; 15 &amp; 15 \\
8 &amp; 1 &amp; 5 &amp; 10 &amp; 15 &amp; 18 &amp; 20 &amp; 21 &amp; 22 &amp; 22 &amp; 22 &amp; 22 &amp; 22 &amp; 22 &amp; 22 &amp; 22 \\
9 &amp; 1 &amp; 5 &amp; 12 &amp; 18 &amp; 23 &amp; 26 &amp; 28 &amp; 29 &amp; 30 &amp; 30 &amp; 30 &amp; 30 &amp; 30 &amp; 30 &amp; 30 \\
10 &amp; 1 &amp; 6 &amp; 14 &amp; 23 &amp; 30 &amp; 35 &amp; 38 &amp; 40 &amp; 41 &amp; 42 &amp; 42 &amp; 42 &amp; 42 &amp; 42 &amp; 42 \\
11 &amp; 1 &amp; 6 &amp; 16 &amp; 27 &amp; 37 &amp; 44 &amp; 49 &amp; 52 &amp; 54 &amp; 55 &amp; 56 &amp; 56 &amp; 56 &amp; 56 &amp; 56 \\
12 &amp; 1 &amp; 7 &amp; 19 &amp; 34 &amp; 47 &amp; 58 &amp; 65 &amp; 70 &amp; 73 &amp; 75 &amp; 76 &amp; 77 &amp; 77 &amp; 77 &amp; 77 \\
13 &amp; 1 &amp; 7 &amp; 21 &amp; 39 &amp; 57 &amp; 71 &amp; 82 &amp; 89 &amp; 94 &amp; 97 &amp; 99 &amp; 100 &amp; 101 &amp; 101 &amp; 101 \\
14 &amp; 1 &amp; 8 &amp; 24 &amp; 47 &amp; 70 &amp; 90 &amp; 105 &amp; 116 &amp; 123 &amp; 128 &amp; 131 &amp; 133 &amp; 134 &amp; 135 &amp; 135 \\
15 &amp; 1 &amp; 8 &amp; 27 &amp; 54 &amp; 84 &amp; 110 &amp; 131 &amp; 146 &amp; 157 &amp; 164 &amp; 169 &amp; 172 &amp; 174 &amp; 175 &amp; 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&gt;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.
Note : I Can't Use MathJax
First, think of the number n as the sum of n ones.
Now think of the k non-negative integers
So now consider this row of n+k-1 objects where there are the n ones and k-1 walls.
We Arrange these (k-1) walls in this row .
Now the k-1 walls cordon off k numbers who shall add up to the number n.
Note that the walls can be adjacent as they shall cordon off zero and zero is non-negative.
So to summarize the total number of ways to do this is the number of arrangements of this row. This is obviously (n+k-1) choose (k-1) as the selection as the selection of the (k-1) places where the walls must go completely determines the rest of the row .
Hope this helps!
P.S ( This Is My First answer on math s.e)