4 mathematics, 3 physics, 2 chemistry (all distinct) books are supposed to arrange on a bookshelf randomly.
What is the probability that no 2 books from the same major will be placed next to each other?
I may need to use the inclusion-exclusion formula, but I can not see a "good" solution.
Here is what I think:
I first put 4 math books.
$\bigcirc_1 M_1 \bigcirc_2 M_2 \bigcirc_3 M_3 \bigcirc_4 M_4 \bigcirc_5$
The circles 2,3,4 must be filled with physics and chemistry books. There are possibilities:
1) 2,1,1,1,0
2) 0,1,1,1,2
3) 1,1,1,1,1
4) 0,2,1,1,1
5) 1,2,1,1,0
6) 0,1,2,1,1
7) 1,1,2,1,0
8) 0,1,1,2,1
9) 1,1,1,2,0
10) 0,2,2,1,0
11) 0,2,1,2,0
12) 0,1,2,2,0
13) 0,3,1,1,0
14) 0,1,3,1,0
15) 0,1,1,3,0
Then
$\frac{8(3.2.2.3!.4!)+4!.5!+ 3(3.2.2.2.2.4!)+3.3.12.4!}{9!}=\frac{79}{1260}\approx 0.0627$
For cases 1-9, except 3: 2 books should be 1 physics and 1 chemistry. We can choose 1 out of 3 physics books, 1 out of 2 chemistry, they can be ordered 2 different ways PC or CP. The remaining 3 books can be arranged in 3! ways, 4 math books can be arranged in 4! ways. So 3.2.2.3!.4!
case 3: math books can be ordered 4! ways, other 5 books can be ordered 5! ways.
cases 10-12: we need 2 physics and 2 chemistry books for 2-2 cases.
For instance, for 11 (2-1-2). For the leftmost 2, we need one P and one C, they could be PC or CP. So 3.2.2. For the rightmost 2, we choose one P from remaining 2 P, and there is only one C left, they could be PC or CP. So 2.2. And for math books 4!.
similar arguments for 3-1-1 cases.
Best Answer
That the $M$-books etc. are distinct has no significance. It remains to count the admissible arrangements of $MMMMPPPCC$ among the totally ${9!\over4!3!2!}=1260$ possible arrangements. We begin with $PPP$ and insert two $C$s in the following ways:
$$CCPPP \ (2\times), \quad PCCPP \ (2\times),\quad CPCPP \ (4\times),\quad PCPCP,\quad CPPPC\ .\tag{1}$$ The first of these has three enforced $M$s, resulting in $CMCPMPMP$, and then the last $M$ can be placed in one of the circled places here: $\ \circ CMC\circ PMPMP\circ\ $. It follows that the first entry in $(1)$ gives rise to $2\cdot3$ admissible arrangements. Doing this for all $5$ entries in $(1)$ we arrive at $$2\cdot 3+2\cdot{4\choose2}+4\cdot{5\choose 3}+{6\choose4}+{4\choose2}=79$$ admissible arrangements.
The desired probability therefore is ${79\over1260}=0.0627$.