Trastorno mental

Permutación de los elementos de un conjunto en el que ningún elemento aparece en su posición original

Número de posibles permutaciones y desajustes de n elementos. n ! ( n factorial ) es el número de n -permutaciones; ! n ( n subfactorial ) es el número de desajustes – n -permutaciones donde todos los n elementos cambian sus lugares iniciales.

En matemáticas combinatorias , un desarreglo es una permutación de los elementos de un conjunto en la que ningún elemento aparece en su posición original. En otras palabras, un desarreglo es una permutación que no tiene puntos fijos .

El número de desajustes de un conjunto de tamaño n se conoce como subfactorial de n o n- ésimo número de desajuste  o n- ésimo  número de De Montmort (en honor a Pierre Remond de Montmort ). Las notaciones para subfactoriales de uso común incluyen ! n , D _n , d _n o n ¡  . ^{[a] [1] [2]}

Para n > 0 , el subfactorial ! n es igual al entero más cercano a n !/ e , donde n ! denota el factorial de n y e ≈ 2,718281828... es el número de Euler . ^[3]

El problema de contar los desequilibrios fue considerado por primera vez por Pierre Raymond de Montmort en su Ensayo de análisis de los juegos de azar [ ^4] en 1708; lo resolvió en 1713, al igual que Nicholas Bernoulli aproximadamente en la misma época.

Ejemplo

Se resaltan los 9 desajustes (de 24 permutaciones).

Supongamos que un profesor da un examen a 4 estudiantes –A, B, C y D– y quiere dejar que cada uno califique los exámenes de los demás. Por supuesto, ningún estudiante debería calificar su propio examen. ¿De cuántas maneras podría el profesor devolver los exámenes a los estudiantes para que los califiquen, de modo que ningún estudiante reciba su propio examen? De 24 permutaciones posibles (¡4!) para devolver los exámenes,

Hay sólo 9 trastornos (mostrados en cursiva azul arriba). En cada otra permutación de este conjunto de 4 miembros, al menos un estudiante obtiene su propia prueba (mostrada en negrita roja).

Otra versión del problema surge cuando preguntamos el número de maneras en que se pueden colocar n cartas, cada una dirigida a una persona diferente, en n sobres con dirección predeterminada de modo que ninguna carta aparezca en el sobre con la dirección correcta.

Trastornos del conteo

Contar los desajustes de un conjunto equivale al problema del guardarropa , en el que se considera el número de formas en que n sombreros (llamémoslos h ₁ a h _n ) pueden devolverse a n personas ( P ₁ a P _n ) de modo que ningún sombrero llegue a su dueño. ^[5]

Cada persona puede recibir cualquiera de los n  − 1 sombreros que no sean suyos. Llamemos h _i al sombrero que recibe la persona P ₁ y consideremos a h _i como su dueño: P _i recibe el sombrero de P _{1 ,} h ₁ o algún otro. En consecuencia, el problema se divide en dos casos posibles:

1. P _i recibe un sombrero distinto de h ₁ . Este caso es equivalente 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 ₁ hay exactamente un sombrero de entre los n  − 1 sombreros restantes que no pueden recibir (para cualquier P _j además de P _i , el sombrero que no se puede recibir es h _j , mientras que para P _i es h ₁ ). Otra forma de ver esto es renombrar h ₁ a h _i , donde el desequilibrio es más explícito: para cualquier j de 2 a n , P _j no puede recibir h _j .
2. P _i recibe h ₁ . En este caso, el problema se reduce a n  − 2 personas y n  − 2 sombreros, porque P ₁ recibió el sombrero de h _i y P _i recibió el sombrero de h ₁ , lo que efectivamente deja a ambos fuera de consideración.

Para cada uno de los n  − 1 sombreros que P ₁ puede recibir, la cantidad de formas en que P ₂ , ...,  P _n pueden recibir sombreros es la suma de los conteos para los dos casos.

Esto nos da la solución al problema del guardarropa: Enunciado algebraicamente, el número ! n de desarreglos de un conjunto de n elementos es para , donde y ^[6] $${\displaystyle !n=\left(n-1\right){\bigl (}{!\left(n-1\right)}+{!\left(n-2\right)}{\bigr )}}$$ ${\displaystyle n\geq 2}$ ${\displaystyle !0=1}$ ${\displaystyle !1=0.}$

El número de alteraciones de longitudes pequeñas se da en la siguiente tabla.

Existen otras expresiones para ! n , equivalentes a la fórmula dada anteriormente. Estas incluyen para y $${\displaystyle !n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}}$$ ${\displaystyle n\geq 0}$

${\displaystyle !n=\left[{\frac {n!}{e}}\right]=\left\lfloor {\frac {n!}{e}}+{\frac {1}{2}}\right\rfloor }$para ${\displaystyle n\geq 1,}$

