Help me understanding what actually i counted with inclusion-exclusion

Question

I tried to solve following task:

Count number of $8$-permutations from $2$ letters $A$, $2$ letters $B$, $2$ letters $C$ and $2$ letters $D$ where exactly one pair of same letters are adjacent in resulting permutation

My solution is straightforward: let $A_i$ be the number of permutations with at least $i$ pairs of same letters adjacent, then our solution will be $A_1 - A_2 + A_3 - A_4$ $$A_1=\binom{4}{1}\times 7 \times 1! \times \frac{6!}{2^3}$$ $$A_2=\binom{4}{2}\times 15 \times 2! \times \frac{4!}{2^2}$$ $$A_3=\binom{4}{3}\times 10 \times 3! \times \frac{2!}{2^1}$$ $$A_4=\binom{4}{4}\times 1 \times 4! \times \frac{0!}{2^0}$$ My logic is following: first take $i$ pairs of same letters that for sure gonna be adjacent, then count number of possibilities to place those pairs in permutation (i used recurrence relation $f(n,k)=f(n-1,k)+f(n-2,k-1)$ to count number of ways to put $k$ $2$-blocks in $n$-block line), then we can permute those pairs $i!$ times, lastly we permute rest of the letters in $\frac{(8-2i)!}{2^{4-i}}$ ways.

Result of this is $1656$ and correct result (according to my computer program) is $984$, so it seems i'm hugely overcounting something, but i have no idea what.

I'd appreciate some help on this.

Answer 1

There are $7!/2^3=630$ permutations with a pair of adjacent letters A.

There are $6!/2^2=180$ permutations with a pair of adjacent letters A and a pair of adjacent letters B. Same for A and C, and for A and D.

There are $5!/2=60$ permutations with a pair of adjacent letters A and a pair of adjacent letters B and a pair of adjacent letters C. Same for A and B and D, and for A and C and D.

There are $4!=24$ permutations where all letters occur as adjacent pair.

So there are $630-3\times 180+3\times 60-24=246$ permutations that have a pair of adjacent letters A and no other adjacent pair of letters.

So there are $4\times 246=984$ permutations that have exactly one pair of adjacent letters.

Answer 2

You are counting the number of arrangements in which at least one pair of adjacent letters is adjacent.

As you found, by the Inclusion-Exclusion Principle, the number of arrangements that include at least one double letter is $$\binom{4}{1}\frac{7!}{2!2!2!} - \binom{4}{2}\frac{6!}{2!2!} + \binom{4}{3}\frac{5!}{2!} - \binom{4}{4}4!$$ However, we want the number of arrangements in which exactly one double letter occurs. When we count arrangements in which a double letter occurs, we count each arrangement in which two double letters occur twice, each arrangement in which three double letters occur three times, and each arrangement in which four double letters occur four times. Since we do not wish to count these arrangements at all, the number of arrangements in which exactly one double letter occurs is $$\binom{4}{1}\frac{7!}{2!2!2!} - 2\binom{4}{2}\frac{6!}{2!2!} + 3\binom{4}{3}\frac{5!}{2!} - 4\binom{4}{4}4!$$ When we made our initial count of $$\binom{4}{1}\frac{7!}{2!2!2!}$$ we chose a double letter, then arranged the seven objects (the double letter and the three pairs of single letters). In doing so, we counted each arrangement with two double letters twice. For instance, we counted arrangements with a double A and a double B once when we chose the double A and arranged the remaining letters once when we chose the double B and arranged the remaining letters. By similar argument, we counted each arrangement with three double letters three times and each arrangement with four double letters four times, once for each of the ways we could have chosen one of those double letters as our double letter in the initial count.