5
$\begingroup$

I wish to distribute $10$ distinct toys to my children $A, B$ and $C$. Each child must get at least one toy, but $A$ must receive an even number of toys, while $C$ must receive an odd number.

How many ways can I go about my distribution?

It's from an exam question. I had stumbled upon it doing my revision, but I still couldn't figure out how to go about solving it.

$\endgroup$
5
$\begingroup$

I think this solution will hold.

As, $A$ receive an even no. of toys, $A$ can get $2,4,6 \text { and } 8$ number of toys.

Now, consider several cases: Whan $A$ gets $2$ toys, $8$ toys are left. So, the else two gets odd number of toys. So, $B$ can get $1,3,5,7$ number of toys.

So, the no. of ways are $${10\choose 2}\left({8\choose 1}+{8\choose 3}+{8\choose 5}+{8\choose7}\right)\tag1$$

Here, $\binom {10}2$ is for selecting $2$ toys for $A$ out of $10$.

Similarly, when $A$ gets $4$ toys, $6$ are left. So, $B$ can get $1,3,5$ no. of toys. So, in analogous way, the no. of way is $${10\choose 4}\left({6\choose1}+{6\choose3}+{6\choose5}\right)\tag2$$.

Similarly, in the case of $A$ gets $6$ toys, the no. of ways are $${10\choose 6}\left({4\choose1}+{4\choose3}\right)\tag3$$

And, when $A$ gets $8$ toys, the no. of ways are $${10\choose8}{2\choose1}\tag4$$

Adding up all $(1),(2),(3)\text{ and }(4)$ and calculating [hint: ${n\choose r}={n\choose n-r}$], you will get the desired result.

Here one can say why I am ignoring the case of $C$, it's only because, when I am considering the cases of $A$ and $B$ getting no. of toys, the remaining toys obviously going to $C$, so we need not consider that case.

$\endgroup$
1
$\begingroup$

Let $|X|$ denote the number of toys child $X$ received. Then $|B|$ has to be odd as well. Assume first that $|B|<|C|$. Then we have $$ (|A|,|B|,|C|)\in\{(2,1,7),(2,3,5),(4,1,5),(6,1,3)\} $$ The number of such combinations can be counted as: $$ \binom{10}2\cdot\binom81+\binom{10}2\cdot\binom83+\binom{10}4\cdot\binom61+\binom{10}6\cdot\binom41=4980 $$ By symmetry of $|B|,|C|$, this figure should be doubled to cover cases $|C|<|B|$. Now assume $|B|=|C|$. Then $$ (|A|,|B|,|C|)\in\{(4,3,3),(8,1,1)\} $$ providing figures $$ \binom{10}4\cdot\binom63+\binom{10}8\cdot\binom21=4290 $$ and these should NOT be doubled. We end up with $$ 2\cdot 4980+4290=14250 $$ ways this can be achieved in total.

$\endgroup$
  • $\begingroup$ I could be wrong, but did you miss out the case for |B|<|C| where another possible combination could be (6, 1, 3)? $\endgroup$ – fer Sep 24 '15 at 19:03
  • $\begingroup$ @fer: Indeed I did. I will edit :/ $\endgroup$ – String Sep 24 '15 at 19:03
1
$\begingroup$

Let's do it for $n$ toys.

Each term in $(A+B+C)^n$, expanded without making use of the commutativity of $A$, $B$, and $C$, corresponds to a way of assigning the toys. We want to eliminate terms in which the total degree of $A$ is odd or the total degree of $C$ is even. This can be done by computing $$ \frac{1}{4}\left[(A+B+C)^n+(-A+B+C)^n-(A+B-C)^n-(-A+B-C)^n\right]. $$ Now we want to eliminate terms in which the total degree of any of $A$, $B$, or $C$ is $0$. Since the total degree of $C$ is now guaranteed odd, we only have to worry about $A$ and $B$. We can eliminate terms that are do not contain any factor of $A$ or any factor of $B$ by subtracting from the expression above the expression with $A$ set to $0$, then subtracting the expression with $B$ set to $0$, and finally by adding the expression with both $A$ and $B$ set to $0$ (to compensate for double-subtraction). We get $$ \begin{aligned} &\frac{1}{4}\left[(A+B+C)^n+(-A+B+C)^n-(A+B-C)^n-(-A+B-C)^n\right]\\ &\quad-\frac{1}{2}\left[(B+C)^n-(B-C)^n\right]-\frac{1}{4}\left[(A+C)^n+(-A+C)^n-(A-C)^n-(-A-C)^n\right]\\ &\quad+\frac{1}{2}\left[C^n-(-C)^n\right]. \end{aligned} $$ The number of terms in the resulting expression is found by setting $A=B=C=1$. This gives $$ \frac{1}{4}\left[3^n-(-1)^n\right]-\frac{1}{2}\left[2^n-0^n\right]-\frac{1}{4}\left[2^n+0^n-0^n-(-2)^n\right]+\frac{1}{2}\left[1^n-(-1)^n\right]. $$ This formula works for any $n$, including $n=0$ with the convention $0^0=1$. If you assume $n>0$, you can make the formula slightly more concise; likewise, if you restrict to odd $n$ or to even $n>0$ you can obtain somewhat shorter formulas: $$ \begin{cases} 0 & n=0,\\ \frac{1}{4}\left[3^n+1\right]-2^n+1 & \text{$n$ odd,}\\ \frac{1}{4}\left[3^n-1\right]-2^{n-1} & \text{$n>0$, even.} \end{cases} $$

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