Calcula de cuántas maneras puedes pintar las esquinas de un Pentágono

Question

Estoy estudiando para un examen que tengo sobre combinatoria la semana que viene y estoy atascado con la solución a esta pregunta:

Imagina que tienes un pentágono y quieres colorear las esquinas del pentágono para que no haya dos esquinas adyacentes del mismo color. Si tienes colores "q", ¿cuántas formas de colorear el pentágono son posibles?

Yo digo que la respuesta es $q^2*(q-1)^2*(q-2) + q*(q-1)*(q-2)^2*(q-3)$ .

Mi amigo dice que la respuesta es $MyAnswer + q*(q-1)*(q-2)*(q-3)*(q-4)$ .

¿Quién tiene razón? (o ambos estamos equivocados).

Además, si pudieras señalar un recurso que explique cómo calcular esta pregunta para otros números de esquinas (digamos un hexágono) lo apreciaríamos mucho.

EDITAR:

Respondiendo a algunos comentarios de la respuesta, las rotaciones del pentágono no deben ser contadas. Lo que quiero decir es que si tenemos 5 colores (a,b,c,d,e) el pentágono con las esquinas {(1,a),(2,b),(3,c),(4,d),(5,e)} es exactamente igual que {(1,c),(2,d),(3,e),(4,a),(5,b)}

Answer 1

Aquí voy a asumir que no estamos buscando configuraciones distintas, es decir, contamos con una rotación o reflejo del pentágono como una posibilidad distinta.

Ambos tienen términos incorrectos. Consideren tener sólo $3$ colores, es decir $q = 3$ . En esta condición debe haber un vértice que se encuentra entre dos puntos que tienen el mismo color. Hay $3 \times 2 = 6$ formas de colorear estos tres puntos, dejando $2$ formas de colorear los dos puntos restantes para un total de $12$ posibilidades. Pero $3^2 \times 2^2 \times 1 + 0 + (0) = 36$ que es demasiado.

Pista: Si estás coloreando un pentágono, hay tres casos posibles:

1. El pentágono puede ser coloreado con $k = 5$ los distintos colores elegidos de la $q$ posibilidades.

2. El pentágono puede ser coloreado con $k = 4$ colores distintos y una repetición.

3. El pentágono puede ser coloreado con $k = 3$ colores distintos donde dos colores aparecen dos veces. (También tenemos que un color podría aparecer tres veces, pero entonces sería imposible colorear un pentágono sin que el mismo color sea adyacente.)

Es fácil ver que es imposible colorear los vértices de un pentágono con sólo 2 colores de tal manera que el mismo color no sea adyacente en ninguna parte.

En tu pregunta, tu amigo está dando cuenta de la $q(q-1)(q-2)(q-3)(q-4)$ formas de colorear un pentágono usando $5$ colores distintos. Para encontrar la solución final, necesitamos contar cuántas formas podemos colorear un pentágono en cada uno de los casos dados y luego sumar todas las posibilidades.

Ahora, para cada uno de los tres casos, $q$ elige $k$ para fijar los elementos k con los que estás trabajando, entonces considera cuántas formas puedes colorear un pentágono usando esos $k$ colores.

Cualquier otra ayuda se dirigirá hacia una solución directa, así que creo que debo detenerme aquí.

Answer 2

Necesitas especificar mejor el problema. ¿Cuentas las rotaciones y los reflejos como diferentes? Por ejemplo, imagina un pentágono normal dibujado en una hoja de papel con una esquina hacia arriba. Empezando por la esquina superior y yendo en el sentido de las agujas del reloj, tal vez tenemos 0,1,2,3,4 (usando números en lugar de colores). ¿Esto es diferente del 1,2,3,4,0? ¿Qué tal del 0,4,3,2,1?

La situación más fácil es si dices que todos estos son diferentes. Entonces el enfoque ingenuo sería decir que tienes $q$ opciones para la esquina superior, $q-1$ opciones para cada una de las próximas tres esquinas (ya que no puedes tener esquinas vecinas que coincidan) y $q-2$ opciones para el último, dando $q*(q-1)^3*(q-2)$ pero esto ignora el hecho de que la primera y la cuarta curva podrían ser del mismo color, dando $q-1$ opciones para el último.

Una forma de tratar esta situación es separarse en clases basadas en qué esquinas coinciden con la de arriba. Si designamos la esquina superior 0 y contamos en el sentido de las agujas del reloj, se puede hacer coincidir el color de la parte superior sólo en ninguna esquina, esquina 2 o esquina 3. Así que no coincidiendo con ninguna, tenemos $q*(q-1)*(q-2)^3 $ ya que en la esquina 1 puedes usar cualquier color menos el de la esquina 0, pero para cada uno de ellos tienes dos eliminados. En la esquina 2, tenemos $q*(q-1)*1*(q-1)*(q-2)$ y en la esquina 3 que tenemos $q*(q-1)*(q-1)*1*(q-2)$ . Súmalos todos y tendrás tu respuesta.

En general, la respuesta tiene que ser un polinomio de quinto grado. Para los grandes $q$ la restricción de no coincidir los colores no reducirá mucho la cuenta. Así que si cuentas las soluciones para seis q diferentes (sugiero de 0 a 5), puedes encajar un polinomio de quinto grado a través de ellas.

Si se quieren contar las rotaciones y los reflejos como iguales, hay dos posibilidades. Una posibilidad es definir una posición estándar y contar sólo los casos en posición estándar. En este caso es fácil. Se diría que el número más pequeño tiene que estar en la parte superior, y que la esquina 2 es menor que la 3. Un error sería decir que el número más pequeño está arriba y que la esquina 1 es menor que la 4. Podría ser que la esquina 1 y la 4 sean iguales, y podría ser que una de las esquinas 2 y 3 sea igual a la esquina 0. Pero contar cuántas configuraciones satisfacen esta restricción puede no ser fácil. Es de nuevo un polinomio de quinto grado. El otro caso es enumerar las configuraciones de las esquinas que coinciden y ver cuántas veces se cuentan cada una de ellas. Así que si ninguna esquina coincide, hay $q*(q-1)*(q-2)*(q-3)*(q-4)$ pero has contado cada una 10 veces, así que divídelas entre 10. Entonces puedes tener un par o dos pares de esquinas que coincidan. Estas son probablemente más fáciles de contar por el enfoque de la posición estándar. Si un par coincide, digamos que tienen que ser las posiciones 0 y 2. Así que tenemos $q*(q-1)*1*(q-1)*(q-2)$ opciones para esto. Y así sucesivamente.

Perdón por quitar los asteriscos de mis expresiones, pero se puso en cursiva y se atropelló cuando estaban allí. Creo que lo hicieron más fácil de leer.