Combinación en simetría
Supongamos que tenemos los seis vértices idénticos conectados con dos líneas diferentes de color verde y negro.
Quiero contar cuántas formas únicas podemos hacer una partición en este sistema. Por ejemplo, si quiero hacer particiones 1x5,
La forma más fácil en la que podemos pensar es 6C1 = 6 casos. Sin embargo, el sistema tiene simetría rotacional con un ángulo de 60 grados. Entonces solo tendremos 2 particiones únicas. Si ignoramos aún más el orden del color, solo tenemos una partición única . La partición solo puede contener una verde y una negra.
Para particiones de 3x3, se vuelve un poco más complicado. Primero, podemos encontrar que hay un total de 6C3 = 20 particiones que existen. Una vez que nos deshagamos del doble conteo, solo tenemos 10 casos.
Sin embargo, debemos tener en cuenta la simetría. Sé la respuesta haciéndolo a mano, solo tenemos 4 casos únicos. tenemos (1 (3 verdes y 3 negros) +3 (Verde + Negro) +3 (3 negros y uno verde) +3 (3 verdes y uno negro).
Usando esta regla, pude contar las soluciones únicas de la siguiente manera
(4 elige 1) tenemos 1 caso único
(4 elige 2) tenemos 3 casos únicos
(6 elige 1) tenemos 1 caso único
(6 elija 2) tenemos 4 casos únicos
(6 elige 3) tenemos 4 casos únicos
¿Hay alguna forma de encontrar la solución de combinación generalizada con la simetría del sistema?
Respuestas
Estás preguntando por el número de particiones de un conjunto (aquí, un hexágono) que son diferentes con respecto a algunas simetrías (en este caso, simetría rotacional). En general, esta es una cuestión importante y bien estudiada en matemáticas. Es genial que hayas encontrado este material al estudiar este ejemplo en profundidad.
La forma muy general de resolver este problema es usar algo llamado lema de Burnside . Si desea obtener más información, debe buscar un libro de texto sobre teoría de grupos.
Para resolver este ejemplo específico de forma sistemática , podemos utilizar las ideas del lema de Burnside sin necesidad explícita de los antecedentes de la teoría de grupos. Por ejemplo, reformulemos su prueba de que hay$4$ particiones distintas del hexágono en dos conjuntos de tres puntos cada uno.
Usted señaló correctamente que hay $\binom{6}{3} = 20$ posibles subconjuntos de tamaño $3$, entonces hay $\binom{6}{3} / 2 = 10$posibles particiones. Para una partición$P$, dejar $f(P)$ denotar el número de formas de diferentes copias rotadas de $P$.
Por ejemplo, en su imagen (copiada a continuación), deje $P$ ser la partición superior izquierda y $P'$ser la partición superior derecha. Luego$f(P) = 3$ y $f(P') = 1$.
Considere la lista de todos $10$ particiones $P_1, \dots, P_{10}$. Cada partición$P$, está "sobrecontado" exactamente $f(P)$veces. Para que cada partición que sea diferente con respecto a la rotación se cuente una vez, hacemos el siguiente truco. Consideramos la suma
$$ \sum_{i=1}^{10} \frac{1}{f(P_i)} .$$
En el caso en el que buscamos particiones del hexágono en dos conjuntos de tamaño tres, esto se convierte en la suma
$$ \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + 1 = 4,$$
que es exactamente lo que contaste!
Esta fórmula también funciona para el caso en el que dividimos el hexágono en un conjunto de tamaños $1$ y un conjunto de tamaño $5$. Hay, hay$6$ particiones totales, y para cada partición tenemos $f(P) = 6$(porque cada partición es una rotación de las demás). Entonces la suma es
$$ \sum_{i=1}^6 \frac{1}{f(P)} = \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = 1.$$
Pruebe esta fórmula en otros casos si no sabe cómo funciona. También funciona si reemplaza el hexágono por otro diferente.$n$-gon, por ejemplo. La parte difícil se vuelve calcular$f(P)$ para cada partición $P$(y enumerando todas las particiones posibles). Espero que esto responda tu pregunta.