7
$\begingroup$

How many solutions for equation $x_1+x_2+x_3+x_4+x_5=15$ have exactly two variables equal to 1? ($x_i \ge 1 $)

Hint: think about splitting 15 beans among 5 children, considering the restrictions.

$\endgroup$
  • 1
    $\begingroup$ So you are basically asking about $x_3+x_4+x_5=13$ ? $\endgroup$ – NeilRoy Jun 2 '15 at 16:06
  • $\begingroup$ No, in your equation, $x_1$ and $x_2$ are the variables equal to 1. But that can also happen to $x_3$, $x_4$, and $x_5$. $\endgroup$ – Marcelo Uchimura Jun 2 '15 at 16:44
  • $\begingroup$ Ya what i meant was $x_a+x_b+x_c=13$ ... But ajotatxe's answer seems to be correct! $\endgroup$ – NeilRoy Jun 2 '15 at 16:50
6
$\begingroup$

Step 1: Give 1 bean to each children. There is $1$ way to do this.

Step 2: Choose two of the children and tell them to go home. There are $\binom 52=10$ ways to do this.

Step 3: Give 1 bean to each children left. There is $1$ way to do this. You have $7$ beans left.

Step 4: Distribute at will the beans. This is a bars and stars problem. There are $\binom 92=36$ ways to do this.

Result: $10\cdot 36=360$.

$\endgroup$
  • $\begingroup$ I have two questions: is Step 3 really necessary? As for Step 4, since three children are left, shouldn't the math be $\binom {13}{3}$ instead? $\endgroup$ – Marcelo Uchimura Jun 2 '15 at 16:34
  • $\begingroup$ First question: I feel more confortable with problems in which you can give $0$ beans to somebody. Second question: there are $\binom{n+r-1}{r-1}$ ways to put $r$ equal balls into $n$ different boxes. $\endgroup$ – ajotatxe Jun 2 '15 at 16:56
  • 1
    $\begingroup$ You need Step 3 because you want exactly two kids with one bean. $\endgroup$ – Masclins Jun 3 '15 at 7:31
4
$\begingroup$

Further HINT: There are $\binom52$ ways to choose two of the children to receive one bean each. Once they’ve been chosen, you have $13$ beans to distribute amongst three children in such a way that each child receives at least $2$ beans. There are as many ways to do that as there are to distribute $10$ beans amongst $3$ children so that each child gets at least one bean.

$\endgroup$
2
$\begingroup$

Step 1: Give 1 bean each to any two children and send them home.[${5\choose 2}$ = 10 ways.]

Step 2: Give 2 beans each to the remaining 3 children. 7 beans now remain.

Step 3: Distribute the remaining 7 beans among 3 children any way using "stars and bars" in ${9\choose 2}$ = 36 ways

Result: 10*36 = 360

$\endgroup$
  • 1
    $\begingroup$ You want exactly two kids with one bean. Your system counts cases where three kids have one bean (also four kids, and so on). $\endgroup$ – Masclins Jun 3 '15 at 7:32
  • $\begingroup$ My bad ! Thanks ! Corrected so as not to confuse others ! $\endgroup$ – true blue anil Jun 4 '15 at 4:02
0
$\begingroup$

Subtract $1$ from each variable, so the restriction is $x_i \ge 0$ and $\sum x_i = 10$. You can select the two variables getting value $0$ in $\binom{5}{2}$ ways, for the other three stars-and-bars tells you there are $\binom{10 + 3 - 1}{3 - 1}$ ways of solving the equation, for a total of:

$$ \binom{5}{2} \cdot \binom{10 + 3 - 1}{3 - 1} = 660 $$

solutions.

$\endgroup$
  • $\begingroup$ Two variables would get 0 whereas the three ones left would get 1 or more. So the n for the stars-and-bars problem would be 10 - 3 = 7, right? $\endgroup$ – Marcelo Uchimura May 21 '18 at 11:53

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.