Todas las entradas de: miguelolalla

Relación de ejercicios del tema 3

Acabamos de subir a este blog la relación de ejercicios del tema 3.

Se ha dividido en dos partes. En la primera parte hemos seleccionado unos ejercicios que permitirán trabajar y reforzar lo que se ha explicado en las clases teóricas. La segunda parte es una relación complementaria con ejercicios que repiten técnicas ya trabajadas en la teoría y en la otra parte, que son algo más difíciles o que se han preguntado en los últimos exámenes.

Contando permutaciones

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?

Corrección en los apuntes del tema 2

Se han corregido los apuntes del tema 2. Concretamente se ha eliminado el siguiente ejercicio que se había propuesto con cierta ligereza:

Este resultado se puede extender a grupos finitos en general. Si \((G,\star )\) es un grupo finito que tiene algún elemento de orden impar, entonces tiene tantos elementos de orden par como impar.

Lo que propone el ejercicio es falso. Invitamos al lector a buscar un ejemplo de grupo que tenga todos sus elementos de orden impar.

El ejercicio eliminado estaba en la página 67 de los apuntes y aparecía etiquetado como “Ejercicio 2.4.6”.

Lo que sí es cierto, tras demostrar el Teorema de Cayley, es que en cada grupo finito, al ser isomorfo a un subgrupo de \(S_n\), debe existir una clasificación análoga a la del signo en las permutaciones. Pero esta clasificación no es la paridad del orden de los elementos.