2.2: Permutaciones de posición prohibida

Supongamos que barajamos una baraja de cartas; ¿cuál es la probabilidad de que ninguna carta esté en su ubicación original? De manera más general, ¿cuántas permutaciones de no\([n]=\{1,2,3,\ldots,n\}\) tienen ninguno de los enteros en sus ubicaciones “correctas”? Es decir, 1 no es primero, 2 no es segundo, y así sucesivamente. Tal permutación se llama un desajuste de\([n]\).

\(S\)Sea el conjunto de todas las permutaciones de\([n]\) y\(A_i\) sean las permutaciones de\([n]\) en las que\(i\) está en el lugar correcto. Entonces queremos saber\(|\bigcap_{i=1}^n A_i^c|\).

Para cualquiera\(i\),\(|A_i|=(n-1)!\): una vez que\(i\) se fija en posición\(i\),\(n-1\) los enteros restantes se pueden colocar en cualquier ubicación.

¿Y qué pasa\(|A_i\cap A_j|\)? Si ambos\(i\) y\(j\) están en la posición correcta, los\(n-2\) enteros restantes se pueden colocar en cualquier lugar, así que\(|A_i\cap A_j|=(n-2)!\).

De la misma manera, vemos eso\(|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|=(n-k)!\). Así, mediante la fórmula de inclusión-exclusión, en la forma de la Ecuación 2.1.1,

\[\eqalign{ |\bigcap_{i=1}^n A_i^c|&=|S|+\sum_{k=1}^n (-1)^k{n\choose k}(n-k)!\cr &=n!+\sum_{k=1}^n (-1)^k{n!\over k!(n-k)!}(n-k)!\cr &=n!+\sum_{k=1}^n (-1)^k{n!\over k!}\cr &=n!+n!\sum_{k=1}^n (-1)^k{1\over k!}\cr &=n!\,\Bigl(1+\sum_{k=1}^n (-1)^k{1\over k!}\Bigr)\cr &=n!\,\sum_{k=0}^n (-1)^k{1\over k!}.\cr }\nonumber\]

La última suma debería parecer familiar:\[e^x=\sum_{k=0}^\infty {1\over k!}x^k.\nonumber\] Sustituir\(x=-1\) da\[e^{-1} = \sum_{k=0}^\infty {1\over k!}(-1)^k.\nonumber\] La probabilidad de obtener un desajuste por casualidad es entonces\[{1\over n!}n!\,\sum_{k=0}^n (-1)^k{1\over k!} =\sum_{k=0}^n (-1)^k{1\over k!},\nonumber\] y cuando\(n\) es mayor que 6, esto está bastante cerca de\[e^{-1} \approx 0.3678.\nonumber\] Así que en el caso de una baraja de cartas, la probabilidad de un descarrilamiento es de aproximadamente 37 %.

Vamos\(D_n=n!\,\sum_{k=0}^n (-1)^k{1\over k!}\). Estos números de desajuste tienen algunas propiedades interesantes. Los descarrilamientos de\([n]\) podrán producirse de la siguiente manera: Para cada uno\(i\in\{2,3,\ldots,n\}\), poner\(i\) en posición 1 y 1 en posición\(i\). Después permuta los números\(\{2,3,\ldots,i-1,i+1,\ldots n\}\) de todas las formas posibles para que ninguno de estos\(n-2\) números esté en el lugar correcto. Hay\(D_{n-2}\) formas de hacer esto. Entonces, manteniendo 1 en posición\(i\), desviar los números\(\{i,2,3,\ldots,i-1,i+1,\ldots n\}\), con la posición “correcta” de\(i\) ahora considerada como posición 1. Hay\(D_{n-1}\) formas de hacer esto. Por lo tanto,\(D_n=(n-1)(D_{n-1}+D_{n-2})\).

Exploramos un poco esta relación de recurrencia:

\[\eqalignno{ D_n&=nD_{n-1}-D_{n-1}+(n-1)D_{n-2}&(*)\cr &=nD_{n-1}-(n-2)(D_{n-2}+D_{n-3})+(n-1)D_{n-2}\cr &=nD_{n-1}-(n-2)D_{n-2}-(n-2)D_{n-3}+(n-1)D_{n-2}\cr &=nD_{n-1}+D_{n-2}-(n-2)D_{n-3}&(*)\cr &=nD_{n-1}+(n-3)(D_{n-3}+D_{n-4})-(n-2)D_{n-3}\cr &=nD_{n-1}+(n-3)D_{n-3}+(n-3)D_{n-4}-(n-2)D_{n-3}\cr &=nD_{n-1}-D_{n-3}+(n-3)D_{n-4}&(*)\cr &=nD_{n-1}-(n-4)(D_{n-4}+D_{n-5})+(n-3)D_{n-4}\cr &=nD_{n-1}-(n-4)D_{n-4}-(n-4)D_{n-5}+(n-3)D_{n-4}\cr &=nD_{n-1}+D_{n-4}-(n-4)D_{n-5}.&(*)\cr }\nonumber\]

Aparece de las líneas estelarizadas que el patrón aquí es que\[D_n=nD_{n-1}+(-1)^kD_{n-k}+(-1)^{k+1}(n-k)D_{n-k-1}.\nonumber\] Si esto continúa, deberíamos llegar a\[D_n=nD_{n-1}+(-1)^{n-2}D_{2}+(-1)^{n-1}(2)D_{1}.\nonumber\]\(D_2=1\) Since y\(D_1=0\), esto daría\[D_n=nD_{n-1}+(-1)^n,\nonumber\] ya\( (-1)^n=(-1)^{n-2}\). En efecto, esto es cierto, y se puede probar por inducción. Esto da una relación de recurrencia algo más simple, por lo que es bastante fácil de calcular\(D_n\).

\[\bullet\quad\bullet\quad\bullet\nonumber\]

Hay muchos problemas similares.

Ejemplo \(\PageIndex{1}\)

¿Cuántas permutaciones de no\([n]\) contienen ninguna instancia de\(i\) seguido por\(i+1\)?

Solución

Por un uso similar de la fórmula de inclusión-exclusión, resulta que esto es\[Q_n=n!\,\sum_{k=0}^{n-1} (-1)^k{1\over k!}+ (n-1)!\,\sum_{k=1}^{n-1} (-1)^{k-1} {1\over (k-1)!}. \nonumber\] Tenga en cuenta que los límites en las dos sumas no son idénticos.

Colaboradores y Atribuciones

• Template:ContribGuichard