donde es la función entera más cercana y es la función base . ^{[3] [6]} ${\displaystyle \left[x\right]}$ ${\displaystyle \left\lfloor x\right\rfloor }$

Otras fórmulas relacionadas incluyen ^{[3] [7]} y $${\displaystyle !n=\left\lfloor {\frac {n!+1}{e}}\right\rfloor ,\quad \ n\geq 1,}$$ $${\displaystyle !n=\left\lfloor \left(e+e^{-1}\right)n!\right\rfloor -\lfloor en!\rfloor ,\quad n\geq 2,}$$ $${\displaystyle !n=n!-\sum _{i=1}^{n}{n \choose i}\cdot {!(n-i)},\quad \ n\geq 1.}$$

También se cumple la siguiente recurrencia: ^[6] $${\displaystyle !n={\begin{cases}1&{\text{if }}n=0,\\n\cdot \left(!(n-1)\right)+(-1)^{n}&{\text{if }}n>0.\end{cases}}}$$

Derivación por principio de inclusión-exclusión

También se puede derivar una fórmula no recursiva para el número de desarreglos de un conjunto n . Definimos que es el conjunto de permutaciones de n objetos que fijan el  objeto k . Cualquier intersección de una colección de i de estos conjuntos fija un conjunto particular de i objetos y, por lo tanto, contiene permutaciones. Existen tales colecciones, por lo que se cumple el principio de inclusión-exclusión y, dado que un desarreglo es una permutación que no deja ninguno de los n objetos fijos, esto implica ${\displaystyle 1\leq k\leq n}$ ${\displaystyle S_{k}}$ ${\displaystyle (n-i)!}$ ${\textstyle {n \choose i}}$ $${\displaystyle {\begin{aligned}|S_{1}\cup \dotsm \cup S_{n}|&=\sum _{i}\left|S_{i}\right|-\sum _{i<j}\left|S_{i}\cap S_{j}\right|+\sum _{i<j<k}\left|S_{i}\cap S_{j}\cap S_{k}\right|+\cdots +(-1)^{n+1}\left|S_{1}\cap \dotsm \cap S_{n}\right|\\&={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+{n \choose 3}(n-3)!-\cdots +(-1)^{n+1}{n \choose n}0!\\&=\sum _{i=1}^{n}(-1)^{i+1}{n \choose i}(n-i)!\\&=n!\ \sum _{i=1}^{n}{(-1)^{i+1} \over i!},\end{aligned}}}$$ $${\displaystyle !n=n!-\left|S_{1}\cup \dotsm \cup S_{n}\right|=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}~.}$$

Por otra parte, dado que podemos elegir n - i elementos para que estén en su propio lugar y alterar los otros i elementos en sólo ! i formas, por definición. ^[8] ${\displaystyle n!=\sum _{i=0}^{n}{\binom {n}{i}}\ !i}$

Aumento del número de trastornos comonorteenfoques ∞

De y sustituyendo se obtiene inmediatamente que Este es el límite de la probabilidad de que una permutación seleccionada aleatoriamente de una gran cantidad de objetos sea un desorden. La probabilidad converge a este límite extremadamente rápido a medida que n aumenta, por lo que ! n es el entero más cercano a n !/ e . El gráfico semilogarítmico anterior muestra que el gráfico de desorden está retrasado respecto del gráfico de permutación en un valor casi constante. $${\displaystyle !n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}}$$ $${\displaystyle e^{x}=\sum _{i=0}^{\infty }{x^{i} \over i!}}$$ ${\textstyle x=-1}$ $${\displaystyle \lim _{n\to \infty }{!n \over n!}=\lim _{n\to \infty }\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}=e^{-1}\approx 0.367879\ldots .}$$

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 .

Expansión asintótica en términos de números de Bell

Una expansión asintótica para el número de desajustes en términos de números de Bell es la siguiente: donde es cualquier entero positivo fijo y denota el -ésimo número de Bell . Además, la constante implicada por el gran término O no excede . ^[9] $${\displaystyle !n={\frac {n!}{e}}+\sum _{k=1}^{m}\left(-1\right)^{n+k-1}{\frac {B_{k}}{n^{k}}}+O\left({\frac {1}{n^{m+1}}}\right),}$$ ${\displaystyle m}$ ${\displaystyle B_{k}}$ ${\displaystyle k}$ ${\displaystyle B_{m+1}}$

Generalizaciones

El problema de los encuentros pregunta cuántas permutaciones de un conjunto de tamaño n tienen exactamente k puntos fijos.

Los trastornos son un ejemplo de un campo más amplio de permutaciones restringidas. Por ejemplo, el problema del trío plantea la pregunta de si n parejas de sexos opuestos están sentadas hombre-mujer-hombre-mujer-... alrededor de una mesa, ¿de cuántas maneras se les puede sentar de modo que nadie se siente al lado de su pareja?

