Find the spot where an overcounting takes place in the application of Principle of inclusion-exclusion (PIE)

Question

Problem:

Use PIE to find the number of rearrangements of the string $11223344$ that contain no two consecutive equal digits.

Answer:

$2520 - 2520 + 1080 - 240 + 24 = 864.$

Below is my analysis for getting the value of the fourth term:

• Let $X_1$ be the set of permutations where each permutation contains the pairs $11, \ 22$ and $33$.

  • Now consider $11p_3p_4p_5p_6p_7p_8$ and $p_1p_2p_3p_4p_5p_611$ where $p_i$ is the $i$th place in the string.

    If we place $22$ as follows -- $1122p_5p_6p_7p_8, \ 11p_3p_4p_5p_622, 22p_3p_4p_5p_611, \ p_1p_2p_3p_42211$ -- then there are three places for $33$. Thus there $4 \times 3 \times \displaystyle{\binom 22} = 12$ such permutations. If $22$ is somewhere in the middle of the string (where there are four places for it) with $11$ at $p_1p_2$ or $p_7p_8$, then there are only two places for $33$. Thus there $\displaystyle{2 \times 4 \times 2 \times \binom 22 = 16}$ permutations of this kind.

  • If $11$ occurs somewhere in the middle of the string, then there are five places for $11$ like so: $ p_111p_4p_5p_6p_7p_8, \ p_1p_211p_5p_6p_7p_8, \ p_1p_2p_311p_6p_7p_8, p_1p_2p_3p_411p_7p_8, \ p_1p_2p_3p_4p_511p_8$.

    • Now consider $p_111p_422p_7p_8, \ p_111p_4p_522p_8, \ p_1p_211p_522p_8, \ p_122p_411p_7p_8, \ p_122p_4p_511p_8, \ p_1p_222p_511p_8$

      In each of these cases there's only one place for $33$. Thus there are $\displaystyle{6 \times 1 \times \binom22 = 6}$ such permutations.

    • Next consider $ p_11122p_6p_7p_8, p_111p_4p_5p_622, \ p_1p_21122p_7p_8, p_1p_211p_4p_522, \ 22p_311p_6p_7p_8, p_12211p_6p_7p_8, p_1p_2p_31122p_8, p_1p_2p_311p_622, 22p_3p_411p_7p_8, p_1p_22211p_7p_8, 22p_3p_4p_511p_8, p_1p_2p_32211p_8$

      In each of these cases there's are two places for $33$. Thus there are $\displaystyle{12 \times 2 \times \binom22 = 24}$ such permutations.

    • Finally, we consider $2211p_5p_6p_7p_8$ and $p_1p_2p_3p_41122$ and there are $\displaystyle{2 \times 3 \times \binom 22 = 6}$ such permutations because there are three places for $33$.

Now $|X_1| = 12 + 16 + 6 + 24 + 6 = 64$. Since there are four pairs, the fourth term is $4|X_1| = 256 \ne 240.$ I am not sure where I am overcounting. Can you, please, tell me if you can spot it? Thanks.

Answer 1

The error is near the beginning: There are $3$, not $4$ places for $22$ in the middle of the string if $11$ is at one of the ends.

In any case, this is terribly complicated. You should be counting like this: There are $5$ objects: $3$ pairs and $2$ remaining numbers. These can be permuted in $5!$ ways, of which $2!$ are equivalent, since the two remaining numbers are identical. Thus there are $\frac{5!}{2!}=60$ different arrangements.

Answer 2

We wish to count the number of permutations of $11223344$ with three pairs of adjacent identical digits.

There are $\binom{4}{3}$ ways to choose the pairs of identical adjacent digits. Say they are $11$, $22$, $33$. Then we have five objects to permute: $11, 22, 33, 4, 4$. Choose two of the five positions for the $4$'s, which can be done in $\binom{5}{2}$ ways. The remaining three distinct objects can be arranged in the remaining three positions in $3!$ ways. Therefore, the number of arrangements containing the adjacent pairs $11$, $22$, $33$ is $$\binom{5}{2}3!$$ so the number of arrangements of $11223344$ in which there are three pairs of adjacent digits is $$\binom{4}{3}\binom{5}{2}3! = 240$$ Avoid doing casework.