¿Cuántas formas hay de darse la mano?

en un grupo de 9 gente, cada persona se da la mano con exactamente 2 de las demás personas del grupo. Dejar X sea ​​el número de formas posibles de realizar estos apretones de manos. Llevar 2 patrones de apretón de manos (arreglos) distintos si y solo si como mínimo 2 las personas que se dan la mano bajo un patrón (acuerdo) no se dan la mano bajo el otro patrón (acuerdo). Encontrar X .

Creo que el trabajo de casos es el camino a seguir.

A batidos con B & C . D batidos con mi & F . GRAMO batidos con H & I .

Quizás podría usar una relación de recurrencia, pero no veo una forma posible.

En total hay:

( 9 3 ) ⋅ ( 6 3 ) ⋅ ( 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 incorrecta.

¡Solo sugerencias por favor!

No, no es un duplicado.
En tu ejemplo, B , C , mi , F , H y I darle la mano a una sola persona.

Respuestas (1)

Los apretones de manos se pueden modelar mediante un gráfico, desea encontrar el número de 2 -gráficos regulares en nueve vértices.

Es sabido 2 -Los gráficos 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 dos veces cada ciclo (una vez en cada orden).

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

Dos componentes conectados:

Tenemos que subdividir dependiendo de los tamaños de los dos componentes:

3 y 6 : primero elige los tres vértices en ( 9 3 ) maneras, después de la fórmula anterior nos da 2 ! 2 5 ! 2 Formas de formar los ciclos. entonces hay ( 9 3 ) 2 ! 2 5 ! 2 = 5 , 040 ciclos de este tipo.

4 y 5 : primero elige los cuatro vértices en ( 9 4 ) maneras, después de que la fórmula anterior nos da 3 ! 2 4 ! 2 Formas de formar los ciclos. entonces hay ( 9 4 ) 3 ! 2 4 ! 2 = 4 , 536

Tres componentes conectados:

Hay ( 9 3 , 3 , 3 ) maneras de dividir los nueve vértices en los tres grupos. Por supuesto, esto distingue a cada uno de los factores, por lo que, de hecho, la respuesta es ( 9 3 , 3 , 3 ) 1 3 ! = 280

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

buena respuesta. Pero: (1) ¿Qué quieres decir con "hacer un ciclo con k vértices?" (2) ¿Cómo dedujiste: ( k − 1 ) ! / 2 ?
bueno, si tienes k vetices 1 , 2 , 3 … k ¿De cuántas maneras podemos agregar aristas para que formen un ciclo? El ciclo más habitual sería conectar 1 con 2 y k y para conectar k con k − 1 y 1 . Y conectar cualquier otro número j con j − 1 y j + 1 . Este es uno de los ciclos posibles. Pero hay muchos otros ciclos. Puede describir un ciclo dando una lista que comience en 1 e incluye cada vértice 1 . Por ejemplo: 1 , 2 , 3 , 4 … k describe el ciclo que mencioné al principio. Cada ciclo se puede caracterizar con una lista como esa. Sin embargo, cada ciclo tiene dos listas.
Por ejemplo aviso 1 , 2 , 3 … k y 1 , k , k − 1 , k − 2 … 3 , 2 darnos el mismo ciclo. Puesto que hay ( k − 1 ) ! permutaciones de los elementos 2 , 3 , 4 , 5 … k y a cada dos de estas permutaciones le corresponde un ciclo, deducimos que hay ( k − 1 ) ! 2 ciclos en los elementos ( 1 , 2 , 3 , 4 , … k )
Más que una "pista" :-) pero creo que esta respuesta es la correcta.
Oh, lo siento por eso. Por alguna razón mi cerebro no analizó esa parte de la pregunta, me di cuenta ahora, debe ser el calor.
@dREaM, no hay problema, esta es una gran respuesta. Sólo un poco más de confusión. Por "ciclo", ¿quieres decir cuántas disposiciones de asientos son posibles? Además, ¿no hay permutaciones correctas? Pero para las permutaciones, ¿por qué dejaste fuera el 1 ? Dijiste "permutaciones de los elementos 2 , 3 , 4 , 5 , . . . , k y a cada dos de estas permutaciones...". ¿Por qué no es k ! / 2 en lugar de ( k − 1 ) ! / 2 ?
@dREaM, ¿por ciclo quieres decir cuántos apretones de manos son posibles? ¿O como el orden de disposición?
@Amad27, si colocas norte personas en un círculo (ciclo en los gráficos), puede cortar cada disposición en norte lugares (entre cada par de personas), y esto da como resultado un total de norte ! arreglos lineales, por lo que hay norte ! / norte = ( norte − 1 ) ! arreglos circulares. Pero en el apretón de manos no hay un orden de izquierda a derecha, por lo que ( norte − 1 ) ! / 2 .
@Amad27. alternativamente, tome el círculo de personas y comience con quien sea 1 yendo a la izquierda El siguiente es uno de norte − 1 otros, entonces norte − 2 , ..., para sólo 1 opción, eso es ( norte − 1 ) ! órdenes circulares, pero la misma secuencia de personas en una secuencia que va a la derecha es el mismo conjunto de apretones de manos, por lo tanto ( norte − 1 ) ! / 2 .
@vonbrand, entonces estás encontrando cuántos arreglos posibles, ¿verdad? ¿No es respectivo a la ubicación? ¿Porque estás arreglando un punto correcto?
@Amad27, sí.
¿Cuántas formas hay de darse la mano?
RespuestasAquíPolítica de privacidad1y, 0v