# Permutation: Distribute 10 distinct items in 3 boxes: one box contain odd number, one box even number object , and all boxes at least one item.

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.

## 3 Answers

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.

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.

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

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