0
$\begingroup$

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! :)

$\endgroup$
  • 1
    $\begingroup$ Welcome to MSE. Please use MathJax. $\endgroup$ – José Carlos Santos Sep 9 '17 at 9:37
  • $\begingroup$ $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. $\endgroup$ – Henno Brandsma Sep 9 '17 at 9:56
  • $\begingroup$ @HennoBrandsma okay noted. So it is $$y_i=2-x_i$$ ? $\endgroup$ – user478905 Sep 9 '17 at 9:58
  • $\begingroup$ Indeed, it is. This is positive exactly when we have at most $2$ per box. $\endgroup$ – Henno Brandsma Sep 9 '17 at 9:59
  • $\begingroup$ @HennoBrandsma sorry again:) , the constraint is $$x_i <= 2$$ but how does it become $$y_i=2-x_i$$? $\endgroup$ – user478905 Sep 9 '17 at 10:07
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hey again, would it be the same technique for $$x_1+x_2+x_3 = 6$$ where $$x_i<=3$$? $\endgroup$ – user478905 Sep 9 '17 at 11:15
  • $\begingroup$ Yes, setting $y_i = 3-x_i$ will work. $\endgroup$ – Henno Brandsma Sep 9 '17 at 11:17
  • $\begingroup$ @user478905 what about $2|2|2$? $\endgroup$ – Henno Brandsma Sep 9 '17 at 12:39
  • $\begingroup$ 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. $\endgroup$ – Henno Brandsma Sep 9 '17 at 12:46
  • $\begingroup$ yes thank you i made several mistakes of not being accurate! $\endgroup$ – user478905 Sep 9 '17 at 14:17
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Henno Brandsma Sep 9 '17 at 9:52
  • $\begingroup$ Sorry, how did you get " =2 " ? $\endgroup$ – user478905 Sep 9 '17 at 9:52
  • $\begingroup$ @user478905 I expanded it in the comment. $\endgroup$ – Henno Brandsma Sep 9 '17 at 9:55

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.