How many ways to visit 6 cities twice without visiting the same city twice in a row?

Question

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 $$

Answer 1

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.

Answer 2

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.