# Combinatorics for RMO and IITJEE maths

Problem:

How many arrangements of 5 $\alpha$‘s, 5 $\beta$‘s and $\gamma$‘s are there with at least one $\beta$ and at least one $\gamma$ between each successive pair of $\alpha$‘s?

Solution:

There are three cases:

1. Exactly one $\beta$ and one $\gamma$ between each pair of $\alpha$‘s: Between each of the four pairs of $\alpha$‘s, the $\beta$ or the $\gamma$ can be first — $2^{4}$ ways. The fifth $\beta$ and fifth $\gamma$ along with the sequence of the rest of the letters can be considered as 3 objects to be arranged — $3!$ ways. Altogether, $2^{4} \times 3!=96$ ways.
2. Exactly, one $\beta$ between each pair of $\alpha$‘s and two $\gamma$‘s between some pair of $\alpha$‘s (or two $\beta$‘s between some pair of $\alpha$‘s and exactly one $\gamma$ between each pair of $\alpha$‘s): there are four choices for between which pair of $\alpha$‘s the two $\gamma$‘s go and 3 ways to arrange the two $\gamma$‘s and one $\beta$ there. There are two $2^{3}$ choices for whether the $\beta$ or the $\gamma$ goes first between the other 3 pairs of $\alpha$‘s and 2 choices for at which end of the arrangement the fifth $\beta$ goes. Multiplying by 2 for the case of two $\beta$‘s between some pair of $\alpha$‘s, we obtain $2 \times (4 \times 3 \times 2^{3} \times 2)=384$ ways.
3. Two $\beta$‘s between some pair of $\alpha$‘s and two $\gamma$‘s between some pair of $\alpha$‘s. There are two subcases. If the two $\beta$‘s and two $\gamma$‘s are between the same pair of $\alpha$‘s, there are 4 choices for which pair of $\alpha$‘s, $C(4,2)$ ways to arrange them between this pair of $\alpha$‘s, and $2^{3}$ choices for whether the $\beta$ or the $\gamma$ goes first between the other 3 pairs of $\alpha$‘s. If two $\beta$‘s and two $\gamma$‘s are between the different pairs of $\alpha$‘s, there are $4 \times 3$ ways to pick between which $\alpha$‘s  the two $\beta$‘s and then between which $\alpha$‘s the two $\gamma$‘s go, $3^{2}$ ways to arrange the two $\gamma$‘s and one $\beta$ and to arrange the one $\gamma$ and two $\beta$‘s, and $2^{2}$ choices for whether the $\beta$ or the $\gamma$ goes first between the other 2 pair of $\alpha$‘s. Together, $4 \times C(4,2) \times 2^{3} + 4 \times 3 \times 3^{2} \times 2^{2}=1056$ ways.

All together, the three cases give us a total of $96+384+1056=1536$ arrangements.

More later,

Nalin Pithwa

This site uses Akismet to reduce spam. Learn how your comment data is processed.