Question:
There are 15 different students: 4 students of group A, 5 students of group B and 6 students of group C. What is the number of different ways to seat these students into a row of seats where no two students of the same group are next to each other?
I tried to seat the students of group C first: $$-C-C-C-C-C-C-$$ Then I would put the students of group A and B into the spaces. I tried 2A (2 students from group A) on both ends, A on one end and B on one end, only A on one end, etc, then decide how many students of each group to put in the middle spaces.
There is so many different possibilities that I thought there could be a better way. Do you have any idea? Thanks in advance.
Solution
Let's count the number of strings containing 4 letter A, 5 letter B and 6 letter C.
To begin with, let's set up the $C$s: $$*C-C-C-C-C-C*$$
There are $7$ gaps: $5$ obligatory $(-)$ gaps and $2$ optional $(*)$ gaps.
Now we shall fill in the gaps with $A$s first and $B$s later. The $A$s can't stand next to one another but have some $B$s separate them. Consider some cases:
Case 1: $ABABABA$ and $2$ spare $B$s.
Obviously this is not enough to fill in $5$ $(-)$ gaps
Case 2: $ABABA$, $A$ and $3$ spare $B$s.
Just enough to fill in $5$ $(-)$ gaps: 1 for $ABABA$, $1$ for $A$ and remaining $3$ for $B$s. There are ${5 \choose 1} \cdot {4 \choose 1} = 20$ strings.
Case 3: $ABA$, $ABA$ and $3$ spare $B$s.
Just enough to fill in $5$ $(-)$ gaps: $2$ for $ABA$ and $3$ remainings for $B$s. There are ${5 \choose 2} = 10$ strings.
Case 4: $ABA$, $A$, $A$ and $4$ spare $B$s.
We have more than enough to fill in the $(*)$ gaps now, with $3$ options:
Option 1: Fill in $2$ $(*)$: Just enough for $7$ gaps: $1$ for $ABA$, $2$ for $A$s and $4$ remainings for $B$. There are ${1 \choose 7} \cdot {2 \choose 6} = 105$ strings.
Option 2: Fill in $1$ $(*)$, we have $3$ more sub-options:
Fill it with $ABA$. To fill the $5$ $(-)$s: $2$ for $A$s and $3$ remaining for $B$s. One spare $B$.
Fill it with $A$. To fill the $5$ $(-)$s: $1$ for $ABA$, $1$ for $A$s and $3$ remaining for $B$s. One spare $B$.
Fill it with $B$. To fill the $5$ $(-)$s: $1$ for $ABA$, $2$ for $A$s and $2$ remaining for $B$s. One spare $B$.
Note that we have $2$ $(*)$ gaps and the spare $B$ can be put into $6$ gaps next to $A$s. There are $2 \cdot \left[ {5 \choose 2} + {5 \choose 1} \cdot {4 \choose 1} + {5 \choose 1} \cdot {4 \choose 2}\right] \cdot {6 \choose 1} = 720$ strings.
Option 3: Fill $0$ $(*)$ gap. To fill the $5$ $(-)$s: $1$ for $ABA$, $2$ for $A$s and $2$ remaining for $B$s. Two spare $B$s can be put into $6$ gaps next to $A$s. There are ${5 \choose 1} \cdot {4 \choose 2} \cdot {6 \choose 2} = 450$ strings.
Case 5: $A$, $A$, $A$, $A$ and $5$ spare $B$s.
This should be the same:
Option 1: This one is different from last time but just like Option 2. There are $\left[ {5 \choose 2} + {2 \choose 1} \cdot {5 \choose 3} + {5 \choose 4}\right] \cdot {8 \choose 2} = 980$ strings.
Option 2: $2 \cdot \left[ {5 \choose 3} + {5 \choose 4} \right] \cdot {8 \choose 3} = 1680$ strings.
Option 3: ${5 \choose 4} \cdot {8 \choose 4} = 350$ strings.
To sum it up:
The total number of desired strings is $20 + 10 + 105 + 720 + 450 + 700 + 1680 + 350 = 4315$ strings.
So there should be $4315 \cdot 4! \cdot 5! \cdot 6! = 8947584000$ ways of seating these students.
The simplest approach would be to set up a counting algorithm using recurrence relations. To this end consider the function $P^{(A)}_n(a,b,c)$ that counts the number of valid strings formed by $a$ times an $A$, $b$ times a $B$, and $c$ times a $C$, that satisfy the constraint that no two $A$'s, $B$'s, or $C$'s will be adjacent, and that will start with an $A$ as the first character. Similarly, we consider the functions $P^{(B)}_n(a,b,c)$ and $P^{(C)}_n(a,b,c)$. The arguments are non-negative $a,b,c \geq 0$ and $n=a+b+c \geq 1$ is the length of the string.
For $n=1$ the functions are initialised by $$ P^{(A)}_1(1,0,0) = P^{(B)}_1(0,1,0) = P^{(C)}_1(0,0,1) = 1 $$ and zero otherwise.
We then know that the number of string of length $n+1$ starting with an $A$ can be expressed as: $$ P^{(A)}_{n+1}(a+1,b,c) = P^{(B)}_{n}(a,b,c) + P^{(C)}_{n}(a,b,c) $$ and like-wise $$ P^{(B)}_{n+1}(a,b+1,c) = P^{(A)}_{n}(a,b,c) + P^{(C)}_{n}(a,b,c) $$ $$ P^{(C)}_{n+1}(a,b,c+1) = P^{(A)}_{n}(a,b,c) + P^{(B)}_{n}(a,b,c) $$
It is clear that the three types of function are symmetric and related under permutations of labels $$ P^{(A)}_{n}(a,b,c)=P^{(A)}_{n}(a,c,b)=P^{(B)}_{n}(c,a,b)=P^{(C)}_{n}(b,c,a) $$ We therefore have not three relations but only a single one, i.e., $$ P^{(A)}_{n+1}(a+1,b,c) = P^{(A)}_{n}(b,c,a) + P^{(A)}_{n}(c,a,b) $$ Since we know that $n=a+b+c$ we can drop the subscript $n$, and if we choose that the first character of a string corresponds to one of which the total number corresponds to the first argument this simplifies to $$ P(a+1;b,c) = P(b;c,a) + P(c;a,b) $$ with $P(1;0,0)=1$ and $P(x;y,z)=0$ whenever one or more arguments are negative.
This can easily be programmed and we find that the total number of strings of the problem can be found as $$ P(4;5,6) + P(5;6,4) + P(6;4,5) = 4315 $$
It is also possible to directly count the number of strings by using a suitable classification system. For instance the six $C$'s will not be adjacent in the string $$ *C-C-C-C-C-C* $$ Hence at the locations $-$ there has to be some combination of $A$'s and $B$'s, and at the locations $*$ there might be such a string.
The four $A$'s will have to be placed within those 7 locations. They can be distributed in five types of fashion, i.e., $\{$ABABABA$\}$ when all $A$'s are found at a single of the seven locations (properly separated by $B$'s of course). The other four types split the $A$'s in two, three, or four smaller groups $\{$ABABA,A$\}$,$\{$ABA,ABA$\}$,$\{$ABA,A,A$\}$,$\{$A,A,A,A$\}$ that each have to be placed at a different location within the 7 possible ones. Within this process some of the $B$'s are already fixed by necessity to separate the $A$'s, some others will have to be at one or more particular locations to form $CBC$ combinations. The remaining $B$'s can be distributed either as $ABC$,$CBA$-combinations or at the outer ends of the string.
A careful counting and analysis is needed for each case to find the appropriate number of strings. For instance the first type $\{ABABABA\}$ can actually not occur, as it would results in two adjacent $C$'s.
Give it a go and let me know if and where you get in trouble.