Formula for Number of possible N element sequences such that their Sum is S?

2k Views Asked by At

How many ways I can choose a $N$ element sequence such their cumulative is $S$? Is there any formula for it? Values of $N$ will be greater Than $0$.
Here are few examples Let $ N=4$ and $S=5$. Their are are $4$ possibilities

$\{(1,1,1,2), \\ (1,1,2,1), \\ (1,2,1,1), \\ (2,1,1,1)\}$

So Possible Sequence is equal to $4$.

Again, let $N=3$ and $S=6$

$\{(1,1,4), \\ (1,2,3),\\ (1,3,2),\\ (1,4,1),\\ (2,1,3),\\ (2,2,2),\\ (2,3,1),\\ (3,1,2),\\ (3,2,1),\\ (4,1,1)\}$

So Possible Sequence is equal to $10$.

2

There are 2 best solutions below

2
On BEST ANSWER

The formula is $\binom{S-1}{N-1}$. This number is a part of what is known as the composition of a number (what is the sum of these numbers over N).

If you want more information you can see the topic more in-depth here.

0
On

The problems seems to be similar to representing a number N as sum of k positive integers which can be solved with star and bar theorems of combinatorics For any pair of positive integers n and k, the number of k-tuples of positive integers whose sum is n is equal to the number of (k − 1)-element subsets of a set with n − 1 elements. https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) binomial (N-1,K-1)