De cara al próximo examen de la asignatura, acabamos de subir a este blog y a la plataforma de enseñanza virtual una autoevaluación de los temas 1 y 2.
Además hemos colgado las soluciones a los ejercicios 19 y 35 de la relación de problemas del tema 1 de conjuntos.
Se acaba de publicar la solución a la autoevaluación del tema 2.
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?
Hace justo un año se publicó esta entrada, que volvemos a traer para los nuevos alumnos de la asignatura.
Los ejercicios 19, 20 y 21 de la relación de Álgebra Básica hacen varias preguntas sobre contar permutaciones con ciertas propiedades: las que no tienen elementos fijos (esto es, \(\sigma(i)\neq i\) para todo \(i\)), las que tienen al menos un elemento fijo, etc. Aquí nos centraremos en los desarreglos. Una permutación \(\sigma\in S_n\) se llama un desarreglo si \(\sigma(i)\neq i\) para todo \(i=1,\dots,n\).
Contar las permutaciones sin elementos fijos, además de ser una muestra de inestabilidad mental, puede tener su importancia en la seguridad de criptosistemas basados en permutaciones. (Por cierto, ahora que caigo, Teoría de códigos y criptografía es una asignatura optativa de tercero de vuestro departamento favorito.)
Por si no me da tiempo a ver todo en clase (que no dará), os pongo aquí algunas curiosidades sobre el tema.
Supongamos que tenemos el conjunto \(\{1,\dots,n\}\). Para contar las posibles permutaciones, empecemos fijando la imagen de \(1\), que llamamos será un cierto \(i\):
\(\displaystyle \left(\begin{array}{cccccccc}1 & 2 & 3 & 4 & 5 \cdots & n\\ i & \cdots \end{array}\right) .\)
Evidentemente, podemos tomar \(i\) entre los \(n\) posibles valores, sin restricción ninguna. Pero entonces, nos queda por asignar la imagen de los \(n-1\) siguientes enteros, entre \(n-1\) posibles valores. De forma que, llamando \(P(n)\) al número de permutaciones de \(n\) elementos, se tiene la relación de recurrencia
\(P(n)=nP(n-1),\qquad P(1)=1. \)
Ahora es posible usar inducción para demostrar que\(P(n)=n!\), como sabemos. Por motivos en los que no quiero entrar ahora, conviene definir \(P(0)=0!=1\).
Vamos ahora al Ejercicio 21. ¿Cuántos desarreglos hay? Podemos intentar contarlos de forma similar al método recurrente que hemos usado para contar permutaciones: elegimos la imagen de \(1\), que llamamos \(i\) entre las \(n-1\) posibilidades que tenemos:
\(\displaystyle \left(\begin{array}{cccccccc}1 & 2 & 3 & 4 & 5 \cdots & n\\ i & \cdots \end{array}\right) .\)
Repito porque es importante: hay que escoger \(i\) entre los \(n-1\)valores aceptables (no puede ser \(1\)). En otras palabras, llamando\(D(n)\) al número de desarreglos de \(n\) elementos, sabemos que
\(D(n)=(n-1)[\text{algo}].\)
El algo es un poco más complicado que calcular que antes; pero básicamente tenemos dos casos
Así que podemos terminar de escribir la fórmula de antes como
\(\displaystyle D(n)=(n-1)\bigl[D(n-1)+D(n-2)\bigr], \)
donde \(D(1)=0\) y \(D(2)=1\). Igual que antes, conviene poner \(D(0)=1\).
Esto sería suficiente para dar por bueno el ejercicio, pero ¿podemos decir algo más acerca de \(D(n)\)? ¿Podemos dar una fórmula para \(D(n)\)? Pues resulta que sí. (Véase este enlace)
Recordemos que tenemos la relación
\(\displaystyle D(n)=(n-1)\bigl[D(n-1)+D(n-2)\bigr]. \)
Restando \(nD(n-1)\) a ambos lados de la igualdad,
\(\displaystyle D(n)-nD(n-1)=-\bigl[D(n-1)-(n-1)D(n-2)\bigr]. \)
Ahora bien, es inmediato probar que
\(D(n)-nD(n-1)=(-1)^{n}.\)
[Es realmente inmediato: poniendo \(Z(n)=D(n)-nD(n-1)\), obtenemos una relación de recurrencia \(Z(n)=-Z(n-1)\), con \(Z(0)=1\).]
Si dividimos por \(n!\), tenemos
\(\displaystyle\frac{D(n)}{n!}-\frac{D(n-1)}{(n-1)!}=\frac{(-1)^{n}}{n!}.\)
Si ahora escribimos
\(\displaystyle\begin{aligned} \frac{D(n)}{n!}-\frac{D(n-1)}{(n-1)!}&=\frac{(-1)^{n}}{n!}\\ \frac{D(n-1)}{(n-1)!}-\frac{D(n-2)}{(n-2)!}&=\frac{(-1)^{n-1}}{(n-1)!}\\ \frac{D(n-2)}{(n-2)!}-\frac{D(n-3)}{(n-3)!}&=\frac{(-1)^{n-2}}{(n-2)!}\\ \vdots \qquad\qquad & \vdots\quad\vdots \end{aligned}\)
sumando todas las igualdades tenemos
\(\displaystyle\frac{D(n)}{n!}=\sum_{k=0}^{n} \frac{(-1)^{k}}{k!},\)
luego
\(\displaystyle D(n)=n!\sum_{k=0}^{n} \frac{(-1)^{k}}{k!}. \)
Acabamos de obtener
\(\displaystyle D(n)=n!\sum_{k=0}^{n} \frac{(-1)^{k}}{k!}.\)
Pero si miramos con atención esta igualdad, vemos que se parece a la serie de Taylor de \(e^{x}\) con \(x=-1\),
\(\displaystyle e^{x}=\sum_{k=0}^{\infty} \frac{x^{k}}{k!},\)
de modo que
\(\displaystyle D(n)\simeq \frac{n!}{e},\)
lo que me parece un resultado alucinante. No sólo eso, sino que el error que se comete al aproximar \(D(n)\) por \(n!/e\) es menor que \(1/(n+1)\) (por ser una serie alternada), de forma que
\(\displaystyle D(n)=\biggl\langle \frac{n!}{e}\biggr\rangle\)
donde \(\langle x \rangle\) es el entero más próximo a \(x\).
Si ponemos \(1/e\simeq 0,367879\ldots\), obtenemos que el 36,78% de las permutaciones son desarreglos.
Vamos a cambiar de problema, vamos a contar las permutaciones que dejan fijos exactamente \(k\) elementos. Claro, esto podemos plantearlo de la siguiente forma: dejar fijo \(k\) elementos, es lo mismo que tachar \(k\) elementos entre los \(n\) que tenemos, y formar un desarreglo con los \(n-k\) restantes. Denotemos por \(S(n,k)\) el número de permutaciones que dejan fijo exactamente \(k\) elementos, se tiene que
\(\displaystyle S(n,k)={n\choose k} D(n-k),\)
y sustituyendo el valor de \(D(n-k)\) que hemos encontrado antes, tenemos
\(\displaystyle S(n,k)=\frac{n!}{k!}\sum_{j=0}^{n-k}\frac{(-1)^{j}}{j!}. \)
Con todo lo que sabemos, podemos contestar rápidamente el Ejercicio 19: ¿cuántas permutaciones hay con al menos un elemento fijo? Pues tantas como permutaciones que no sean desarreglos. Llamando \(F(x)\) al número de permutaciones con al menos un punto fijo,
\(\displaystyle F(n)=n!-D(n)=n!-n!\sum_{k=0}^{n} \frac{(-1)^{k}}{k!}=n!\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!}.\)
Para hacer una estimación grosera, podemos poner
\(\displaystyle F(n)\simeq n!-\frac{n!}{e}=n!(1-1/e)=n!(e-1)/e.\)
Sabiendo que \((e-1)/e\simeq 0,632130\ldots\) , obtenemos que, aproximadamente, el 63,21% de las permutaciones tiene al menos un elemento invariante (con un error bastante pequeño).
Para saber más, puede consultarse Mathworld, o directamente el artículo Hassani, M. “Derangements and Applications.” J. Integer Seq. 6, No. 03.1.2, 1-8, 2003
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.
Se acaba de subir a este blog (y a la plataforma de enseñanza virtual) la presentación que uso en mis clases para la explicación del tema 2. Está en la página MATERIAL DE LA ASIGNATURA CURSO 15/16.
Además se han modificado las notas de teoría del tema 2. Concretamente se han corregido las permutaciones que intervienen en la explicación del juego inicial (página 58 y siguientes), que estaban mal, y la del ejemplo 2.3.15. Además se ha añadido una observación tras la fórmula de Cauchy en la página 63, la nota 2.3.19.
Se acaba de subir a este blog la relación de ejercicios propuesta para el tema 2.
Acabo de subir a la red las notas de teoría correspondientes al Tema 2: Introducción a la teoría de grupos.
Se han publicado en la página Material de la Asignatura los enunciados de la primera prueba en todos los grupos.
Hay que reconocer que se nos ha ido un poco la mano con la autoevaluación del tema 2. Hay algún ejercicio difícil y, sobre todo, es demasiado larga. Acabamos de subir a Material de la Asignatura la solución, para que se pueda contrastar qué se ha hecho bien y cómo se hace aquello que no se ha sabido hacer.