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.

• You want the number of partitions of $n$ with at most $k$ parts; this gets quite messy, to put it mildly. Commented Oct 20, 2012 at 20:10
• I see. That explains why it was omitted from my intro discrete math class. This question came up when I was considering questions of the form "how many ways can I put $k$ (un)labeled objects into $n$ (un)labeled groups". Commented Oct 20, 2012 at 20:23
• Yes, it’s usually postponed at least until you get to a serious combinatorics class and learn about generating functions. There’s a huge literature on partitions, and some of the results aren’t bad, but by and large it’s not simple stuff. Commented Oct 20, 2012 at 20:26

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(n,k)$$ is the number of partitions of $$n$$ into $$k$$ non-zero parts, then $$p(n,k)$$ satisfies the recurrence relation \begin{align} p(n,k) &= 0 & \text{if } k>n \\ p(n,k) &= 1 & \text{if } k=n \\ p(n,k) &= p(n-1,k-1)+p(n-k,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(n,k)$$.

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);


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.

• Great answer! But what if the partition has an upper bound? Commented May 21, 2014 at 17:03
• I believe there is a mistake in the recurrence relation. It gives the wrong answer, and does not match the table. Doing $p(k,n) = p(k-1,n-1)$ and adding that $p(1,n) = 1$ seems to provide the correct result. Commented Apr 9, 2017 at 23:20
• This answer seems wrong indeed! for $k=2, n=5$, the table shows 2, but we have 3 ways - $[(0 + 5), (1 + 4), (2 + 3)]$ Commented Jul 25, 2018 at 20:15

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.

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) !}$$

• The numerator is factorizable $F_k(n)=\frac{(n+1)(n+2)\cdots(n+k-1)}{(k-1)!}$.
– zwim
Commented Dec 12, 2017 at 14:51
• Shouldn't the third row be $F_3(n) = \sum_{l=0}^n F_2(l) = \sum_{l=0}^n n-l+1 = \frac{n(n+1)}{2} + (n+1)$ and so on for the following rows? I think you are using $n$ instead of $l$ by mistake when you call $F_{k-1}(l)$ Commented Oct 24, 2019 at 21:30
• @Johan is there an entry for this in the encyclopedia of integer sequences?
– NM_
Commented Oct 28, 2021 at 20:45
• I think you are over counting here. Consider $F_2(4)$, your solution suggest this should equal $5$, which is not the case. The partitions of $4$ into two sets is given by $0+4, 1+3, 2+2$. If you look at your example "number of ways to write 4 as a sum of 3 digits" you sum 5 brackets below, but I suspect that the last bracket and first bracket count the same partitions as well as the second and second to last brackets. However I think the fix is easy, you simply sum $l$ from $0$ to $\lceil \frac{n}{2} \rceil$ in your expression for $F_k(n)$.
– THIG
Commented Jan 18, 2022 at 21:48
• Also +1 this was still very helpful and has given me some much needed insight! Many Thanks!
– THIG
Commented Jan 18, 2022 at 21:50

A much simpler and mathematical approach:

This problem is equivalent to finding the co-efficient of $x^N$ in the expression $f(x) = (1+x+x^2+x^3+\dots +x^N)^M$

Then $f(x) = ((x^{(N-1)} - 1)/(x-1))^M$. Differentiate it $M$ times (so use $\frac{d^Nf(x)}{dx^N}$) and the co-efficient will be $(\frac{1}{n!})\left(\frac{d^Nf(x)}{dx^N}\right)$ at $x = 0$; differentiation can be done using any numerical differentiation technique. So the complexity of the algorithm is $O(N\times \text{the complexity of differentiation})$.

• Um... How it is equivalent? That coefficient would be the number of different non-commutative sums. But the question is about the number of different commutative sums. Commented Dec 1, 2019 at 20:08
• AnT is correct, this answer is completely wrong for this question. It is a shame this is so highly upvoted. Commented Apr 11, 2023 at 18:13

I have a much simpler approach using DP which does not take an exponential time to calculate the number of partition. I verified this with certain small values though for n=1024 and k=16 I got different answer. Following is the java implementation of the problem. It has three independent part:

1. Divide S in K parts. The parts can have value 0 and order matters. i.e. 10 = 0+5+5+0 and 10=5+5+0+0 are different
2. Divide S in K parts. The parts can not have value 0 and order matters. i.e. 10 can not have value 0+5+5+0 but 10 can be 1+4+4+1 and 4+4+1+1
3. Divide S in K parts. The parts can have value 0 but order does not matters. i.e. 10 = 0+5+5+0 and 10=5+5+0+0 are same.

