Primaria Combinatoria Pruebas con el grupo de acción

Question

En tratando de demostrar que el número de árboles de expansión en $K_5$ $125$ I adoptó el siguiente método:

Deje $S$ ser el conjunto de todos los árboles de expansión y deje $S_5$ actúan de una manera natural en $S$. Ahora, exactamente, tres nonisomorphic árboles de expansión $T_1=K_{1,4},T_2=P_5,T_3=\text{chair}$$\text{Stab}(T_i)=\text{Aut}(T_i)$.

Como $|\text{Orbit}(T_i)|=\frac{|S_5|}{|\text{Stab}(T_i)|}$ y $S$ es un discontinuo de la unión de las tres órbitas por lo tanto tenemos: $$|S|=\frac{5!}{4!}+\frac{5!}{2!}+\frac{5!}{2!}=125.$$

Este resultado puede ser obtenido puramente por el recuento de los argumentos, pero me parece que la anterior prueba más satisfactoria. ¿Cuáles son algunos otros elementales de conteo de pruebas en la combinatoria que puede ser interpretado en términos de la acción de grupo?

---

Aquí es otro ejemplo del tipo de resultados que estoy buscando:

El número de maneras de elegir a $k$ distintos objetos de $n$ donde el orden importa es $\frac{n!}{(n-k)!}$.

Prueba: Supongamos $G=S_n$$X=\cup_{m=1}^n \{(x_1,\ldots,x_m):x_i\ne x_j\text{ for }i\ne j, x_i\in[n]\}$. La función de $G\times X$ $X$definido por $\sigma\cdot (x_1,\ldots,x_m)=(\sigma(x_1),\ldots,\sigma(x_m))$ es claramente un grupo de acción.

Deje $x=(x_1,\ldots,x_k)\in X$. A continuación, $\mathcal{O}_x$ es, precisamente, la colección de todos los $k$-tuplas de $[n]$ donde cada coordenada es diferente. La prueba será terminado si se demuestra que $|\mathcal{O}_x|=\frac{n!}{(n-k)!}$. Tenga en cuenta que las permutaciones que arreglar $x$ y por lo tanto cada una de las $x_i$ son exactamente aquellos que permutar los elementos distintos, a continuación, $x_1,\ldots,x_k$ y tales permutaciones son, precisamente, $(n-k)!$ en número. Por lo $|G_x|=(n-k)!$. El resultado ahora sigue invocando la órbita estabilizador teorema.

Un resultado similar $\tbinom{n}{k}=\frac{n!}{k!(n-k)!}$ puede ser obtenida por dejar a $X$ a ser el conjunto de todos los $k$-subconjuntos de a $[n]$.

Answer 1

Este argumento es debido a Golomb.

Deje $p$ ser una de las primeras, y consideremos el conjunto de todas las secuencias de longitud $p$ con elementos tomados de a $\{1, 2, \dots, n\}$. Podemos ver $Z_p$ como actuar en estas secuencias rotación cíclica (por ejemplo, rotación de $12523$ $2$ rendimientos $23125$). Esta acción particiones de la $n^p$ secuencias de longitud $p$ en órbitas, incluyendo la $n$ órbitas de tamaño $1$ (las secuencias de la forma $aa\dots a$, los cuales son fijados por todas las rotaciones). El resto de las órbitas de todos tiene el tamaño de $p$ (desde $p$ es primo), y hay $\frac{n^p-n}{p}$ de ellos.

En particular, $\frac{n^p-n}{p}$ tiene que ser un número entero, dando de Fermat Poco Teorema.

Answer 2

Hay conteo de métodos de prueba para esto, pero aquí está el grupo de acción a prueba el uso de Burnside el Lema:

Supongamos que tenemos un $4\times4$ tablero de ajedrez con 16 plazas. Deje $S$ ser el conjunto de todos los colores con 8 negros y blancos 8 colores. ¿Cuántos colores hay?

Es obvio que hay $\binom{16}{8}=12870$ diferentes maneras para colorear de la junta. Para realizar esta interesante, en lugar de suponer que los colorantes son considerados de la misma si se asignan a cada uno de los otros mediante rotaciones y reflexiones.

