Number of ways to choose N integers that sum up to X

[mnb96]

Hello,
is there a straightforward way, or some well-known expression to count how many ways there are of choosing N positive integers a_1,\ldots,a_N such that a_1+\ldots+a_N = X (where X is some fixed positive integer).

Note that if N=2, and X=10 (for example), I consider the pairs 1+9 and 9+1 (for instance), as being two different ways of obtaining X=10, as well as 2+8 and 8+2, or 3+7 and 7+3, and so on...

For N=1 there is obviously only 1 choice.
For N=2 the result should be: X-1 ways.
For N=3 it is (X-1)(X-2)/2

...For N>3 things get more complicated...

 

[Stephen Tashi]

You could use a "generating functions" to find the number of combinations of integers that sum to a given number. Then you might be able to infer the number of permutations from that answer. A search for "generating functions ways of making change" turns up many expositions, for example this PDF explains it: http://ocw.mit.edu/courses/mathematics/18-310c-principles-of-applied-mathematics-fall-2007/lecture-notes/22_2_ln.pdf

If anyone knows a way to use generating functions to get the answer for the number of permutations directly, I'd like to hear about it.

 

[Edgardo]

The answer is: {X-1 \choose N-1}

This problem is related to the following:
The number of ways to place r indistinguishable balls into n distinguishable boxes such that no box is empty is given by

{r-1 \choose n-1}

See:
http://msor.victoria.ac.nz/twiki/pub/Courses/MATH261_2011T1/WebHome/notes_2.pdf"

To understand the formula we consider 10 balls:
o o o o o o o o o o

Suppose we are interested in how many ways we can represent 10 as a sum of 3 variables:
a1 + a2 + a3 = 10

We can model this by dividing the 10 balls into 3 blocks, for example:
o o o | o o | o o o o o

Obviously, we need 2 dividers to form 3 blocks. All we need to do is count the number of ways we can place
the dividers between the balls. For 10 balls there are 9 spaces between the balls. Thus, there are 9 positions for the 2 dividers yielding

{9 \choose 2} possibilities.


Summary:
r=10 balls, n=3 blocks
=> r-1 positions for n-1 dividers

possibilities: {r-1 \choose n-1} = {9 \choose 2}