# How to find all the N-tuples with nonnegative integers that add up to a fixed integer M

I am trying to find a method to find all the $N$ tuples $(a_1,a_2,\ldots,a_N)$ where all the $a_i \in \mathbb{Z}, a_i \geq 0$ such that the sum of the elements of the tuples is exactly $M=\sum_{i=1}^N a_i$. An obvious way to do this is to to generate all the $N$ tuples with entries between 0 and $M$ and then select the ones add up to the number $M$.

I wonder if there is a way to obtain said $N$ tuples without going through all the possible $N$ tuples.

Geometrically this problem is like finding all the points that belong to the hyperplane $\sum_{i=1}^N a_i = M$ in the set $(\mathbb{Z}^{\geq})^N$.

Thanks in advance for any help!

• en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) – Richard D. James Aug 29 '17 at 21:02
• Have you looked up the knapsack problem? – Randall Aug 29 '17 at 21:03
• @Quasicoherent he wants to generate the tuples, not count them. – Henno Brandsma Aug 29 '17 at 21:15
• @Randall knapsack has nothing to do with it, there you get the weights in advance and don't know how many you need. – Henno Brandsma Aug 29 '17 at 21:16

The stars and bars page referenced by Quasicoherent is what you want. Add $1$ to all the $a_i$ to make them positive. Now you want $N$-tuples that sum to $N+M$. Make a line of $N+M$ stars and put $N-1$ bars to separate them. Count the stars between the bars to get your tuple. There are $N+M-1$ places to put bars, so $N+M-1 \choose N-1$ different tuples.

• (+1) I would have gone for this approach, but since you grabbed it, I went with a generating function approach. – robjohn Aug 29 '17 at 21:38

Generating Function approach \begin{align} \left[x^m\right]\left(\frac1{1-x}\right)^n &=(-1)^m\binom{-n}{m}\\[6pt] &=\binom{n+m-1}{m} \end{align}

A Different Stars and Bars Approach

Either I misunderstand Ross Millikan's answer or this is a different approach.

Take $n-1$ bars to separate the $n$ numbers and $m$ stars to represent the numbers between the bars. The number of stars between the bars is one of the $n$ numbers. To count how many $n$-tuples there are, just count the number of ways to choose where the $m$ stars should go within the $n+m-1$ objects: $$\binom{n+m-1}{m}$$

• I see that I have answered a different question. This is how many $n$-tuples there are, not a list of them. – robjohn Aug 29 '17 at 21:40

Recursion-like solutions would suggest themselves: generate all $N$-tuples that sum to $M-1$ and add $1$ to every coordinate of all of them. And then go back.