public class Main {
public static void main(String[] args) throws Exception {
int S = 10, K = 4;
System.out.println("S=" + S + "   K=" + K);
System.out.println(PartionwithZero(S, K));
System.out.println(PartionwithoutZero(S, K));
System.out.println(PartionwithZeroUnique(S, K));
}

/* Divide S in K parts 0 may be present */
public static long PartionwithZero(int S, int K) {
long DP_Table[][] = new long[K][];
for (int i = 0; i < K; i++)
DP_Table[i] = new long[S + 1];
for (int i = 0; i < S + 1; i++)
DP_Table[0][i] = 1;
for (int i = 0; i < K; i++)
DP_Table[i][0] = 1;

for (int i = 1; i < K; i++) {
for (int j = 1; j < S + 1; j++)
DP_Table[i][j] = DP_Table[i - 1][j] + DP_Table[i][j - 1];
}

/*
* for(long i=0;i<K;i++) { for(long j=0;j<S+1;j++)
* System.out.prlong(DP_Table[i][j]+" "); System.out.println(); }
*/
return DP_Table[K - 1][S];
}

/* Divide S in K parts 0 should not be present */
public static long PartionwithoutZero(int S, int K) {
long DP_Table[][] = new long[K][S];
for (int i = 0; i < S; i++)
DP_Table[0][i] = 1;
for (int i = 1; i < K; i++)
DP_Table[i][0] = 0;

for (int i = 1; i < K; i++) {
for (int j = 1; j < S; j++)
DP_Table[i][j] = DP_Table[i - 1][j - 1] + DP_Table[i][j - 1];
}

/*
* for(long i=0;i<K;i++) { for(long j=0;j<S;j++)
* System.out.print(DP_Table[i][j]+" "); System.out.println(); }
*/
return DP_Table[K - 1][S - 1];
}

/* Divide S in K parts 0 may be present */
public static long PartionwithZeroUnique(int S, int K) {
long DP_Table[][][] = new long[K][S + 1][S + 1]; // DP_Table[no of
// partition][Sum][Maximum
// value in the
// partition]

for (int i = 0; i < K; i++)
DP_Table[i][0][0] = 1;
for (int i = 1; i < S + 1; i++) {
DP_Table[0][i][0] = 0;
DP_Table[0][i][i] = 1;
}
for (int i = 1; i < S + 1; i++)
DP_Table[0][0][i] = 0;

for (int i = 0; i < S + 1; i++)
for (int j = 0; j < i; j++)
DP_Table[0][i][j] = 1;

for (int i = 1; i < K; i++) {
for (int j = 1; j < S + 1; j++)
for (int k = 1; k < S + 1; k++) {
// System.out.println(i+" "+j+" "+k);
DP_Table[i][j][k] = (k - j) >= 0 ? DP_Table[i - 1][j][k - j]
: 0;
}
for (int k = 0; k < S + 1; k++) {
long sum = 0;
for (int j = 0; j < S + 1; j++) {
DP_Table[i][j][k] += sum;
sum = DP_Table[i][j][k];
}
}
}

/*
* for(int i=0;i<K;i++) { System.out.println("K ="+i); for(int
* j=0;j<S+1;j++) { for(int k=0;k<S+1;k++)
* System.out.print(DP_Table[i][j][k]+" "); System.out.println(); }
* System.out.println(); System.out.println(); }
*/
return DP_Table[K - 1][S][S];
}


}

Following are the output of some cases:

S=6 K=3 28 10 7

S=10 K=3 66 36 14

S=20 K=12 84672315 75582 582

I have been recently solving a similar problem: how many ways can 1024 items fall into 16 histogram bins? This is essentially the same question, and the problem it coincides with is the number of unordered partitions (we don't care in which order the numbers are filled, writing e.g. 1024 = 512 + 256 + 256 + 0's is the same as 1024 = 0's + 256 + 512 + 256, or any other).

Since my problem is quite big, I've written C++ code to either just count the partitions, or also enumerate them. Get it at http://www.stud.fit.vutbr.cz/~xpolok00/proj/UnPart.h. One can use:

CUnorderedPartition(n, k).n_Partition_Num()


to get just the number of partitions. For n = 1024 and k = 16, it will return 6561153029810 in about two days of time on an average computer.

To also evaluate partitions, one can for example use:

CUnorderedPartition part(10, 3); // write 10 as a sum of 3 numbers
do {
cout << part.r_Bin_Values()[0] << ", " <<
part.r_Bin_Values()[1] << ", " <<
part.r_Bin_Values()[2] << endl;
} while(part.b_Next()); // is there a next combination?
cout << "that was " << part.n_Partition_Num() << " partitions" << endl;


And that will write:

0, 0, 10
0, 1, 9
0, 2, 8
0, 3, 7
0, 4, 6
0, 5, 5
1, 1, 8
1, 2, 7
1, 3, 6
1, 4, 5
2, 2, 6
2, 3, 5
2, 4, 4
3, 3, 4
that was 14 partitions


You can see in the table that the result is correct. The values will always come out sorted in ascending order (since it generates unordered partitions). Enumerating the partitions is a bit slower, for 1024, 16 it takes about three days.

In python you can list the solutions recursively very simply:

k = 6
def a(n, m, l):
if len(l) < k-1:
for i in range(0, n+1):
a(n-i, m-1, l+[i])
else:
print(l+[n])

a(10, k, [])


The above example prints all the solutions for n = 10 and k = 6.

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)