A bit of math…

Just another WordPress.com site

Permutaciones sin puntos fijos; un resultado/ejercicio sorprendente

En este post, vamos a calcular la cantidad de elementos del grupo simétrico en n letras S_n que no tienen puntos fijos. Con este número, calcularemos la probabilidad de que una permutación en S_n no tenga puntos fijos, y encontraremos el límite asintótico cuando n\to\infty. El resultado es elegante y sorprendente.

Meta 1:

Queremos contar la cantidad de elementos que tiene el conjunto

P_n=\{\sigma\in S_n:\sigma(x)\neq x\mbox{ para todo }x\in\{1,\ldots,n\}\}.

Procedimiento:

Consideremos el grupo \{\sigma\in S_n:\sigma(1)=1\}\leq S_n. Notamos que este grupo es isomorfo a S_{n-1}, y lo denotaremos (por el momento) como S_{n-1}(1). De hecho, para todo x\in\{1,\ldots,n\} y para cualquier \eta\in S_n tal que \eta(1)=x, el subgrupo S_{n-1}(x)=\{\sigma\in S_n:\sigma(x)=x\} es isomorfo a S_{n-1}S_{n-1}(x)=\eta S_{n-1}(1)\eta^{-1}.

Dejaremos la notación S_{n-1}(1), y denotaremos este subgrupo simplemente por S_{n-1}.

Notamos que S_{n-1} tiene precisamente n conjugados, ya que \sigma S_{n-1}\sigma^{-1} depende solamente de \sigma(1), y hay n posibles valores para este número. Otra forma de ver el mismo hecho es que el normalizador de S_{n-1} en S_n es S_{n-1}, y luego la cantidad de conjugados de S_{n-1} es igual a [S_n:N(S_{n-1})]=[S_n:S_{n-1}]=n.

Observamos que P_n=S_n\backslash\left(\bigcup_{\sigma\in S_n}\sigma S_{n-1}\sigma^{-1}\right), y entonces para calcular la cardinalidad de P_n, basta calcular la cardinalidad de \bigcup_{\sigma\in S_n}\sigma S_{n-1}\sigma^{-1}.

Podemos ver que para todo x,y\in\{1,\ldots,n\} distintos, se tiene que S_{n-1}(x)\cap S_{n-1}(y) es igual al conjunto de todos los elementos en S_{n-1}(x) que fijan y, y luego es isomorfo a S_{n-2}. Siguiendo la misma lógica, vemos que la intersección de k de estos subgrupos es isomorfo a S_{n-k}, y luego tiene cardinalidad (n-k)!.

Recordemos ahora el Principio de Inclusión-Exclusión, que dice que si A_1,\ldots,A_n son conjuntos, entonces

\left|\bigcup_{i=1}^nA_i\right|=\sum_{k=1}^n\sum_{1\leq i_1<i_2<\cdots<i_k\leq n}(-1)^{k-1}\left|\bigcap_{i=1}^kA_i\right|.

Así, si \sigma_i\in S_n es tal que \sigma_i(1)=i, tenemos que

|S_n\backslash P_n|=\left|\bigcup_{i=1}^n\sigma_iS_{n-1}\sigma_i^{-1}\right|=\sum_{k=1}^n\sum_{1\leq i_1<i_2<\cdots<i_k\leq n}(-1)^{k-1}\left|\bigcap_{i=1}^k\sigma_iS_{n-1}\sigma_i^{-1}\right|

La gracia de esta fórmula en el contexto en el cual estamos trabajando nosotros es que ya conocemos las cardinalidades de todas las intersecciones (por lo que dijimos anteriormente).

Entonces

\left|\bigcup_{i=1}^n\sigma_iS_{n-1}\sigma_i^{-1}\right|=\sum_{k=1}^n\sum_{1\leq i_1<i_2<\cdots<i_k\leq n}(-1)^{k-1}(n-k)!

=\sum_{k=1}^n\left[(-1)^{k-1}(n-k)!\sum_{1\leq i_1<i_2<\cdots<i_k\leq n}1\right].

Podemos ver (por inducción, por ejemplo) que

|\{(i_1,\ldots,i_k):1\leq i_1<i_2<\cdots<i_k\leq n\}|=\binom{n}{k}.

Reemplazando esto entonces, obtenemos que

\left|\bigcup_{i=1}^n\sigma_iS_{n-1}\sigma_i^{-1}\right|=\sum_{k=1}^n(-1)^{k-1}(n-k)!\binom{n}{k}.

Finalmente entonces, obtenemos el cálculo buscado:

|P_n|=n!-\sum_{k=1}^n(-1)^{k-1}(n-k)!\binom{n}{k}=\sum_{k=2}^n(-1)^{k}(n-k)!\binom{n}{k}.

Meta 2:

Queremos calcular ahora la probabilidad \mathbb{P}(P_n) (la probabilidad de que al elegir una permutación de S_n, sea justamente una permutación sin puntos fijos), y queremos encontrar \lim_{n\to\infty}\mathbb{P}(P_n).

Procedimiento:

Tenemos que \mathbb{P}(P_n)=\frac{1}{n!}|P_n|=\sum_{k=2}^n(-1)^{k}\frac{1}{k!}. Entonces

\lim_{n\to\infty}\mathbb{P}(P_n)=\lim_{n\to\infty}\sum_{k=2}^n\frac{(-1)^k}{k!}=\frac{1}{e}.

¡Qué hermoso! Entonces lo que hemos calculado básicamente es que al elegir una permutación cualquiera, aproximadamente 1/e de las veces tal permutación no tendrá puntos fijos. Qué impresionante, ¿no?

Anuncios

Navegación en la entrada única

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: