0
$\begingroup$

If I want to count the number of non-negative integer solutions to the equation $x_1+x_2+x_3=4$, then I know I have (6 nCr 2)=15 possible solution sets. What I want to know is how many distinct solution sets there are. For example, $(0,0,4)$ is a solution, but so is $(0,4,0)$ but now I want to treat these both as the same solution, in other words I don't care about the order. For something small like this, I found there were 4 possibilities by just writing it out: (0,0,4), (0,2,2), (0,1,3) and (1,1,2). How do I generalise this?

$\endgroup$
  • 1
    $\begingroup$ You are looking at partitions of $4$ into at most $3$ parts. $\endgroup$ – Lord Shark the Unknown Apr 13 '18 at 5:30
  • $\begingroup$ If you have numbers $(x_1, x_2, x_3)$ which form a solution, any reordering of them is also a solution. Therefore, each distinct solution is repeated $3! = 6$ times. $\endgroup$ – Matti P. Apr 13 '18 at 5:31
  • 1
    $\begingroup$ Matti, that's not true. For example, the solution (0,0,4) can only be reordered 3 times. $\endgroup$ – Ayumu Kasugano Apr 13 '18 at 5:33
  • $\begingroup$ @MattiP Then we should have $6\cdot 4=24\not=15$ solutions... $\endgroup$ – Robert Z Apr 13 '18 at 5:33
  • $\begingroup$ @AyumuKasugano ah, it's true. Silly me. $\endgroup$ – Matti P. Apr 13 '18 at 6:00
1
$\begingroup$

You are moving from compositions to partitions because partitions do not care about order where compositions do. Partitions are much harder for exactly the reason you are pointing out. It is hard to tell how many permutations of compositions are the same partition because it depends on how many of the elements match. For partitions into $3$ parts it is not so hard. Condition on the maximal part and find the number of partitions of what is left.

For weak partitions ($0$ is allowed) of $n$ into three parts, let $k$ be the largest part. Now you need to partition $n-k$ into two parts, which can be done in $\lfloor \frac {n-k}2 \rfloor+1$ ways. The total number is then $$\sum_{k=\lceil \frac n3 \rceil}^n\left\lfloor \frac {n-k}2 \right\rfloor+1$$

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