How many ways to visit 6 cities twice without visiting the same city twice in a row? A person wishes to visit 6 cities, each exactly twice, and never visiting the same city twice in a row. In how many ways can this be done?
I tried complement. Define $S(n)$ as the number of permutations wherein exactly $n$ cities are visited twice in a row, then the answer is $S(0)$.
$S(6)$ is simple:
$$S(6) = C_6^6 P_6^6$$
But starting from $S(5)$, things become convoluted because $S(i)$ involves partial $S(i+1)$:
$$
S(5) = C_6^5(\frac{P_7^7} {P_2^2} - C_1^1 P_6^6)
$$
$$
S(4) = C_6^4[\frac{P_8^8} {(P_2^2)^2} - C_2^1 (\frac{P_7^7} {P_2^2} - C_1^1 P_6^6) - C_2^2 P_6^6]
$$
$$
\vdots
$$
 A: You can do this using inclusion–exclusion. There are $2^{k-6}(12-k)!$ arrangements in which $k$ particular cities are visited twice in a row, so there are
$$
2^{-6}\sum_{k=0}^6(-2)^k\binom6k(12-k)!=2631600
$$
arrangements in which no city is visited twice in a row.
A: If you don't know inclusion-exclusion, you may find the answer by setting up a recurrence relation. Let $T_n(k)$ be the number of ways to visit $n$ different cities, such that each city is visited exactly twice and $k$ out of $n$ cities are visited twice in a row. We want to find $T_6(0)$. Note that
$T_1(0)=0,\ T_1(1)=1,\ T_1(2)=0$ and for $n\ge2,\ k=0,1,\ldots,n$, we have
$$
\begin{align*}
T_{n}(k)
&= (2n-k)\ \ T_{n-1}(k-1)\\
&+\ \left[k + {2n-1-k\choose 2}\right]\ \ T_{n-1}(k)\\
&+\ (k+1)(2n-k-2)\ \ T_{n-1}(k+1)\\
&+\ {k+2\choose 2}\ \ T_{n-1}(k+2).
\end{align*}
$$
For instance, we can explain the coefficient ${k+2\choose 2}$ of $T_{n-1}(k+2)$ as follows. Suppose we are given an itinerary of visiting $n-1$ cities such that each city is visited twice but exactly $k+2$ of them are visited twice in a row. We now try to add one more city $C$ to this itinerary, so that this city is also visited twice and after the addition, only $k$ cities are visited twice in a row. To do so, we have to choose two cities $A$ and $B$ in the old itinerary, such that each of them are visited twice (denoted $AA$ and $BB$) in a row. We then insert the visits to $C$ so that we have $ACA$ and $BCB$ in the new itinerary. Since there are ${k+2\choose 2}$ ways to pick two cities out of those $k$ cities that are visited twice in a row in the old itinerary, you get the coefficient for $T_{n-1}(k+2)$. You may try to figure out how the other coefficients arise.
Using the above recurrence relation, I got $T_6(0)=2631600$, which agrees with Joriki's answer.
