How to find number of integral solutions, containing large number of cases?

Question

Number of positive unequal integral solutions of the equation $x+y+z=12$ can be found out knowing the cases it involves: $(1, 2, 9) , (1,3,8), (1,4,7), (1,5,6), (2,3,7), (2,4,6) and (3,4,5)$. Thus, the number of positive integral solutions of the above equation = $7×3! = 42$.
Now suppose the equation is like this: $a+b+c+d+e=99$. In this equation if we follow the above followed method then it'll take me decades to find out all the cases. What should be my approach now in order to find out the number of solutions?

Answer 1

Let's try to simply the problem:

• the number of compositions of $99$ into $5$ positive distinct parts such as $44+25+1+26+3=99$ is
• $5!$ times the number of partitions of $99$ into $5$ positive distinct parts, since such a distinct partition such as $1+3+25+26+44=99$ can be ordered $5!$ ways, and this is
• $5!$ times the number of partitions of $99-(1+2+3+4+5)=84$ into no more than $5$ positive parts, removing the need for the parts to be positive or distinct by lowering the larger parts such as $(1-1)+(3-2)+(25-3)+(26-4)+(44-5) $ $=0+1+22+22+39 =84$ , and this is
• $5!$ times the number of partitions of $84$ where the largest part is no more than $5$, such as $1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+$ $3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+4$ $=84$, using the symmetry of a Ferrers or Young diagram

This still involves a calculation, though would not take decades even by hand. If we are looking for $T(n,k)$ the number of partitions of $n$ into parts no more than $k$ then

• $T(0,k)=1$ trivially
• $T(n,0)=0$ for $n>0$ since it would be impossible
• $T(n,k)=T(n,k-1)$ for $n<k$ since we cannot use $k$ as a part
• $T(n,k)=T(n,k-1)+T(n-k,k)$ for $0<k\le n$ since we can either use a smaller maximum or we can add a part sized $k$ to a partition of $n-k$

Building up the table of $T(n,k)$ using the recurrence we get

    k:  0   1    2    3    4     5
n:                          
0       1   1    1    1    1     1
1       0   1    1    1    1     1
2       0   1    2    2    2     2
3       0   1    2    3    3     3
4       0   1    3    4    5     5
5       0   1    3    5    6     7
6       0   1    4    7    9    10
7       0   1    4    8   11    13
...
79      0   1   40  560 4109 19366
80      0   1   41  574 4263 20282
81      0   1   41  588 4410 21224
82      0   1   42  602 4571 22204
83      0   1   42  616 4725 23212
84      0   1   43  631 4894 24260

where for example $T(84,5)= T(84,4)+T(79,5)=4894+19366=24260$.

So the answer to the original question is $5! \times 24260= 2911200$.

Doing the same for the small example:

• the number of compositions of $12$ into $3$ positive distinct parts is
• $3!$ times the number of partitions of $12$ into $3$ positive distinct parts, and this is
• $3!$ times the number of partitions of $12-(1+2+3)=6$ into no more than $3$ positive parts, and this is
• $3! \times T(6,3) = 6\times 7=42$ as expected