9.1: Desórdenes

Definición: Desórdenes

Un desajuste de una lista de objetos es una permutación de los objetos, en la que no queda ningún objeto en su posición original.

Un ejemplo clásico de esto es una situación en la que escribes cartas a diez personas, dirijas sobres a cada una de ellas, y luego las pones en los sobres, pero accidentalmente terminas sin ninguna de las letras en el sobre correcto.

Otro ejemplo podría ser una clase de baile en la que se inscriben cinco parejas hermano-hermana. El instructor los mezcla para que nadie esté bailando con un hermano.

Ya que estamos considerando la enumeración, no debería sorprenderte que la pregunta que queremos responder es: ¿de cuántas maneras puede suceder esto? Es decir, dados\(n\) los objetos, ¿cuántos descarrilamientos de los\(n\) objetos hay? Utilicemos\(D_n\) para denotar el número de desórdenes de\(n\) los objetos.

Podemos etiquetar los objetos con los números\(\{1, . . . , n\}\), y pensar en un desajuste como una bijección

\[f : \{1, . . . , n\} → \{1, . . . , n\}\]

tal que\(f\) no fija ningún valor. Hay\(n − 1\) opciones para\(f(n)\), ya que la única restricción es\(f(n) \neq n\). Diga\(f(n) = i\). Consideramos dos casos posibles.

Caso 1:\(f(i) = n\)

Ahora bien, en los demás\(n − 2\) valores entre\(1\) y\(n\) que no son\(i\) ni\(n\),\(f\) deben\(\{1, . . . , n −1\} \setminus \{i\}\) mapearse a\(\{1, . . . , n −1\} \setminus \{i\}\), y deben ser un desconcierto. Entonces hay\(D_{n−2}\) desórdenes que tienen\(f(n) = i\) y\(f(i) = n\).

Caso 2:\(f(j) = n\) para algunos\(j \neq i\)

En este caso, definimos otra función

\[g : \{1, . . . , n − 1\} → \{1, . . . , n − 1\}\]

como sigue. Nosotros establecemos\(g(j) = i\), y para cada otro valor,\(g(a) = f(a)\) (es decir, para cada\(a ∈ \{1, . . . , n − 1\} \setminus \{j\}\)). Tuvimos\(f(j) = n\) y\( f(n) = i\), y estamos eliminando\(n\) del desajuste manteniendo una bijección, creando el atajo\(f\) con\(g(j) = i\) pero\(g(a) = f(a)\) para todos los demás\(a ∈ \{1, . . . , n − 1\}\). Ya que\(f\) es un desajuste y\(j \neq i\), vemos que también\(g\) es un desajuste (esta vez de\(n − 1\) objetos). Entonces hay\(D_{n−1}\) posibles desórdenes\(g\), y para una elección fija de\(i\), estos están en correspondencia uno a uno con los descarrilamientos\(f\) que tienen\(f(j) = n\) y\(f(n) = i\), por lo que también hay\(D_{n−1}\) de estos.

Concluimos que\(D_n = (n − 1)(D_{n−1} + D_{n−2})\).

También necesitamos algunas condiciones iniciales. Tenemos\(D_1 = 0\); no hay forma de organizar un solo objeto para que no termine en el lugar correcto. También,\(D_2 = 1\), ya que existe exactamente una manera de descarrilar dos objetos (intercambiándolos).

Si quisiéramos resolver esta secuencia definida recursivamente, necesitaríamos usar funciones generadoras exponenciales, que presentaremos en este capítulo pero que realmente no estudiaremos en este curso. En cambio, daremos la fórmula explícita para\(D_n\) sin pruebas.

Proposición\(\PageIndex{1}\)

Para cualquiera\(n ≥ 1\), el número de descarrilamientos de\(n\) objetos es

\[D_n = n! \left( \sum_{i=0}^{n} \dfrac{(-1)^i}{i!} \right) \]

Ejercicio\(\PageIndex{1}\)

1. Utilizar la inducción para probar la Proposición 9.1.1.
2. ¿Qué tipo de inducción tuviste que usar para probar la Proposición 9.1.1?
3. Calcular\(D_5\) usando la fórmula explícita dada en la Proposición 9.1.1.
4. Calcular\(D_5\) usando la relación recursiva.