2 standard 52 card decks, how many sequences with exactely 12 adjacent pairs of identical cards? I am doing recreational math as a pastime. I like to do math exams and such and also to come up with math-puzzles on my own.
Recently i was doing the following MIT math exam:
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/exams/MIT6_042JF10_final_2004.pdf
It was super fun! :-)
Anyway, here is problem 7:

That problem got me thinking about the problem I described below.

Take 2 standard 52 card decks.
Then you can take those cards and form sequences.
There are a total of $104! / 2^{52}$ possible different sequences.
From all of those only $52!$ exist that have $52$ pairs of identical cards placed right next to one another. For example ( Ad,Ad,Ah,Ah,As,As,...)
How many sequences are there with exactly 12 pairs?
Can anyone help me out?
 A: Here we use PIE
, the principle of inclusion-exclusion as proposed by @ThomasAndrews. We then look at a small example which is intended as plausibility check and we provide an algebraic derivation.
The problem: We look at the more general case, consider $n$ pairwise different cards instead of $52$ and take two decks of them. We already know according to OP, the number of different sequences is
\begin{align*}
\frac{(2n)!}{2^n}\tag{1}
\end{align*}
since we can take all permutations of length $2n$ and identify $n$ pairs of the same type. We are looking for  the number of sequences which contain exactly $q$ pairs of the same type placed right next to one another, i.e. which form a run of length $2$.
PIE: We have $\binom{n}{q}$ ways to choose $q$ pairwise different cards which form the runs of length $2$. We take these $q$ cards from the deck and have now $2n-q$ cards from which we can make
\begin{align*}
\frac{(2n-q)!}{2^{n-q}}\tag{2}
\end{align*}
different sequences. In (2) we have $n-q$ pairs left which justifies the denominator $2^{n-q}$. Note, the so derived number
\begin{align*}
\binom{n}{q}\frac{(2n-q)!}{2^{n-q}}
\end{align*}
does not give the number of sequences with exactly $q$ pairs having runs of length $2$ but the number of sequences with at least $q$ pairs with runs of length $2$ instead. The number of sequences counted in (2) does also count sequences with runs of length $2$ of other than the selected $q$ pairs.
This is when PIE comes into play, since it enables us to transform at least information into exact information. Subtracting the number of sequences which contain at least $q+1$ pairs and adding the number which contain at least $q+2$ pairs, etc. gives the necessary compensation of over- and undercounting to finally derive the number of sequences with exakt $q$ pairs with runs of length $2$. The so derived formula is
\begin{align*}
\color{blue}{\binom{n}{q}\sum_{k=0}^{n-q}(-1)^k\binom{n-q}{k}\frac{(2n-q-k)!}{2^{n-q-k}}\qquad\qquad 0\leq q\leq n}\tag{3}
\end{align*}
Small example: $n=3, q=1$ We calculate as plausibility check of (3) a small example. We consider three differenct types of cards $a,b,c$ and look- for the number of valid sequences of length $6$ which have exactly one pair with a run of length $2$.

