7
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ What about $(1,1,10)$ and $(2,2,8)$ and $(3,3,6)$ and $(4,4,4)$ and $(5,5,2)$? $\endgroup$ Commented Jul 18, 2016 at 15:18
  • 1
    $\begingroup$ @barakmanos Presumably that's ruled out by the 'unequal' requirement. (Though the more typical word is 'distinct.') $\endgroup$ Commented Jul 18, 2016 at 15:23
  • $\begingroup$ @Semiclassical: Right... Well, without this requirement, the number of solutions is $\binom{12-1}{3-1}$ for the given example, and $\binom{99-1}{5-1}$ for the actual question. Probably need to perform some sort of elaborated "inclusion/exclusion" in order to get the exact answer. $\endgroup$ Commented Jul 18, 2016 at 15:26
  • $\begingroup$ That depends on ignoring the order of entries in the solution, i.e. the number of compositions rather than partitions. (In the case of distinct entries, the difference between the two is some overall combinatorial factor and so uninteresting. But in the generic case---the one you consider---the number of partitions is much harder to compute.) @barakmanos $\endgroup$ Commented Jul 18, 2016 at 15:29
  • $\begingroup$ @Semiclassical: According to the example, different ordering = different solution (i.e., OP wants to count compositions, not partitions). $\endgroup$ Commented Jul 18, 2016 at 15:30

1 Answer 1

0
$\begingroup$

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
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .