I am doing bigger task from combinatorics and stuck at this sub-problem:
Find number of words which every letter A, B, C, D occurs exactly 2 times and exactly 3 pairs of same letters occurs on neighbouring positions
Ok, my approach was just writing some cases and trying to find some rules for that. But I find interesting way to do this without big explanation and I am not sure why it works
Solution
$$ \binom{4}{3}\underbrace{\binom{5}{1}}_{\text{AA}}\underbrace{\binom{4}{1}}_{\text{BB}}\underbrace{\binom{3}{1}}_{\text{CC}} $$
My current understanding
$\binom{4}{3} $ – we choose 3 types of letters from 4 available
$\underbrace{\binom{5}{1}}_{\text{AA}}$ we choose… position for (for example) $A$, probably i'th place and we put to $(i,i+1)$ first letter. But why it is
$$ \underbrace{\binom{5}{1}}_{\text{AA}}$$
And not $$ \underbrace{\binom{7}{1}}_{\text{AA}}$$
Can somebody explain me this approach? It seems interesting and really smart.
Best Answer
The count you gave from the linked question is for at least three pairs of identical letters in adjacent positions in an Inclusion-Exclusion Principle argument.
There are $\binom{4}{3}$ ways of choosing which three pairs of identical letters are in adjacent positions. Suppose, as in your example, they are AA, BB, and CC. Then we have five objects to arrange. They are AA, BB, CC, D, and D. The position of AA can be selected in five ways, the position of BB can be selected in four ways, and the position of CC can be selected in three ways. The Ds must be placed in the remaining two positions. That gives the count $$\binom{4}{3}\binom{5}{1}\binom{4}{1}\binom{3}{1}$$ you found in the linked problem. Notice, however, that this includes arrangements such as $$AADDCCBB$$ in which there are four pairs of adjacent identical letters. There are $4!$ such arrangements for each of the $\binom{4}{3}$ ways we could designate three of the four pairs as the three identical pairs. Hence, the number of arrangements with exactly three pairs of adjacent identical letters is $$\binom{4}{3}\binom{5}{1}\binom{4}{1}\binom{3}{1} - \binom{4}{3}4!$$
Another way to see this is to choose three of the four letters to be the adjacent identical pairs, which can be done in $\binom{4}{3}$ ways. The chosen pairs can be arranged in $3!$ ways. This creates four spaces, two between successive pairs and two at the ends of the row. For instance, suppose the chosen pairs are AA, BB, and CC. Then $$\square AA \square BB \square CC \square$$ is one possible arrangement. To ensure that the remaining two identical letters are separated, we must choose two of the four spaces in which to place the remaining letter. Thus, the number of arrangements of A, A, B, B, C, C, D, D with exactly three pairs of adjacent identical letters is $$\binom{4}{3}3!\binom{4}{2}$$