Learn / Library / Combinatorics

No equal neighbours

CombinatoricsHard

How many distinct strings use all $9$ letters of $COMMITTEE$ (where $M$ , $T$ and $E$ each appear $2$ times) so that no $2$ equal letters are next to each other?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Use inclusion-exclusion on which repeated letters end up adjacent; a glued pair behaves as one object.

Solution

Without restrictions there are $9! \div 2^{3} = 45360$ strings.
Call a letter glued when its copies are adjacent. Gluing a chosen set of $j$ letters leaves $9 - j$ objects with $3 - j$ letters still repeated, giving $(9 - j)! \div 2^{3 - j}$ strings.
For $j = 1$ this is $8! \div 4 = 10080$ for each of the $3$ letters, for $j = 2$ it is $7! \div 2 = 2520$ for each of the $3$ choices, and for $j = 3$ it is $6! = 720$ .
By inclusion-exclusion the answer is $45360 - 3 \times 10080 + 3 \times 2520 - 720 = 21960$ .

Answer: $21960$

Next question Back to the library