Categoría: 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 )(bulletbullet )stackrel{b_2}{cdots}(bulletbullet )(bullet bulletbullet )stackrel{b_3}{cdots}(bulletbulletbullet )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 sharpleft{begin{array}{c}mbox{Permutaciones de }S_n\ mbox{con }b_jmbox{ ciclos de longitud }jend{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 (sigmain 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

(displaystylefrac{D(n)}{n!}-frac{D(n-1)}{(n-1)!}=frac{(-1)^{n}}{n!}.)

Si ahora escribimos

(displaystylebegin{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 qquadqquad & vdotsquadvdots end{aligned})

sumando todas las igualdades tenemos

(displaystylefrac{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)=biggllangle frac{n!}{e}biggrrangle)

donde (langle x rangle) es el entero más próximo a (x).

Si ponemos (1/esimeq 0,367879ldots), 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)={nchoose 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)/esimeq 0,632130ldots) , 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