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.