Números combinatorios clásicos · Definición

Desarreglo

combinatoria enumerativanúmeros combinatorios clásicos

Antes de empezar necesitas conocer

El problema del sombrero o de la carta extraviada pide contar las permutaciones que evitan todos los puntos fijos. La respuesta sale directamente del principio de inclusión-exclusión.

Definición

Un desarreglo es una permutación de \(n\) elementos sin puntos fijos; el número de desarreglos es \(D_n\).

\[D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}\]

Sea \(A_i\) el conjunto de permutaciones que fijan el elemento \(i\). Como \(|A_{i_1}\cap\cdots\cap A_{i_k}|=(n-k)!\), la inclusión-exclusión da la fórmula de cabecera. Además, \(D_n=(n-1)(D_{n-1}+D_{n-2})\) y \(D_n/n!\to e^{-1}\).

Para \(n=4\) se suman \(4!\), \(-\binom{4}{1}3!\), \(+\binom{4}{2}2!\), \(-\binom{4}{3}1!\) y \(+\binom{4}{4}0!\), que da \(9\). Por ejemplo, \(2143\) y \(4321\) son dos de esos desarreglos.

Error típico: quedarse con el primer término de la serie y escribir \(D_n\approx n!-1\), olvidando que los términos de orden superior corrigen los solapamientos entre conjuntos de puntos fijos.

Para pensar

¿Por qué \(n!-\sum_i |A_i|\) da cero y no \(D_n\)?

Porque \(\sum_i |A_i|=n\,(n-1)!=n!\) cuenta de más las permutaciones con varios puntos fijos; hay que volver a sumar las intersecciones.

Ejercicios 10

  1. ¿Cuál de estas permutaciones de \(\{1,2,3,4\}\), escritas como \(\sigma(1)\sigma(2)\sigma(3)\sigma(4)\), es un desarreglo?
  2. De los 9 desarreglos de 4 elementos, ¿cuántos son un ciclo de longitud 4?
  3. ¿Cuánto vale \(D_3\)?
  4. ¿Cuánto vale \(D_4\)?
  5. Si \(D_n/n!\) se aproxima a \(1/e\), ¿qué proporción aproximada de permutaciones de \(n\) elementos tiene algún punto fijo para \(n\) grande?
  6. En la serie \(D_n/n!=\sum_{k=0}^{n}\frac{(-1)^k}{k!}\), ¿cuál es el coeficiente del término \(k=2\)?
  7. Cuando \(n\) es grande, ¿a qué valor se aproxima \(D_n/n!\)?
  8. ¿Cuántas permutaciones de 5 elementos tienen exactamente un punto fijo?
  9. ¿Cuántas permutaciones de 4 elementos fijan al menos un punto?
  10. ¿Cuál afirmación sobre \(D_n\) es falsa?

Referencias

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.