Entrada publicada en el blog de Álgebra Básica
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
- 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.
- 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