I've been struggling with the following exercise:
Find the number of sequences of length $2n$ that can be formed with digits from set $A={1,2, ... ,n}$ where every digit has to appear exactly twice in the sequence and no two adjacent elements are alike.
I know that I must use inclusion/exclusion formula, but I don't know exactly how. I am able to count the total number of such sequences, neglecting that the adjacent digits mustn't be the same. What should I do next? I can't fit it to the inclusion/exclusion formula.
Thanks for help in advance!
Each admissible $f:\>[2n]\to[n]$ induces a pairing of $[2n]$ whereby no two adjacent numbers are paired. Denote by ${\cal P}_n$ the set and by $a_n$ the number of such unlabeled pairings of $[2n]$. Given a $w\in{\cal P}_n$ there are $n!$ functions $f:\>[2n]\to[n]$ inducing this $w$, hence there are $n!\, a_n$ admissible functions in all.
In order to determine the $a_n$ I set up a certain generating function scheme, and with the help of Mathematica arrived at the following table: $$(a_n)_{1\leq n\leq10}\quad=\quad (0, 1, 5, 36, 329, 3655, 47844, 721315, 12310199, 234615096)\ .$$ This sequence is listed in OEIS under A278990 and A000806; the second of these is mentioning the problem at hand. In the first reference one finds without proof the following simple recursion for the $a_n$: $$a_1=0,\qquad a_2=1,\qquad a_n=(2n-1)a_{n-1}+a_{n-2}\ .\tag{1}$$ The rest of this answer is devoted to a selfcontained combinatorial proof of $(1)$.
We represent the pairings $w$ as rows of $2n$ colored balls, whereby the colors just serve to identify the pairs and are not to be interpreted as function values. Consider a $w\in{\cal P}_n$ with the leftmost ball red. We distinguish three cases (see the figure):
(i) The second red ball is between two balls of different colors or at the end of the row. In this case we can remove the two red balls and obtain an admissible $w'\in{\cal P}_{n-1}$. Conversely: Given any admissible $w'\in{\cal P}_{n-1}$ we can prepend it by a red ball and insert the second red ball after any of the $2n-2$ balls in $w'$. The result is a $w\in{\cal P}_n$ of the type considered here.
(ii) The second red ball is between two balls of the same color (say blue), whereby there is a ball of a third color immediately to the right of the first red ball. In this case we remove the two blue balls and obtain an admissible $w'\in{\cal P}_{n-1}$. Conversely: Given any admissible $w'\in{\cal P}_{n-1}$ with the leftmost ball red we can place two blue balls immediately to the left and the right of the second red ball. The result is a $w\in{\cal P}_n$ of the type considered here. (This brings us from $2n-2$ to $2n-1$ on the RHS of $(1)$.)
(iii) The arrangement $w$ starts with two interlaced pairs red/blue/red/blue. In this case we remove these four balls and obtain an admissible $w'\in{\cal P}_{n-2}$. Conversely: Given any admissible $w'\in{\cal P}_{n-2}$ we can prepend it with a quadruple red/blue/red/blue and obtain a $w\in{\cal P}_n$ of the type considered here. (This accounts for the last term on the RHS of $(1)$.)