# Stars and Bars combinatorics

This is my second question on MSE, as my first one had format issues. So apologies for that!

I have a problem here.

How many ways can you distribute 4 balls into 3 boxes?

I would calculate $x_1 + x_2 + x_3 = 4$ (right?) But further on, there is a fixed constraint on each of the variables, stating that only a maximum of $2$ is allowed in each box. (non negative allowed). So I write, $$y_1 = x_1 - 2, y_2 = x_2 - 2, y_3 = x_3 - 2$$

This gives

$$x_1 - 2 + x_2 -2 + x_3 -2 = 4-2-2-2$$ $$y_1+y_2+y_3 = -2$$

I am stuck there. It gives a negative value, how will I be able to count for it? Please correct me and help if there are any problems!

Thank you so much! :)

• Welcome to MSE. Please use MathJax. – José Carlos Santos Sep 9 '17 at 9:37
• $x_i -2$ is only positive if we have at least 2 balls per box (which we cannot have for these numbers), which is a different kind of problem. – Henno Brandsma Sep 9 '17 at 9:56
• @HennoBrandsma okay noted. So it is $$y_i=2-x_i$$ ? – user478905 Sep 9 '17 at 9:58
• Indeed, it is. This is positive exactly when we have at most $2$ per box. – Henno Brandsma Sep 9 '17 at 9:59
• @HennoBrandsma sorry again:) , the constraint is $$x_i <= 2$$ but how does it become $$y_i=2-x_i$$? – user478905 Sep 9 '17 at 10:07

So your example is to count the number of solutions $(x_1,x_2, x_3)$ to $$x_1 + x_2 +x_3 = 4 \text{ where } 0 \le x_i \le 2 \text{ for all } i$$

The generating function way to do this is to compute the coefficient of $x^4$ in $(1+x+x^2)^4 = x^6 + 3x^5 + 6x^4 + 7x^3 + 6x^2 + 3x + 1$,
which equals $6$ here.

Another way: count all solutions without maximum restrictions by stars and bars: this gives $\binom{6}{2} = 15$. There are $3$ trivial ones with one $x_i =4$, the others $0$, which we subtract and also a few where some $x_i = 3$. (these options are mutually exclusive, and at most one can be equal to $3$) The last problem is equivalent to the remaining two variables summing to $1 = 4-3$, so there are $2$ solutions for fixed $x_i = 3$, and there are $3$ choices for the $x_i$, so $6$ solutions in all have this property. And $15 - 3 - 6 = 6$ agreeing with the first solution.

• Hey again, would it be the same technique for $$x_1+x_2+x_3 = 6$$ where $$x_i<=3$$? – user478905 Sep 9 '17 at 11:15
• Yes, setting $y_i = 3-x_i$ will work. – Henno Brandsma Sep 9 '17 at 11:17
• @user478905 what about $2|2|2$? – Henno Brandsma Sep 9 '17 at 12:39
• Solving $y_1 + y_2 + y_3 = 3$ by enumeration, we see there are solutions $(3,0,0)$ in $3$ permutations, which gives $3$ solutions, and also $(1,2,0)$ in $6$ permutations, or $(1,1,1)$ (uniquely), so $10 = 3+6+1$ in total .In terms of the original equation $x_1 +x_2 + x_3 = 6$ these correspond to ball distributions $(0,3,3)$ ($3$ times), $(2,1, 3)$ ($6$ times) or $(2,2,2)$ 1 time. – Henno Brandsma Sep 9 '17 at 12:46
• yes thank you i made several mistakes of not being accurate! – user478905 Sep 9 '17 at 14:17

For $i=1,2,3$ define $y_i=2-x_i$.

Then you must find for nonnegative integers $y_i$ the number of sums: $$y_1+y_2+y_3=2$$ under the extra condition that $y_i\leq2$ for $i=1,2,3$.

Fortunately that extra condition is automatically satisfied, so here you can use stars and bars without any annoying constraints.

• Indeed $(-x_1) + (-x_2) + (-x_3) = -4$ so adding $6 = 2+ 2+ 2$ to both sides gives $y_1 + y_2 + y_3 = 2$. Then the stars and bars give $\binom{2+2}{2} = 6$ again. Nice and short. Also $x_i \le 2 \leftrightarrow y_i \ge 0$ and $x_i \ge 0 \leftrightarrow y_i \le 2$. But this is indeed automatic. – Henno Brandsma Sep 9 '17 at 9:52
• Sorry, how did you get " =2 " ? – user478905 Sep 9 '17 at 9:52
• @user478905 I expanded it in the comment. – Henno Brandsma Sep 9 '17 at 9:55