En matemática combinatoria , una alteración es una permutación de los elementos de un conjunto , de manera que ningún elemento aparece en su posición original. En otras palabras, un trastorno es una permutación que no tiene puntos fijos .
El número de trastornos de un conjunto de tamaño n se conoce como el subfactorial de n o el número n- ésimo de trastorno o el número n- ésimo de Montmort . Las notaciones para subfactoriales de uso común incluyen! n, D n , d n o n ¡. [1] [2]
¡Se puede demostrar eso! n es igual al número entero más próximo a n ! / E, donde n ! denota el factorial de n y e es el número de Euler .
El problema de contar los trastornos fue considerado por primera vez por Pierre Raymond de Montmort [3] en 1708; lo resolvió en 1713, al igual que Nicholas Bernoulli aproximadamente al mismo tiempo.
Ejemplo
Suponga que un profesor dio una prueba a 4 estudiantes (A, B, C y D) y quiere que ellos califiquen las pruebas de los demás. Por supuesto, ningún estudiante debe calificar su propia prueba. ¿De cuántas maneras podría el profesor devolver las pruebas a los estudiantes para que las califiquen, de modo que ningún estudiante reciba su propia prueba? De 24 posibles permutaciones (¡4!) Para devolver las pruebas,
ABCD , AB DC, A CB D , Un CDB, Un DBC, A D C B, BA CD , BADC , BCA D , BCDA , BDAC , BD C A, CABINA D , CADB , C B A D , C B DA, CDAB , CDBA , DABC , DA C B, D B AC, D BC A, DCAB , DCBA .
solo hay 9 trastornos (mostrados arriba en cursiva azul). En todas las demás permutaciones de este conjunto de 4 miembros, al menos un estudiante recupera su propia prueba (que se muestra en rojo negrita).
Otra versión del problema surge cuando preguntamos el número de formas en que n cartas, cada una dirigida a una persona diferente, pueden colocarse en n sobres con la dirección previa para que ninguna carta aparezca en el sobre con la dirección correcta.
Contando trastornos
Contar los desarreglos de un conjunto equivale a lo que se conoce como el problema de la verificación del sombrero , [4] en el que se considera el número de formas en que n sombreros (llámelos h 1 a h n ) pueden devolverse a n personas ( P 1 a P n ) de manera que ningún sombrero regrese a su dueño.
Cada persona puede recibir cualquiera de los n - 1 sombreros que no sea el suyo. Llame al sombrero que P 1 reciba h i y considere al dueño de h i : P i recibe el sombrero de P 1 , h 1 o algún otro. En consecuencia, el problema se divide en dos casos posibles:
- P i recibe un sombrero distinto de h 1 . Este caso equivale a resolver el problema con n - 1 personas y n - 1 sombreros porque para cada una de las n - 1 personas además de P 1 hay exactamente un sombrero entre los n - 1 sombreros restantes que pueden no recibir (por cualquier P j además de P i , el sombrero inadmisible es h j , mientras que para P i es h 1 ).
- P i recibe h 1 . En este caso, el problema se reduce a n - 2 personas y n - 2 sombreros.
Para cada uno de los n - 1 sombreros que P 1 puede recibir, el número de formas en que P 2 ,…, P n pueden recibir todos sombreros es la suma de los recuentos de los dos casos. Esto nos da la solución al problema del hat-check: ¡expresado algebraicamente, el número! n de alteraciones de un conjunto de n elementos es
- ,
donde! 0 = 1 y! 1 = 0. Los primeros valores de! n son:
norte | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
! norte | 1 | 0 | 1 | 2 | 9 | 44 | 265 | 1.854 | 14,833 | 133,496 | 1,334,961 | 14,684,570 | 176,214,841 | 2,290,792,932 |
También hay varias otras expresiones (equivalentes) para! n : [5]
(dónde es la función entera más cercana [6] yes la función de piso )
Para cualquier número entero n ≥ 1 ,
Entonces, para cualquier número entero n ≥ 1 , y para cualquier número real r ∈ [1/3, 1/2] ,
Por lo tanto, como e = 2.71828… ,1/mi ∈ [ 1/3, 1/2] , luego [7]
La siguiente repetición también es válida: [8]
Derivación por principio de inclusión-exclusión
Otra derivación de una fórmula (equivalente) para el número de alteraciones de un conjunto n es la siguiente. Para definimos ser el conjunto de permutaciones de n objetos que fijan el k- ésimo objeto. Cualquier intersección de una colección de i de estos conjuntos fija un conjunto particular de i objetos y por lo tanto contienepermutaciones. Existentales colecciones, por lo que el principio de inclusión-exclusión produce
y dado que un trastorno es una permutación que no deja fijo ninguno de los n objetos, obtenemos
Límite de la relación entre el trastorno y la permutación cuando n se aproxima a ∞
De
y
se obtiene inmediatamente usando x = −1:
Este es el límite de la probabilidad de que una permutación seleccionada al azar de un gran número de objetos sea un trastorno. La probabilidad converge a este límite extremadamente rápido a medida que n aumenta, ¡por eso! n es el número entero más cercano a n ! / e . Los anteriores semi-log gráfico muestra que el gráfico desarreglo retrasa el gráfico de permutación por un valor casi constante.
Puede encontrar más información sobre este cálculo y el límite anterior en el artículo sobre las estadísticas de permutaciones aleatorias .
Generalizaciones
El problème des rencontres pregunta cuántas permutaciones de un conjunto de tamaño n tienen exactamente k puntos fijos.
Los trastornos son un ejemplo del campo más amplio de permutaciones restringidas. Por ejemplo, el problema del ménage pregunta si n parejas del sexo opuesto están sentadas hombre-mujer-hombre-mujer -... alrededor de una mesa, ¿de cuántas formas se pueden sentar para que nadie se siente al lado de su pareja?
Más formalmente, conjuntos dados A y S , y algunos conjuntos de U y V de surjections A → S , que a menudo desean saber el número de pares de funciones ( f , g ) tal que f está en U y g es en V , y para todo a en A , f ( a ) ≠ g ( a ); en otras palabras, donde para cada f y g , existe un trastorno φ de S tal que f ( a ) = φ ( g ( a )).
Otra generalización es el siguiente problema:
- ¿Cuántos anagramas sin letras fijas de una palabra determinada hay?
Por ejemplo, para una palabra compuesta de solo dos letras diferentes, digamos n letras A ym letras B, la respuesta es, por supuesto, 1 o 0 según n = m o no, ya que la única forma de formar un anagrama sin letras fijas es intercambiar toda la A con B , lo cual es posible si y solo si n = m . En el caso general, para una palabra con n 1 letras X 1 , n 2 letras X 2 , ..., n r letras X r resulta (después de un uso adecuado de la fórmula de inclusión-exclusión ) que la respuesta tiene el formulario:
para una determinada secuencia de polinomios P n , donde P n tiene grado n . Pero la respuesta anterior para el caso r = 2 da una relación de ortogonalidad, de donde los P n son los polinomios de Laguerre ( hasta un signo que se decide fácilmente). [9]
En particular, para los trastornos clásicos
Complejidad computacional
Es NP-completo para determinar si un grupo de permutación dado (descrito por un conjunto dado de permutaciones que lo generan) contiene alguna alteración. [10]
Referencias
- ^ El nombre "subfactorial" se origina con William Allen Whitworth ; véase Cajori, Florian (2011), A History of Mathematical Notations: Two Volumes in One , Cosimo, Inc., p. 77, ISBN 9781616405717.
- ^ Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Matemáticas concretas (1994), Addison-Wesley, Reading MA. ISBN 0-201-55802-5
- ↑ de Montmort, PR (1708). Essay d'analyse sur les jeux de hazard . París: Jacque Quillau. Segunda edición, Revue & augmentée de plusieurs Lettres . París: Jacque Quillau. 1713.
- ^ Scoville, Richard (1966). "El problema de la revisión del sombrero". American Mathematical Monthly . 73 (3): 262-265. doi : 10.2307 / 2315337 . JSTOR 2315337 .
- ^ Hassani, M. "Trastornos y aplicaciones". J. Integer Seq. 6, núm. 03.1.2, 1 a 8, 2003
- ^ Weisstein, Eric W. "Función entera más cercana" . MathWorld .
- ^ Weisstein, Eric W. "Subfactorial" . MathWorld .
- ^ Consulte las notas para (secuencia A000166 en la OEIS ).
- ^ Incluso, S .; J. Gillis (1976). "Trastornos y polinomios de Laguerre" . Procedimientos matemáticos de la Sociedad Filosófica de Cambridge . 79 (1): 135-143. doi : 10.1017 / S0305004100052154 . Consultado el 27 de diciembre de 2011 .
- ^ Lubiw, Anna (1981), "Algunos problemas NP-completos similares al isomorfismo de grafos", SIAM Journal on Computing , 10 (1): 11-21, doi : 10.1137 / 0210002 , MR 0605600. Babai, László (1995), "Grupos de automorfismo, isomorfismo, reconstrucción", Manual de combinatoria, Vol. 1, 2 (PDF) , Amsterdam: Elsevier, págs. 1447-1540, MR 1373683 ,
Un resultado sorprendente de Anna Lubiw afirma que el siguiente problema es NP-completo: ¿Tiene un grupo de permutación dado un elemento libre de punto fijo?
.
enlaces externos
- Báez, John (2003). "¡Vamos a trastornarnos!" (PDF) .
- Bogart, Kenneth P .; Doyle, Peter G. (1985). "Solución no sexista del problema del ménage" .
- Dickau, Robert M. "Diagramas de trastornos" . Figuras matemáticas usando Mathematica .
- Hassani, Mehdi. "Trastornos y aplicaciones" . Journal of Integer Sequences (JIS), Volumen 6, Número 1, Artículo 03.1.2, 2003.
- Weisstein, Eric W . "Trastorno" . MathWorld: un recurso web de Wolfram.