2
$\begingroup$

The question - how many strings of length 8, from 4 letter alphabet, using each letter twice. There is to be exactly one pair of same letters next to each other (example of valid string: AABCDBCD).

I tried to check how this develops by drawing a tree, but it seems that this gets really unwieldy really fast. What counting technique can be used here to make it easier?

$\endgroup$
2
$\begingroup$

If there were no restrictions, we could arrange the letters AABBCCDD in $$\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2} = \frac{8!}{2!6!} \cdot \frac{6!}{4!2!} \cdot \frac{4!}{2!2!} \cdot \frac{2!}{0!2!} = \frac{8!}{2!2!2!2!}$$ distinguishable ways since we can place the two A's in two of the eight available positions, the two B's in two of the six remaining positions, the two C's in two of the four remaining positions, and the two D's in the last two open positions.

We choose which of the four letters is doubled, placing the pair in a box so that we have seven objects - the box containing the double letter, and the other six letters. We choose which of the seven positions will be occupied by that box. The remaining letters can be arranged in $\binom{6}{2}\binom{4}{2}\binom{2}{2}$ ways. Hence, the number of ways of arranging the letters AABBCCDD so that two adjacent letters are the same is $$\binom{4}{1}\binom{7}{1}\binom{6}{2}\binom{4}{2}\binom{2}{2}$$ However, we have counted arrangements in which more than one pair of identical letters are adjacent. We must exclude these from the total.

Suppose two letters are doubled. We choose two of the four letters to be doubled, placing each double letter in a distinct box. This gives us six objects, the two boxes and four remaining letters. We choose which two of the six positions will be occupied by the boxes, arrange them in these positions in $2!$ ways, and then arrange the remaining four letters in $\binom{4}{2}\binom{2}{2}$ ways. This gives $$\binom{4}{2}\binom{6}{2} \cdot 2! \cdot \binom{4}{2}\binom{2}{2}$$ arrangements with two double letters.

Suppose three letters are doubled. We choose three of the four letters to be doubled, placing each double letter in a distinct box. This gives us five objects, the three boxes and the two single letters. We choose three of the five positions for the letters, arrange the boxes in these positions in $3!$ ways, then arrange the remaining two letters in $\binom{2}{2}$ ways. This gives $$\binom{4}{3}\binom{5}{3} \cdot 3! \cdot \binom{2}{2}$$ arrangements with three double letters.

Suppose all four letters are doubled. We place each double letter in a distinct box. The four boxes can be arranged in $4!$ orders.

By the Inclusion-Exclusion Principle, the number of arrangements of AABBCCDD in which there is exactly one pair of adjacent letters that are the same is $$\binom{4}{1}\binom{7}{1}\binom{6}{2}\binom{4}{2}\binom{2}{2} - \binom{4}{2}\binom{6}{2} \cdot 2! \cdot \binom{4}{2}\binom{2}{2} + \binom{4}{3}\binom{5}{3} \cdot 3! \cdot \binom{2}{2} - 4!$$

$\endgroup$
  • $\begingroup$ That was extremely clear and easy to follow! Thank you so much for that! $\endgroup$ – UpsideDownRide Apr 13 '16 at 2:24
3
$\begingroup$

Outline: Use Inclusion/Exclusion. Count first the number of words with a double A. It is perhaps easy to see that there are $\frac{7!}{2!2!2!}$ such words. Similarly, there are $\frac{7!}{2!2!2!}$ with a double B, and so on. So our first estimate is that there are $4\cdot \frac{7!}{2!2!2!}$ words of the desired kind.

However, this double-counts the number of words with, for example, a double A and a double B. There are $\frac{6!}{2!2!}$ such words. There are $\binom{4}{2}$ ways to choose the pair that we will have two doubles of. So our next estimate of the required number of words is $4\cdot \frac{7!}{2!2!2!}-\binom{4}{2}\cdot \frac{6!}{2!2!}$.

However, we have subtracted too much, for we have subtracted one too many times the $\binom{4}{3}\cdot \frac{5!}{2!}$ words of that have three doubles.

After we have added back $\binom{4}{3}\cdot \frac{5!}{2!}$, there is only a little adjustment left to make.

$\endgroup$
  • $\begingroup$ I understand Taussig's answer without any problem. In case of yours I'm not sure where does 7!/(2!*2!) come from. Would you be so kind to direct me on what to read? Thanks a lot! $\endgroup$ – UpsideDownRide Apr 13 '16 at 2:26
  • $\begingroup$ I do not have $\frac{7!}{2!2!}$ anywhere, but do have something similar, with an extra $2!$ at the bottom.. This is the number of ways to arrange $7$ "letters", an AA, two B's, two C's, two D's. So $7$ "letters", giving $7!$, except the two B's are identical and so on, leading to the division by $(2!)^3$. $\endgroup$ – André Nicolas Apr 13 '16 at 3:14
0
$\begingroup$

For starters, let we just consider the cases in which we have a substring $AA$ (the final outcome will be four times this number of strings). By removing such a substring and glueing back together the remaining characters, we have a $6$-character string over the alphabet $\Sigma=\{B,C,D\}$ in which every symbol appears exactly twice and there are no equal adjacent symbols (sub-case $I$) or just one couple of equal adjacent symbols (sub-case $II$). We may deal with the sub-case $II$ just like with the original problem, but respect to a smaller alphabet: we may assume that $BB$ occurs (memo: multiply by three at the end) and by removing $BB$ we may get $CDCD,DCDC$ ($II-I$) or $CDDC,DCCD$ ($II-II$). By considering in which positions between the letters we may re-insert $BB$ back, we have that the sub-case $II$ is covered by $3\cdot(2\cdot 5+2)=36$ strings. The strings accounted by the sub-case $I$ are six times the strings in sub-case $I$ that start with $BC$. The last strings may be only $BCD$ followed by a permutation of $\{B,C,D\}$ whose first element is not $D$ ($4$ cases) or $BCBDCD$ ($1$ case). If follows that the sub-case $I$ accounts for $6\cdot(4+1)=30$ strings. If we are in sub-case $II$, we have just one way to re-insert $AA$ back into the string. If we are in sub-case $I$, we have seven ways. So the answer is given by:

$$ 4\cdot(30\cdot 7+36)=\color{red}{984}. $$

$\endgroup$
  • $\begingroup$ This is what Mathematica says: Length[Select[Permutations[{1, 1, 2, 2, 3, 3, 4, 4}], Count[Differences[#], 0] == 1 &]] gives the same answer. $\endgroup$ – Steve Kass Apr 13 '16 at 2:13
  • $\begingroup$ @SteveKass: that is pleasant to know :) $\endgroup$ – Jack D'Aurizio Apr 13 '16 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.