Sets of Stars and Bars solutions question

Question

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?

Answer 1

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