Siguiendo con los ejercicios de contar permutaciones, volvemos a traer esta entrada de hace un año que puede ser de ayuda para resolver el ejercicio 14 de la relación de problemas de grupos de Álgebra Básica.
Tras la entrada anterior, en la que contábamos los desarreglos, es decir, las permutaciones de \(S_n\) que “mueven” todos los elementos, vamos a exponer una fórmula de Cauchy que cuenta todas las permutaciones que tienen una distribución de ciclos determinados.
Es decir, el problema es contar todas las permutaciones de \(S_n\) que en su descomposición de ciclos disjuntos tienen exactamente \(b_j\) ciclos de longitud \(j\).
Atención: En esta entrada vamos a considerar los ciclos de longitud 1, aunque todos ellos sean iguales a la identidad.
Es decir, queremos conocer la cantidad de permutaciones que, en su descomposición de ciclos disjuntos, se escriben como producto de \(b_2\) trasposiciones, \(b_3\) ciclos de longitud 3, …, \(b_n\) ciclos de longitud \(n\) y \(b_1\) ciclos de longitud 1, que coincide con la cantidad de elementos que “no se mueven”.
Desde luego, tenemos una importante restricción entre los \(b_j\), pues se trata de ciclos disjuntos:
\(b_1+2b_2+3b_3+\cdots +nb_n=n.\)
Como queremos contar las permutaciones que tienen la siguiente distribución de ciclos
\(\displaystyle (\bullet )\stackrel{b_1}{\cdots}(\bullet )(\bullet\bullet )\stackrel{b_2}{\cdots}(\bullet\bullet )(\bullet \bullet\bullet )\stackrel{b_3}{\cdots}(\bullet\bullet\bullet )\cdots\)
podemos considerar que hemos repartido el espacio en el que tienen que ir los \(n\) números en \(b_j\) compartimentos de longitud \(j\). En principio los \(n\) números “caen” sobre estos huecos de cualquier manera, lo que da \(n!\) posibilidades. Pero hay que quitar las repeticiones, es decir, aquellas que representan a la misma permutación.
Por ejemplo, si estoy contando las permutaciones de \(S_9\) que tienen tres ciclos de longitud 2 y uno de longitud 3, obtendré la permutación
\((13)(48)(59)(267)\)
y también
\((31)(48)(95)(672),\)
que en realidad son la misma permutación. Es decir, hay que quitar aquellas representaciones iguales del mismo ciclo. Cada ciclo de longitud \(j\) se escribe de \(j\) maneras distintas, luego los \(b_j\) ciclos de longitud \(j\) aparecen \(j^{b_j}\) veces.
Así, cada permutación se repite
\(1^{b_1}2^{b_2}\cdots n^{b_n}.\)
¿Es correcto? Me temo que no, pues no hemos tenido en cuenta que los ciclos disjuntos conmutan. Es decir, la permutación
\((48)(59)(13)(267)\)
es igual a las anteriores, luego hay más repeticiones que tenemos que descontar. Estas repeticiones consisten en permutar entre sí los \(b_j\) ciclos de longitud \(j\). Esto puede hacerse \(b_j!\) veces, luego (ahora sí) cada permutación se repite
\(1^{b_1}2^{b_2}\cdots n^{b_n}b_1!b_2!\cdots b_n!\)
veces. Obteniendo la fórmula que queríamos
\(\displaystyle \sharp\left\{\begin{array}{c}\mbox{Permutaciones de }S_n\\ \mbox{con }b_j\mbox{ ciclos de longitud }j\end{array}\right\} = \frac{n!}{1^{b_1}2^{b_2}\cdots n^{b_n}b_1!b_2!\cdots b_n!}.\)
Ahora te animo a que apliques esta fórmula al Ejercicio 14 de la relación, que consiste en contar las permutaciones que son producto de trasposiciones disjuntas (ver Ejercicio 13).
¿Te atreves a decir cuántas permutaciones de \(S_n\) son producto de una trasposición? ¿Y de dos trasposiciones? ¿Y de tres? ¿Y de \(b_2\) trasposiciones?