We obtain from (3)
\begin{align*}
\binom{3}{1}&\sum_{k=0}^{2}(-1)^k\binom{2}{k}\frac{(5-k)!}{2^{2-k}}\\
&=\binom{3}{1}\left(\binom{2}{0}\frac{5!}{2^2}-\binom{2}{1}\frac{4!}{2^1}
+\binom{2}{2}\frac{3!}{2^0}\right)\\
&=3\left(30-24+6\right)\\
&\,\,\color{blue}{=36}
\end{align*}
The valid $\color{blue}{36}$ sequences having exactly one pair with run of length $2$ are
\begin{align*}
\begin{array}{cccccc}
\mathrm{\color{blue}{aa}bcbc}&\mathrm{\color{blue}{aa}cbcb}&\mathrm{b\color{blue}{aa}cbc}&\mathrm{bc\color{blue}{aa}bc}&\mathrm{bc\color{blue}{aa}cb}&\mathrm{bcb\color{blue}{aa}c}\\
\mathrm{bcbc\color{blue}{aa}}&\mathrm{c\color{blue}{aa}bcb}&\mathrm{cb\color{blue}{aa}bc}&\mathrm{cb\color{blue}{aa}cb}&\mathrm{cbc\color{blue}{aa}b}&\mathrm{cbcb\color{blue}{aa}}\\
\mathrm{a\color{blue}{bb}cac}&\mathrm{aca\color{blue}{bb}c}&\mathrm{acac\color{blue}{bb}}&\mathrm{ac\color{blue}{bb}ac}&\mathrm{ac\color{blue}{bb}ca}&\mathrm{\color{blue}{bb}acac}\\
\mathrm{\color{blue}{bb}caca}&\mathrm{ca\color{blue}{bb}ac}&\mathrm{ca\color{blue}{bb}ca}&\mathrm{caca\color{blue}{bb}}&\mathrm{cac\color{blue}{bb}a}&\mathrm{c\color{blue}{bb}aca}\\
\mathrm{abab\color{blue}{cc}}&\mathrm{aba\color{blue}{cc}b}&\mathrm{ab\color{blue}{cc}ab}&\mathrm{ab\color{blue}{cc}ba}&\mathrm{a\color{blue}{cc}bab}&\mathrm{baba\color{blue}{cc}}\\
\mathrm{bab\color{blue}{cc}a}&\mathrm{ba\color{blue}{cc}ab}&\mathrm{ba\color{blue}{cc}ba}&\mathrm{b\color{blue}{cc}aba}&\mathrm{\color{blue}{cc}abab}&\mathrm{\color{blue}{cc}baba}
\end{array}
\end{align*}

Algebraic derivation: Formula (3) gives the number of valid sequences with $q$ pairs with runs of length $2$ with $0\leq q\leq n$. Since the number of all valid sequences is $\frac{(2n)!}{2^n}$
according to (1), we sum up over $q$ and claim
\begin{align*}
\sum_{q=0}^n\binom{n}{q}\sum_{k=0}^{n-q}(-1)^k\binom{n-q}{k}\frac{(2n-q-k)!}{2^{n-q-k}}=\frac{(2n)!}{2^n}\qquad n\geq 0\tag{4}
\end{align*}

We start with the left-hand side of (4) and obtain
\begin{align*}
\color{blue}{\sum_{q=0}^n}&\color{blue}{\binom{n}{q}\sum_{k=0}^{n-q}(-1)^k\binom{n-q}{k}\frac{(2n-q-k)!}{2^{n-q-k}}}\\
&=\sum_{q=0}^n\binom{n}{q}\sum_{k=0}^{q}(-1)^k\binom{q}{k}\frac{(n+q-k)!}{2^{q-k}}\tag{4.1}\\
&=\sum_{q=0}^n\binom{n}{q}\sum_{k=0}^{q}(-1)^k\binom{q}{k}\frac{(n+k)!}{2^{k}}\tag{4.2}\\
&=\sum_{k=0}^n(-1)^k\frac{(n+k)!}{2^k}\sum_{q=k}^n\binom{n}{q}\binom{q}{k}(-1)^q\tag{4.3}\\
&=\sum_{k=0}^n(-1)^k\binom{n}{k}\frac{(n+k)!}{2^k}\sum_{q=k}^n\binom{n-k}{n-q}(-1)^q\tag{4.4}\\
&=\sum_{k=0}^n\binom{n}{k}\frac{(n+k)!}{2^k}\sum_{q=0}^{n-k}\binom{n-k}{q}(-1)^q\tag{4.5}\\
&=\sum_{k=0}^n\binom{n}{k}\frac{(n+k)!}{2^k}(1-1)^{n-k}\tag{4.6}\\
&\,\,\color{blue}{=\frac{(2n)!}{2^n}}
\end{align*}
and the claim follows.

Comment:

*

*In (4.1) we change the order of summation of the outer sum $q\to n-q$.


*In (4.2) we change the order of summation of the inner sum $k\to q-k$.


*In (4.3) we exchange inner and outer sum respecting the index region: $0\leq q\leq k\leq n$.


*In (4.4) we use the binomial identity $\binom{n}{q}\binom{q}{k}=\frac{n!}{(n-q)!}\cdot\frac{1}{k!(q-k)!}=\binom{n}{k}\binom{n-k}{n-q}$.


*In (4.5) we shift the index of the inner sum to start with $q=0$.


*In (4.6) we apply the binomial theorem and observe that all summands with $k<n$ are zero.
