1
$\begingroup$

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!

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

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.

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

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.