¿Cuántas formas hay de dar la mano?

Question

En un grupo de $9$ personas, cada persona estrecha la mano con exactamente $2$ de las otras personas del grupo. Deja que $X$ sea el número de formas posibles de realizar estos apretones de manos. Toma $2$ patrones de apretón de manos (arreglos) distintos si y sólo si al menos $2$ las personas que se dan la mano bajo un patrón (arreglo) no se dan la mano bajo el otro patrón (arreglo). Encontrar $X$ .

Creo que el trabajo en caja es el camino a seguir.

$A$ batidos con $B$ & $C$ . $D$ batidos con $E$ & $F$ . $G$ batidos con $H$ & $I$ .

Tal vez podría utilizar una relación de recurrencia, pero no veo una forma posible.

En total hay:

$$\binom{9}{3} \cdot \binom{6}{3} \cdot \binom{3}{3} = 1680$$

Formas de elegir grupos de tres personas.

Pero no hago nada más a este problema, y claramente esta es la respuesta equivocada.

Sólo sugerencias, por favor.

Answer 1

Los apretones de manos pueden ser modelados por un gráfico, se quiere encontrar el número de $2$ -grafos regulares sobre nueve vértices.

Se sabe que $2$ -Los grafos regulares tienen ciclos como componentes conectados.

Hay tres opciones para el número de componentes conectados:

Un componente conectado:

En este caso el gráfico es un ciclo en $9$ vértices, el ciclo puede verse como una permutación que comienza con $1$ enumerando los vértices en orden. Hay $8!$ tales permutaciones, pero nos dan cada ciclo dos veces (una en cada orden).

Por lo tanto, hay $\frac{8!}{2}=20,160$ tales ciclos. Será bueno tomar nota de la siguiente fórmula: hay $\frac{(k-1)!}{2}$ formas de hacer un ciclo con $k$ vértices.

Dos componentes conectados:

Tenemos que subdividir en función de los tamaños de los dos componentes:

$3$ y $6$ : primero elige los tres vértices en $\binom{9}{3}$ formas, después de la fórmula anterior nos da $\frac{2!}{2}\frac{5!}{2}$ formas de formar los ciclos. Así que hay $\binom{9}{3}\frac{2!}{2}\frac{5!}{2}=5,040$ ciclos de este tipo.

$4$ y $5$ : primero elige los cuatro vértices en $\binom{9}{4}$ formas, después de la fórmula anterior nos da $\frac{3!}{2}\frac{6!}{2}$ formas de formar los ciclos. Así que hay $\binom{9}{4}\frac{3!}{2}\frac{4!}{2}=4,536$

Tres componentes conectados:

Hay $\binom{9}{3,3,3}$ formas de dividir los nueve vértices en los tres grupos. Por supuesto, esto distingue cada uno de los factores, por lo que de hecho la respuesta es $\binom{9}{3,3,3}\frac{1}{3!}=280$

Así que la respuesta final es $20,160+5,040+4,536+280=30,016$