7.4: Desordenamientos
- Page ID
- 118515
Ahora consideremos una situación en la que podamos hacer uso de las propiedades definidas en el Ejemplo 7.5. Corrige un entero positivo n y deja que X denote el conjunto de todas las permutaciones en\([n]\). Una permutación\(\sigma \in X\) se llama un trastornamiento si es\(\sigma(i) \neq i\) para todos\(i=1,2,…,n\). Por ejemplo, la permutación\(\sigma\) que se da a continuación es un desajuste, mientras que no lo\(\mathcal{τ}\) es.
Si volvemos a dejar\(P_i\) ser la propiedad que\(\sigma(i)=i\), entonces los trastornamientos son precisamente aquellas permutaciones que no satisfacen\(P_i\) para ninguna\(i = 1,2,...,n\).
Para cada subconjunto\(S \subseteq [n]\), \(N(S)\)depende sólo de\(|S|\). De hecho, si\(|S|=k\), entonces
\(N(S) = (n-k)!\)
- Prueba
-
Para cada uno\(i \in S\), el valor\(\sigma(i)=i\) es fijo. Los otros valores de\(\sigma\) son una permutación entre las\(n−k\) posiciones restantes, y hay\((n−k)!\) de éstas.
Como antes, el resultado principal de esta sección se desprende inmediatamente del lema y del Principio de Inclusión-Exclusión.
Para cada entero positivo\(n\), el número\(d_n\) de desajustes de\([n]\) satisface
\(d_n = \displaystyle \sum_{k=0}^n (-1)^k \dbinom{n}{k}(n-k)!\).
Por ejemplo,
\[\begin{align*} d_5 &= \dbinom{5}{0}5! - \dbinom{5}{1} 4! + \dbinom{5}{2}3! - \dbinom{5}{3}2! + \dbinom{5}{4}1! - \dbinom{5}{5} 0! \\[4pt] &= 120 - 120 + 60 -20 +5 -1 \\[4pt] &= 44 \end{align*}\]
Ha sido tradicional plasmar el tema de los desórdenes como una historia, llamada el problema Hat Check. La historia pertenece a la época en que los hombres llevaban sombreros de copa. Para un baile elegante, 100 hombres revisan sus sombreros de copa con la persona Hat Check antes de entrar al piso del salón de baile. Más tarde en la noche, la traviesa persona del cheque del sombrero decide devolver los sombreros al azar. ¿Cuál es la probabilidad de que los 100 hombres reciban un sombrero distinto al suyo? Resulta que la respuesta es muy cercana a\(1/e\), como muestra el siguiente resultado.
Para un entero positivo\(n\), vamos\(d_n\) denotar el número de desajustes de\([n]\). Entonces
\(\displaystyle \lim_{n \to \infty} \dfrac{d_n}{n!} = \dfrac{1}{e}\).
Equivalentemente, la fracción de todas las permutaciones de\([n]\) que son desajustes se acerca a\(1/e\) medida que\(n\) aumenta.
- Prueba
-
Es fácil ver que
\(\dfrac{d_n}{n!} = \dfrac{\sum_{k=0}^n(-1)^k \binom{n}{k}(n-k)!}{n!}\)
\(= \displaystyle \sum_{k=0}^n(-1)^k \dfrac{n!}{k!(n-k)!} \dfrac{(n-k)!}{n!}\)
\(= \displaystyle \sum_{k=0}^n (-1)^k \dfrac{1}{k!}\).
Recordemos de Calculus que la expansión de la serie Taylor\(e^x\) está dada por
\(e^x = \displaystyle \sum_{k=0}^{\infty} \dfrac{x^k}{k!}\),
y así el resultado luego sigue sustituyendo\(x=-1\).
Por lo general no estamos tan interesados en\(d_n\) sí mismos como lo estamos en enumerar permutaciones con ciertas restricciones, como lo ilustra el siguiente ejemplo.
Considera el problema del Hat Check, pero supongamos que en vez de querer que ningún hombre se vaya con su propio sombrero, nos interesa la cantidad de formas de distribuir los 100 sombreros para que precisamente 40 de los hombres se vayan con sus propios sombreros.
Si 40 hombres se van con sus propios sombreros, entonces hay 60 hombres que no reciben sus propios sombreros. Hay\(C(100,60)\) formas de elegir a los 60 hombres que no recibirán sus propios sombreros y\(d_{60}\) formas de distribuir esos sombreros para que ningún hombre reciba los suyos. Sólo hay una manera de distribuir los 40 sombreros a los hombres que deben recibir sus propios sombreros, es decir, que hay
\(\dbinom{100}{60}d_{60} = 42078873492228172128327462833391345210773815159514072218289944467852500232068048628965153767728913178940196920\)
tales formas de devolver los sombreros.