Contar el número de agrupaciones mediante acciones de grupo

Sí, y de hecho vamos a generalizar a desordenado$k$-tuplas. Escribir$[n]$para el conjunto$\{ 1, 2, \dots n \}$. El conjunto de pedidos$k$-tuplas es el conjunto$[n]^{[k]}$de funciones$[k] \to [n]$. Este conjunto tiene una acción natural del grupo simétrico.$S_k = \text{Aut}([k])$, y el conjunto de desordenados$k$-tuplas es el conjunto de órbitas bajo esta acción.

Podemos contar el número de órbitas usando el lema de Burnside de la siguiente manera. una permutación$\pi \in S_k$corrige una función función$f : [k] \to [n]$iff es constante en cada uno de los ciclos de$\pi$. De ello se deduce que el número de tales funciones fijado por$\pi$es$|\text{Fix}(\pi)| = n^{c(\pi)}$dónde$c(\pi)$denota el número total de ciclos y, por lo tanto, el lema de Burnside da que el número de ciclos no ordenados$k$-tuplas es

Cuando$k = 2$esto da

ya que en este caso solo hay dos permutaciones en$S_2$, con$1$y$2$ciclos respectivamente. Cuando$n = 3$esto da

ya que en este caso hay seis permutaciones en$S_3$, la identidad tiene$3$ciclos, las tres transposiciones tienen$2$ciclos, y los dos$3$-los ciclos tienen$1$ciclo. En general esto da

dónde$s(k, i)$denota los números de Stirling (sin signo) del primer tipo , que cuentan el número de permutaciones en$S_k$teniendo$i$ciclos No es del todo obvio a primera vista que esta suma debería simplificarse a${n+k-1 \choose k}$, pero esto se puede probar de varias maneras diferentes, por ejemplo, estableciendo una recursividad apropiada para los números de Stirling.