combinatorial answer using inclusion exclusion principles

Solution 1:

$A_i={n \choose i}\cdot i!\cdot {{2n-1}\choose i}\cdot B_i$ is the number of arrangement with at least $i$ forbidden consecutive letters.

${n\choose i}$ is the number of choices of letters wanted to be consecutive.

$i!{{2n-1}\choose i}$ is the number of ways to arrange those chosen letters such that each pair is consecutive regardless of other letters. Consider a sequence of $2n-i$ stars, where there is a bar inserted after each star: $$* \vert*\vert*\vert* \dots*\vert*\vert*\vert$$ Then pick $i$ bars out of the $2n-i$ bars, with $i!$ ways to permute the chosen $i$ different letters, then assign them to the selected bars. And then assign the stars in front of the selected bars the same letter. It's easy to see that this is in bijection with the different ways of arranging $2(n-i)$ letters with maximum forbidden adjacency.

Let $B_i$ be the number of ways to arrange $2(n-i)$ letters two of each kind of $(n-i)$ types. $\displaystyle B_i={{2(n-i)}\choose{2,2,\cdots,2}}=\frac{2(n-i)!}{2^{n-i}}$

Hence $\displaystyle\sum^{n}_{i=0}{n\choose i}\cdot i!\cdot {{2n-i}\choose i}\cdot \frac{2(n-i)!}{2^{n-i}}\cdot (-1)^i$ using IEP.

This is similar to a problem from Stanley's EC1, p.226, problem 19.