Question: How many distinct permutations of the word "CORRESPONDENTS" exist in which at least three same letters are adjacent to each other.
EXAMPLE: NNCREREOOSSPDT
ANSWER: $206\times 9!$ according to the test
my solution:
$$9!\times\begin{pmatrix}5\\3\end{pmatrix}\times\dfrac{8\times 9}{2!\times 2!}+9!\times\begin{pmatrix}5\\4\end{pmatrix}\times \dfrac8{2!}+9!\times\begin{pmatrix}5\\5\end{pmatrix}=201\times9!$$
I start by rearranging the nine different letters. Then, I pick three out of the five identical letters and place them next to their matching ones. After that, I add the rest of the letters to complete the arrangement. I do this for both groups of letters, one with four and the other with five adjacent letters.
EDIT: With nine letters in play, we have ten potential spots to place the second 'N.' However, we need to avoid positioning it directly to the left or right of the first 'N.' To account for this, we multiply by (10−2)=8
. We repeat this process for the letter 'S,' which this time yields a total of nine options, as we've already added the second 'N,' creating more available positions.
Additionally, the division by 2!
is essential to account for the fact that identical letters are not counted twice, ensuring the permutations are distinct
Best Answer
Let's follow lulu's suggestion in the comments that we add those permutations in which exactly $3$ pairs of adjacent identical letters occur, exactly four pairs of adjacent identical letters occur, and all five pairs of adjacent identical letters occur.
Exactly three pairs of adjacent identical letters occur: There are $\binom{5}{3}$ ways to select three pairs of adjacent identical letters. Then we have eleven objects to arrange. For example, suppose we have selected OO, RR, EE as our three double letters. Then the eleven objects are OO, RR, EE, S, S, N, N, C, P D, T. These objects can be arranged in $$\frac{11!}{2!2!}$$ distinguishable ways.
However, this counts each arrangement with four pairs of adjacent identical letters four times, once for each of the $\binom{4}{3}$ ways we could have designated three of those four pairs of adjacent identical letters as the adjacent pairs of identical letters. We don't want to count such arrangements at all, so we must subtract four times the number of arrangements with four pairs of adjacent identical letters.
Four pairs of adjacent identical letters: There are $\binom{5}{4}$ ways to select four pairs of adjacent identical letters. Then we have ten objects to arrange. For example, suppose we have selected OO, RR, EE, SS as our four double letters. Then the objects are OO, RR, EE, SS, N, N, C, P, D, T. These objects can be arranged in $\frac{10!}{2!}$ distinguishable ways. Hence, there are $$\binom{5}{4} \cdot \frac{10!}{2!}$$ arrangements with four pairs of adjacent identical letters.
However, if we subtract $\binom{4}{3}\binom{5}{4} \cdot \frac{10!}{2!}$, we will have subtracted too much. That is because, we first counted each arrangement with five pairs of adjacent identical letters $10$ times when we counted arrangements with three pairs of adjacent identical letters, once for each of the $\binom{5}{3}$ ways of designating three of those pairs as the three pairs of adjacent identical letters, then subtracted them $20$ times when we subtracted those arrangements with four pairs of adjacent identical letters, four times each for each of the $\binom{5}{4}$ ways of designating four of those five pairs as the four pairs of adjacent identical letters. We don't want to count arrangements with five pairs of adjacent identical letters at all, so we must add those arrangements $10$ times, once for each of the $\binom{5}{3}$ ways of designating three of those pairs as the three pairs of adjacent identical letters.
Five pairs of adjacent identical letters: If there are five pairs of adjacent identical letters, then we have $9$ distinct objects to arrange: OO, RR, EE, SS, NN, C, P, D, T. They can be arranged in $9!$ ways.
Hence, there are $$\binom{5}{3} \cdot \frac{11!}{2!2!} - \binom{4}{3}\binom{5}{4} \cdot \frac{10!}{2!} + \binom{5}{3}\binom{5}{5} \cdot 9!$$ arrangements with exactly three identical letters.
Exactly four pairs of adjacent identical letters occur: We showed above that there are $$\binom{5}{4} \cdot \frac{10!}{2!}$$ arrangements with four pairs of identical letters.
However, this counts each arrangement with five pairs of adjacent identical letters five times, once for each of the $\binom{5}{4}$ ways of designating four of those five double letters as the four pairs of adjacent identical letters. We don't want to count such arrangements at all, so we must subtract them five times. We found above that there are $9!$ arrangements with five pairs of adjacent identical letters. Hence, there are $$\binom{5}{4} \cdot \frac{10!}{2!} - \binom{5}{4} \cdot 9!$$ arrangements with exactly four pairs of adjacent identical letters.
Exactly five pairs of adjacent identical letters: We showed above that there are $9!$ arrangements with five pairs of adjacent identical letters.
Total: Since the three cases are mutually exclusive and exhaustive, there are $$\binom{5}{3} \cdot \frac{11!}{2!2!} - \binom{4}{3}\binom{5}{4} \cdot \frac{10!}{2!} + \binom{5}{3}\binom{5}{5} \cdot 9! + \binom{5}{4} \cdot \frac{10!}{2!} - \binom{5}{4} \cdot 9! + 9!$$ arrangements of the letters of the word CORRESPONDENTS with at least three pairs of adjacent identical letters.