Inclusion-exclusion with anagrams

Question

How many are the permutations of the letters of the word PROPOR in which are not consecutive letters equal?

How to approach this problem through the principle of inclusion-exclusion?

Answer 1

There are $6!/2^3=90$ ways to arrange the letters. There are $5$ spots where we can place two consecutive equal letters, and $3$ choices for the letter. Once we have placed them, we have $4!/2^2=6$ ways to arrange the other $4$ letters, giving $5\cdot3\cdot6=90$ ways to put to like letters next to one another.

However, we have subtracted the arrangements with two pairs of equal letters twice, so we have to add these back in. The heart of the problem is figuring out how many ways there are for this to happen. If the first pair occupies spots $1$ and $2$, the first letter of the second pair must occupy spot $3$,$4$, or $5$, giving $3$ ways. Likewise, there are $2$ ways if the first pair occupies spots $2$ and $3$, and $1$ way if the occupy spots $3$ and $4$, so $6$ ways in all. There are $6$ ways to decide which two letters will occupy these positions, and then there is only one choice for the remaining spots. This gives $6\cdot6=36$ ways to have two pairs.

Now an arrangement with $3$ like pairs has been added in the original $90$, subtracted $3$ times in the second $90$, and added $3$ times in the $36$. Since we don't want to count it, it must be subtracted. There are clearly $6$ such arrangements, so the answer is $$\boxed{90-90+36-6=30}$$

Answer 2

Lets solve the inverse problem to count number of permutations where two letters appear side by side. Suppose set $A_i$ ($i=P, O, R$) denotes the set of permutations where character i comes together. Then in order to solve the problem we have to compute $\lvert A_P \bigcup A_O \bigcup A_R \rvert$ and then subtract from the total possible permutations ($6!/2^3 = 90$). So by inclusion-exclusion, we have:

$$\lvert A_P\bigcup A_O\bigcup A_R \rvert = \lvert A_P\rvert + \lvert A_O\rvert + \lvert A_R\rvert - \lvert A_P \bigcap A_O\rvert - \lvert A_P \bigcap A_R\rvert - \lvert A_R \bigcap A_O\rvert + \lvert A_P \bigcap A_O \bigcap A_R\rvert$$

Now, $\lvert A_i \rvert = 5!/2.2 $; since we can treat two consecutive character as single character then we have to permute 3 different objects of counts 1,2,2. For example suppose we are counting for P, then we can treat PP as (say D) single character and now this is equivalent to permute $DOORR$ which would be $5!/4$, this would be same for all $A_i$s.

Similarly we can calculate pair-wise count, which would $\lvert A_i \bigcap A_j \rvert = 4!/2 $, and finally $\lvert A_P \bigcap A_O \bigcap A_R\rvert = 3!$

So $$ \lvert A_P\bigcup A_O\bigcup A_R \rvert = 3*5!/4 - 3*4!/2 + 3! = 60 $$

and hence answer would be $30$.