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.

Precalentamiento: vamos a contar permutaciones

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\).

Un desarreglo, dos desarreglos…

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

1. Primer caso: la imagen de \(i\) es precisamente \(1\). En este caso, si eliminamos tanto \(i\) como \(1\), para escribir el resto de la permutación lo que nos queda es precisamente elegir un desarreglo de \(i-2\) elementos. En otras palabras, tenemos \(D(n-2)\) posibles formas de terminar de escribir la permutación.
2. Segundo caso: la imagen de \(i\) no es \(1\). El truco ahora es el siguiente: Cada uno de los elementos \(2,\dots, n\) puede elegir libremente su imagen; salvo que cada elemento tiene una y sólo una restricción: el elemento \(2\) no puede ir al \(2\), el elemento\(3\) no puede ir al \(3\), …el elemento \(i\) no puede ir al \(1\), y el elemento \(n\) no puede ir al \(n\). Es otras palabras, resolver este problema es lo mismo que escribir un desarreglo de \(n-1\)elementos. Por tanto, hay \(D(n-1)\) formas de resolverlo.

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!}. \)

¿Análisis? Sí, gracias.

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.

Pequeños arreglos

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 al menos un elemento fijo

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

En la serie Futurama, el episodio 10 de la sexta temporada, El prisionero de Benda, es un poco especial. Tan especial, que merece la pena que hablemos de él en Álgebra Básica. Al fin y al cabo, no en muchas series aparecen teoremas originales, correctamente enunciados, y correctamente demostrados.

En este capítulo ocurren muchas cosas, pero el argumento esencial es que el Profesor Farnsworth y Amy construyen una máquina que les permite intercambiar sus mentes. Así, cada uno puede hacer cosas que no podría en su cuerpo original. (No haré más spoilers que éste.)

Por desgracia, la máquina no funciona dos veces sobre los mismos cuerpos. En términos de permutaciones (este sigue siendo el blog de Álgebra Básica, después de todo), si representamos el intercambio del profesor y Amy como una trasposición, tenemos que una vez que se usa la trasposición \((pa)\), ya no se puede volver a usar.

Naturalmente, como Futurama es Futurama, la cosa se desmadra bastante, y tras una muy complicada serie de acontecimientos, hay que deshacer cambios entre Amy, el Profesor Farnsworth, el Emperador Nikolai, Bender, el robot cubo de limpieza, Leela, Fry, Zoidberg, Hermes y Scrufy. ¿Cómo resolverlo?

En palabras del Profesor Farnsworth (hablando desde el cuerpo de Bender),

I’m afraid we need to use… math!
Profesor Farnsworth

El autor de este capítulo resulta ser Ken Keeler, casualmente un matemático doctorado por la Universidad de Harvard. Para reolver el capítulo, Keeler demostró el siguiente Teorema:

En el capítulo, \(x\) e \(y\) son dos personajes nuevos, dos globertrotters que demuestran el teorema y consiguen devolver cada mente a su cuerpo (o al revés, ya no me queda claro).

El teorema, y su demostración correcta y completa, aparece en una imagen del episodio:

Se puede seguir fácilmente la demostración escrita en la imagen, así que no haré más que un par de comentarios.

1. En primer lugar, como toda permutación se descompone en producto de ciclos disjuntos, basta demostrar el Teorema para un ciclo \(\pi\), que se puede escribir, sin pérdida de generalidad como
   $$
   \pi =\begin{pmatrix}
   1 & 2 & \dots &k &k+1 &\dots& n \\
   2 & 3 & \dots & 1 & k+1 &\dots &n
   \end{pmatrix}.
   $$
2. En la demostración, por comodidad se escribe el producto de permutaciones de izquierda a derecha, mientras que nosotros, en clase, usamos el producto de derecha a izquierda.

Me había planteado poner este teorema como ejercicio del primer parcial, pero en fin, me han convencido para que no lo haga, al menos este año.

¿Conocéis otros ejemplo de un teorema correctamente demostrado en una serie o película? No vale si están sólo enunciados…

---

Aquí tenéis un vídeo (en inglés) que comenta con bastante más detalle el capítulo y el enunciado del Teorema, aunque no cubre la demostración.

Hace unos días, comenté en clase de pasada que existe un teorema de clasificación de grupos finitos, y dije (de cabeza) que el teorema tiene aproximadamente 15.000 páginas. No era un error, pero quizá sea interesante dar algunos detalles adicionales.

Subgrupos normales… y de los otros.

En primer lugar, hace falta definir lo que es un subgrupo normal. Dado un grupo \((G,\star)\), se dice que \(H\subset G\) es un subgrupo si para todo elemento \(g\in G\) se verifica que \(g\star H=H\star g\). Obviamente, si el grupo \(G\) es conmutativo, todos sus subgrupos son normales. Pero eso no es necesariamente cierto si \(G\) no es conmutativo.

Ejercicio: Demuestre que \(H=\{(),(12)\}\) es un subgrupo NO normal de \(S_3\). Demuestre que el grupo alternado \(A_3\) sí es un subgrupo normal de \(S_3\).

[Indicaciones: para la primera parte, calcule \((123)H\neq H(123)\). Para la segunda, observe que \(\sigma A_3\) sólo puede ser, bien\(A_3\), bien el conjunto de todas las permutaciones impares.]

Subgrupos simples… y de los otros.

Un grupo se llama simple si no tiene subgrupos normales. Si un grupo no es simple, se puede “romper” en dos grupos más pequeños; un subgrupo normal y el grupo cociente. A su vez, cada uno de estos grupos se pueden “romper” en grupos más pequeños y así sucesivamente. Si \(G\) es un grupo finito, es claro que en algún momento llegaremos a expresar \(G\) en función de grupos simples. El resultado preciso es más complicado de enunciar, se llama Teorema de Jordan-Hölder.

El resumen de todo esto es que para clasificar los grupos finitos, basta clasificar los grupos finitos simples. Para saber más, puede empezar por la wikipedia, o por un artículo de Richard Elwes sobre el tema.

El mega-Teorema.

Pues bien, existe un Teorema de Clasificación de grupos simples finitos, distribuido a lo largo de 15.000 páginas, que dice, esencialmente, que un grupo finito simple es isomorfo a uno de los siguientes tipos¹:

1. Grupos cíclicos de orden primo.
2. Grupos alternados \(A_n\), con \(n\geq 5\).
3. Grupos (de tipo Lie) de Chevalley
4. Otros grupos (de tipo Lie): grupos de Chevalley torcidos (twisted) o grupo de Tits.
5. Grupos esporádicos. Aquí aparecen 26 grupos “inclasificables”. Entre éstos, encontramos nombres tan curiosos como baby monster, monster, los grupos parias, etc.

El grupo monster se llama así no por la bebida energética, sino porque es el grupo simple finito más grande. Además, contiene 20 de los 26 grupos esporádicos como subcocientes. Los seis que no están contenidos son los “parias”. El grupo monster es finito, pero poco: tiene orden

\(808017424794512875886459904961710757005754368000000000.\)

¡Sí que da miedo el monster!