Cómo muchas maneras de visitar 6 ciudades dos veces sin visitar la misma ciudad dos veces en una fila?

Question

Una persona desea visitar 6 ciudades, exactamente dos veces, y nunca a visitar la misma ciudad dos veces en una fila. De cuántas maneras se puede hacer esto?

Traté de complemento. Definir $S(n)$ como el número de permutaciones en donde exactamente $n$ ciudades visitadas dos veces en una fila, entonces la respuesta es $S(0)$.

$S(6)$ es simple:

$$S(6) = C_6^6 P_6^6$$

Pero a partir de $S(5)$, las cosas se vuelven complicado debido a $S(i)$ implica parcial $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

Usted puede hacer esto mediante la inclusión–exclusión. Hay $2^{k-6}(12-k)!$ arreglos en los que $k$ particular las ciudades son visitado dos veces en una fila, por lo que hay

$$2^{-6}\sum_{k=0}^6(-2)^k\binom6k(12-k)!=2631600$$

arreglos en los que ninguna ciudad es visitada dos veces en una fila.

Answer 2

Si usted no sabe de inclusión-exclusión, usted puede encontrar la respuesta mediante el establecimiento de una relación de recurrencia. Deje $T_n(k)$ el número de maneras de visitar $n$ diferentes ciudades, de tal manera que cada ciudad es visitada exactamente dos veces y $k$ $n$ ciudades visitadas dos veces en una fila. Queremos encontrar a $T_6(0)$. Tenga en cuenta que $T_1(0)=0,\ T_1(1)=1,\ T_1(2)=0$ $n\ge2,\ k=0,1,\ldots,n$ , tenemos $$\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*}$$ Por ejemplo, podemos explicar el coeficiente de ${k+2\choose 2}$ $T_{n-1}(k+2)$ como sigue. Supongamos que tenemos un itinerario de visita a $n-1$ ciudades de tal manera que cada ciudad es visitada dos veces, pero exactamente $k+2$ de ellos se visitó dos veces en una fila. Ahora tratamos de añadir uno más de la ciudad de $C$ a este itinerario, por lo que esta ciudad también es visitado en dos ocasiones y después de la adición, sólo $k$ ciudades visitadas dos veces en una fila. Para ello, tenemos que elegir entre las dos ciudades a $A$ $B$ en el antiguo itinerario, de tal manera que cada uno de ellos son visitado dos veces (denotado $AA$$BB$) en una fila. Nosotros, a continuación, insertar las visitas a $C$, de modo que tenemos $ACA$ $BCB$ en el nuevo itinerario. Desde allí se ${k+2\choose 2}$ formas de seleccionar dos ciudades fuera de los $k$ ciudades que se visitan dos veces en una fila en el antiguo itinerario, se obtiene el coeficiente de $T_{n-1}(k+2)$. Usted puede tratar de averiguar cómo el resto de coeficientes surgir.

Usando la relación de recurrencia, conseguí $T_6(0)=2631600$, lo cual está de acuerdo con Joriki la respuesta.