Desorden (permutación)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 20 de diciembre de 2021; la verificación requiere 1 edición .

En combinatoria , un desorden es una permutación sin puntos fijos .

Ejemplos

Comprobación de trabajo

Digamos que un profesor le dio a cuatro estudiantes (llamémoslos A, B, C y D) una prueba y luego les pidió que la revisaran entre ellos. Naturalmente, ningún estudiante debe revisar su propia prueba. ¿Cuántas opciones tiene el profesor para distribuir pruebas de control en las que ningún alumno obtiene su propio trabajo? De las 24 permutaciones (¡4!) para el regreso del trabajo, solo 9 trastornos son adecuados para nosotros:

BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA.

En cualquier otra permutación de estos 4 elementos, al menos un estudiante obtiene su examen para ser revisado.

Problema de letras

Calcular la cantidad de desorden es un problema popular en las matemáticas de las Olimpiadas , que se presenta en varias formulaciones, como el problema del desorden , el problema de las letras , el problema de la reunión , etc.

Si las cartas se colocan al azar en diferentes sobres, ¿cuál es la probabilidad de que cualquiera de las cartas termine en su propio sobre?

norte

norte

La respuesta viene dada por la expresión

1-{\frac {!n}{n!}}\approx 1-{\frac {1}{e}}.

Así, la respuesta depende débilmente del número de cartas y sobres y es aproximadamente igual a la constante . $1-{\frac {1}{e}}\aprox. 0{,}63212$

Número de disturbios

El número de todos los desordenes de orden n se puede calcular utilizando el principio de inclusión-exclusión y viene dado por

!n=n!-{\frac {n!}{1!}}+{\frac {n!}{2!}}-{\frac {n!}{3!}}+\puntos +(-1)^{n}{\frac {n!}{n!}}=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{ k!}},

que se llama el subfactorial de n .

El número de trastornos satisface las relaciones recursivas $!n=d(n)$

d(n)=(n-1)[d(n-1)+d(n-2)]

d(n)=nd(n-1)+(-1)^{n},

donde y . $d(1)=0$ $d(2)=1$

En vista de que , el valor se comporta como . Además, cuando se puede representar como el resultado de redondear el número . $\sum _{k=0}^{\infty}(-1)^{k}{\frac {1}{k!}}={\frac {1}{e}}$ $!norte$ $norte$ ${\frac{n!}{e))$ $n>0$ ${\frac{n!}{e))$

Desorden (permutación)

Ejemplos

Comprobación de trabajo

Problema de letras

Número de disturbios

Véase también

Notas

Enlaces