Más formalmente, dados los conjuntos A y S , y algunos conjuntos U y V de sobreyecciones A → S , a menudo deseamos saber el número de pares de funciones ( f ,  g ) tales que f está en U y g está en V , y para todo a en A , f ( a ) ≠ g ( a ); en otras palabras, donde para cada f y g , existe un desequilibrio φ 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 formada por sólo dos letras diferentes, digamos n letras A y m letras B, la respuesta es, por supuesto, 1 o 0 según si n = m o no, ya que la única forma de formar un anagrama sin letras fijas es intercambiar todas las A por B , lo que es posible si y sólo si n = m . En el caso general, para una palabra con n ₁ letras X ₁ , n ₂ letras X ₂ , ..., 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 la forma para una cierta 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). ^[10] $${\displaystyle \int _{0}^{\infty }P_{n_{1}}(x)P_{n_{2}}(x)\cdots P_{n_{r}}(x)\ e^{-x}dx,}$$

${\displaystyle \ \int _{0}^{\infty }(t-1)^{z}e^{-t}dt\ }$en el plano complejo

En particular, para los trastornos clásicos, se tiene que donde es la función gamma incompleta superior . $${\displaystyle !n={\frac {\Gamma (n+1,-1)}{e}}=\int _{0}^{\infty }(x-1)^{n}e^{-x}dx}$$ ${\displaystyle \Gamma (s,x)}$

Complejidad computacional

Es NP-completo determinar si un grupo de permutaciones dado (descrito por un conjunto dado de permutaciones que lo generan) contiene algún desequilibrio. ^{[11] [12]}

Notas al pie

1. El nombre "subfactorial" tiene su origen en William Allen Whitworth . ^[1]

Referencias

1. Cajori, Florian (2011). Una historia de las notaciones matemáticas: dos volúmenes en uno. Cosimo, Inc. p. 77. ISBN 9781616405717– a través de Google.
2. Graham, Ronald L.; Knuth, Donald E .; Patashnik, Oren (1994). Matemáticas concretas . Reading, MA: Addison–Wesley. ISBN 0-201-55802-5.
3. Hassani, Mehdi (2003). "Desajustes y aplicaciones". Journal of Integer Sequences . 6 (1). Artículo 03.1.2. Código Bibliográfico :2003JIntS...6...12H – vía cs.uwaterloo.ca.
4. de Montmort, PR (1713) [1708]. Essay d'analyse sur les jeux de Hazard (en francés) (Revue & augmentée de plusieurs Lettres, segunda ed.). París, FR: Jacque Quillau (1708) / Jacque Quillau (1713).
5. Scoville, Richard (1966). "El problema del guardarropa". American Mathematical Monthly . 73 (3): 262–265. doi :10.2307/2315337. JSTOR  2315337.
6. Stanley, Richard (2012). Combinatoria enumerativa, volumen 1 (2.ª edición). Cambridge University Press. Ejemplo 2.2.1. ISBN 978-1-107-60262-5.
7. Weisstein, Eric W. "Subfactorial". MathWorld .
8. Bizley, MTL (mayo de 1967). "Una nota sobre los trastornos". Math. Gaz . 51 : 118-120.
9. Hassani, M. "Desajustes y suma alternada de permutaciones por integración". J. Integer Seq. 23, artículo 20.7.8, 1–9, 2020
10. Even, S.; Gillis, J. (1976). "Desajustes y polinomios de Laguerre". Actas matemáticas de la Cambridge Philosophical Society . 79 (1): 135–143. Código Bibliográfico :1976MPCPS..79..135E. doi :10.1017/S0305004100052154. S2CID  122311800 . Consultado el 27 de diciembre de 2011 .
11. Lubiw, Anna (1981). "Algunos problemas NP-completos similares al isomorfismo de grafos". Revista SIAM de Computación . 10 (1): 11–21. doi :10.1137/0210002. MR  0605600.
12. Babai, László (1995). "Grupos de automorfismo, isomorfismo, reconstrucción". Handbook of Combinatorics (PDF) . Vol. 1, 2. Ámsterdam, Países Bajos: Elsevier. cap. 27, págs. 1447–1540. MR  1373683 – vía cs.uchicago.edu.

Enlaces externos

• Baez, John (2003). “¡Vamos a volvernos locos!” (PDF) – vía math.ucr.edu.
• Bogart, Kenneth P.; Doyle, Peter G. (1985). "Solución no sexista del problema del trío" – vía math.dartmouth.edu.
• Weisstein, EW "Trastorno". MathWorld / Wolfram Research: a través de mathworld.wolfram.com.