Deje $G=\{ e,A,B,C,D,90^\circ,180^\circ,270^\circ\}$ el grupo de simetrías donde $A$ $B$ vertical y horizontal reflexiones, $C$ $D$ son diagonales de las reflexiones y de $90^\circ,180^\circ,270^\circ$ son las rotaciones. Entonces: $$|S^e|=\binom{16}{8}$$ $A$ $B$ reflejan mitades, de modo que: $$|S^A|=|S^B|=\binom{8}{4}$$ Desde $90^\circ$ $270^\circ$ proyecto para cada uno de los cuadrantes, obtenemos $$|S^{90^\circ}|=|S^{270^\circ}|=\binom{4}{2}$$ Del mismo modo, $180^\circ$ intercambios mitades: $$|S^{180^\circ}|=\binom{8}{4}$$ Para$C$$D$, 0, 2, o 4 cuadrados de color negro a lo largo de la diagonal. De lo contrario, llegaremos a una contradicción como un número impar de casillas negras deben ser divididos en partes iguales en dos mitades. Caso 1: No hay cuadros negros en la diagonal. Esto significa que hay 4 cuadrados de color negro de tomar hasta 6 plazas en cada mitad. Esto le da a $\binom{6}{4}$. Caso 2: 2 cuadrados de color negro en diagonal. En este caso, tenemos 6 plazas de izquierda, que se dividen en 3 por la mitad (de 6 plazas disponibles), así que tenemos $\binom{6}{3}$. Pero hay $\binom{4}{2}$ diferentes formas de organización de los cuadrados de color negro en la diagonal. Por lo tanto, para el Caso 2 tenemos $\binom{6}{3}\binom{4}{2}$. Para el Caso 3 (4 cuadrados de color negro en diagonal), cada lado tiene un total de 6 plazas y 2 cuadrados de color negro, que es $\binom{6}{2}$. La combinación de los casos, obtenemos: $$|S^C|=|S^D|=\binom{6}{4}+\binom{6}{3}\binom{4}{2}+\binom{6}{2}$$ La aplicación de Burnside del Lema, $$|S/G|=\frac{1}{|G|}\sum_{g\in G}|S^g|=\frac{1}{8}\left[\binom{16}{8}+3\binom{8}{4}+2\binom{4}{2}+ 2\left[\binom{6}{4}+\binom{6}{3}\binom{4}{2}+\binom{6}{2}\right] \right]$$$$=1674.$$

Answer 3

El alcance de las posibles respuestas a esta pregunta es realmente enorme. Yo sugieren que este MSE Meta Enlace como un punto de entrada para la exploración adicional.

Por medio de enriquecimiento me gustaría presentar otra prueba de que la elección de $q$ objetos de $m$ distintos objetos, donde el fin de que importaes $$\frac{m!}{(m-q)!}$$ el uso de la Polya Enumeración Teorema (PET). Creo que esta es una muy ejemplo donde podemos ver avanzados de mecánica de probar una muy simplecombinatoria declaración.

La utilización de PET tenemos que el número de opciones donde el orden importa es dada por $$q! \times \a la izquierda.Z(P_q)\left(\sum_{p=1}^m X_p\right) \right|_{X_1=X_2=\cdots=1}$$

donde $Z(P_q) = Z(A_q)-Z(S_q)$ es la diferencia entre el ciclo índice de la alternancia de grupo y el ciclo de índice de la clave grupo. Este ciclo de índice es conocido en la teoría de especies como el conjunto de operador $\mathfrak{P}_{=q}.$

Recordar la recurrencia por Lovasz para el ciclo de índice $Z(P_q)$ de el conjunto operador $\mathfrak{P}_{=q}$ $q$ ranuras, que es $A$Z(P_q) = \frac{1}{q} \sum_{i=1}^q (-1)^{l-1} a_l Z(P_{q-l}) \quad\text{donde}\quad Z(P_0) = 1.$$ Esta recurrencia nos permite calcular el ciclo de índice $Z(P_q)$ muy fácilmente. En particular, se puede utilizar para calcular la OGF de $Z(P_q)$ que es $$\sum_{q\ge 0} Z(P_q) z^q = \exp\left(a_1 z - a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} -\cdots\right).$$

Esto implica que $$\sum_{q\ge 0} Z(P_q)\left(\sum_{p=1}^m X_p\right) z^q \\ = \exp\left(z \sum_{p=1}^m X_p - \frac{z^2}{2} \sum_{p=1}^m X_p^2 + \frac{z^3}{3} \sum_{p=1}^m X_p^3 +\cdots\right).$$

y, en particular, $$\left.\sum_{q\ge 0} Z(P_q)\left(\sum_{p=1}^m X_p\right) z^q \right|_{X_1=X_2=\cdots =1} = \exp\left(m z - m \frac{z^2}{2} + m \frac{z^3}{3} - \cdots\right).$$

Esto es $$\exp\left(m\log(1+z)\right) = (1+z)^m.$$

Nota sin embargo de que $$q! \times [z^q] (1+z)^m = q! \times {m\elegir q} = \frac{m.}{(m-q)!}$$ lo que demuestra la demanda.

Elegí a propósito de este ejemplo es el contraste entre la sencillez de la que ha resultado probado y la complejidad de la maquinaria que se utiliza.