How many ways are there to arrange 3 physics books, 3 math books and 3 chemistry books so that no two books of the same subject are next to each other. All the books of the same subject are distinct.
I tried subtracting the number of permutations that don't satisfy the condition from the total number of permutations. I used inclusion-exclusion principle for this. I believe that this is the correct approach but I seem to be missing something.
Let's say there are two books of the same subject next to each other. We can take books of any of the 3 subjects. There are 3 (3nCr2) ways to select a pair. The two books within a pair can be arranged in two ways (ab, ba). We can look at this pair as a single book. Therefore there are 8! permutations where the two previously selected books are next to each other. This gives us 3*3*2*8!. It's obvious that there are many repeating permutations here (this is 2*9! which is the total number of permutations of the 9 books). Obviously there are permutations when there are 2 books of 2 subjects next to each other. There are 3 combinations of the subjects. The two books can be selected in 3 ways each. And within a pair of books there can be 2 ways books can be arranged. Looking at the pairs of books of the same subject next to each other as a single book gives us 7! permutatios. This means we should add 3*3*2*3*2*7!. Now we need to subtract the permutations where the number of elements where there are at least two books of each pair next to each other. Following the same line of reasoning we get 3*2*3*2*3*2*6!. Now let's denote as a,b,c the books of one subject, doesn't matter which one. Notice that when we have all three books next to each other abc it doesn't matter which pair we chose in the previous example because they are going to repeat. If we take ab and then comes c is the same as bc coming after a. So we need to add back those permutations that we subtracted in the first subtraction. So we subtract 3*3!*7!. Following the same reasoning we can add back the number of permutations where we have 2 triplets of books of the same subject next to each other which is 3*3!*3!*5!. Finally we need to add 3!*3!*3!*3! for the case where there are 3 triplets of the books of the same subject. When I compute the whole expression I get 103 896. I don't have a solution but I've written the following Python script to calculate the result and I get 37 584.
from itertools import permutations
x = [1]*3
x.extend([2]*3)
x.extend([3]*3)
s = 0
for perm in permutations(x):
for i in range(8):
if perm[i] == perm[i+1]:
s += 1
break
print(362880 - s)
Hope you understand my line of reasoning, sorry if it is too long.
Best Answer
Since the books are distinct, there are $9!$ ways to arrange them. From these, we must exclude those arrangements in which one or more books of the same subject are adjacent.
A pair of books of the same subject are adjacent: There are three ways to pick the subject from which the books are selected and $\binom{3}{2}$ ways to pick two of the three books from that subject. This gives us eight objects to arrange, the block of books from the same subject and the other seven books. They can be arranged in $8!$ ways. The books within the block can be arranged in $2!$ ways. Hence, there are $$\binom{3}{1}\binom{3}{2}8!2!$$ arrangements in which a pair of books of the same subject are adjacent.
Two pairs in which books of the same subject are adjacent: This can occur in two ways.
Both pairs are from the same subject: There are three ways to pick the subject. We have seven objects to arrange, the block of three books from one subject and the other six books. They can be arranged in $7!$ ways. The books within the block can be arranged in $3!$ ways. Hence, there are $$\binom{3}{1}7!3!$$ such arrangements.
The pairs come from two different subjects: There are $\binom{3}{2}$ ways to pick the subjects from which the pairs are taken. There are $\binom{3}{2}$ ways to select which two of the three books are selected from each of those subjects. We have seven objects to arrange, the two blocks and the other five books. The objects can be arranged in $7!$ ways. The books within each block can be arranged in $2!$ ways. Hence, there are $$\binom{3}{2}\binom{3}{2}^27!2!^2$$ such arrangements.
Three pairs in which books of the same subject are adjacent: This can also occur in two ways.
Two pairs are from the same subject and one pair is taken from a different subject: There are three ways to select the subject from which two pairs of adjacent books are selected. This leaves two ways to select the subject from which one pair of adjacent books is selected. The books from that subject can be selected in $\binom{3}{2}$ ways. This gives us six objects to arrange, the block of three books, the block of two books, and the other four books. The objects can be arranged in $6!$ ways. The three adjacent books from the same subject can be arranged in $3!$ ways within their block. The pair of adjacent books from the second subject can be arranged in $2!$ ways within their block. Hence, there are $$\binom{3}{1}\binom{2}{1}\binom{3}{2}6!3!2!$$ such arrangements.
One pair is taken from each of the three subjects: There are $\binom{3}{2}$ ways to select two of the three books from each subject. This gives us six objects to arrange, the three blocks and the other three books. They can be arranged in $6!$ ways. Within each block, the books can be arranged in $2!$ ways. Hence, there are $$\binom{3}{2}^36!2!^3$$ such arrangements.
Four pairs in which books of the same subject are adjacent: This can also occur in two ways.
Two adjacent pairs are selected from each of two subjects: There are $\binom{3}{2}$ ways to choose the two subjects from which two pairs of adjacent books are selected. This gives us five objects to arrange, the two blocks of three books from the same subject and the other three books. The objects can be arranged in $5!$ ways. Each block can be arranged internally in $3!$ ways. Hence, there are $$\binom{3}{2}5!3!^2$$ such arrangements.
Two adjacent pairs are selected from one object and one pair each is selected from the other two subjects: There are three ways to select the subject from which two pairs are taken. For each of the remaining subjects, there are $\binom{3}{2}$ ways to select which two books will in the pair. This gives us five objects to arrange, the block of three books from one subject, the two blocks of adjacent pairs, and the other two books. The objects can be arranged in $5!$ ways. The three adjacent books from one subject can be arranged within their block in $3!$ ways. In each pair of adjacent books, the books can be arranged within their blocks in $2!$ ways. Hence, there are $$\binom{3}{1}\binom{3}{2}^25!3!2!^2$$ such arrangements.
Five pairs in which books of the same subject are adjacent: It must be the case that there are two subjects from which two pairs of adjacent books are selected and one subject from which a pair of adjacent books are selected. There are $\binom{3}{2}$ ways to select the subject from which two pairs of adjacent books are selected. There are $\binom{3}{2}$ ways to select two of the three books from the remaining subject for the pair. This gives us four objects to arrange, the two blocks of three books of the same subject, the block of two books of the remaining subject, and the other book. The objects can be arranged in $4!$ ways. Each block of three books can be arranged internally in $3!$ ways. The block of two books can be arranged internally in $2!$ ways. Hence, there are $$\binom{3}{2}\binom{3}{2}4!3!^22!$$ such arrangements.
Six pairs in which books of the same subject are adjacent: This can only occur if all three books of each subject are adjacent. This gives us three objects to arrange, the three blocks consisting of three books of the same subject. The objects can be arranged in $3!$ ways. Within each block, the books can be arranged in $3!$ ways. Hence, there are $$3!3!^3$$ such arrangements.
By the Inclusion-Exclusion Principle, the number of arrangements in which no two books of the same subject are adjacent is $$9! - \binom{3}{1}\binom{3}{2}8!2! + \binom{3}{1}7!3! + \binom{3}{2}\binom{3}{2}^27!2!^2 - \binom{3}{1}\binom{2}{1}\binom{3}{2}6!3!2! - \binom{3}{2}^36!2!^3 + \binom{3}{2}5!3!^2 + \binom{3}{1}\binom{3}{2}^25!3!2!^2 - \binom{3}{2}\binom{3}{2}4!3!^22! + 3!3!^3$$