Trastorno mental

Permutation of the elements of a set in which no element appears in its original position

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

En matemáticas combinatorias , un trastorno 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 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 subfactorial de n o número de trastorno n- ésimo o número de Montmort n- ésimo (en honor a Pierre Remond de Montmort ). Las notaciones para subfactoriales de uso común incluyen ! n, D _n , d _n , o n ¡. ^{[1] [2]}

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

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

Ejemplo

Se resaltan los 9 trastornos (de 24 permutaciones).

Supongamos que un profesor les dio una prueba a 4 estudiantes (A, B, C y D) y quiere que califiquen las pruebas 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 las pruebas,

solo hay 9 trastornos (que se muestran arriba en cursiva azul). En cada otra permutación de este conjunto de 4 miembros, al menos un estudiante recupera su propio examen (que se muestra en rojo y negrita).

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

Trastornos de conteo

Contar los trastornos de un conjunto equivale al problema de la verificación del sombrero , en el que se considera el número de formas en que n sombreros (llámelos h ₁ a h _n ) pueden devolverse a n personas ( P ₁ a P _n ) de manera que no El sombrero regresa a su dueño. ^[5]

Cada persona puede recibir cualquiera de los n  − 1 sombreros que no sea el suyo. Llame h _i al sombrero que recibe la persona P ₁ y considérelo 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 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 ₁ hay exactamente un sombrero entre los n  − 1 sombreros restantes que no pueden recibir (por cualquier P _j además de _Pi , el sombrero no aceptable es h _j , mientras que para P _i es h ₁ ). Otra forma de ver esto es cambiar el nombre de h ₁ a h _i , donde el trastorno es más explícito: para cualquier j de 2 a n , P _j no puede recibir h _j .
2. Pi 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, el número de formas en que P ₂ , ...,  P _n pueden recibir 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 trastornos de un conjunto de n elementos es

${\displaystyle !n=(n-1)\cdot ({!(n-1)}+{!(n-2)})}$para , ${\displaystyle n\geq 2}$

dónde y . ^[6] ${\displaystyle !0=1}$ ${\displaystyle !1=0}$

El número de trastornos de longitud pequeña se indica en la siguiente tabla.

¡Hay varias otras expresiones para! n , equivalente a la fórmula dada anteriormente. Éstas incluyen

${\displaystyle !n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}}$para ${\displaystyle n\geq 0}$

y

${\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 suelo . ^{[3] [6]} ${\displaystyle \left[x\right]}$ ${\displaystyle \left\lfloor x\right\rfloor }$

Otras fórmulas relacionadas incluyen ^{[3] [7]}

$${\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 trastornos de un n -conjunto. Porque definimos como el conjunto de permutaciones de n objetos que fijan el -ésimo objeto. Cualquier intersección de una colección de i de estos conjuntos fija un conjunto particular de i objetos y, por tanto, contiene permutaciones. Existen tales colecciones, por lo que el principio de inclusión-exclusión produce ${\displaystyle 1\leq k\leq n}$ ${\displaystyle S_{k}}$ ${\displaystyle 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}}}$$

n

$${\displaystyle !n=n!-\left|S_{1}\cup \dotsm \cup S_{n}\right|=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}.}$$

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

Crecimiento del número de trastornos a medida que n se aproxima a ∞

De

$${\displaystyle !n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}}$$

$${\displaystyle e^{x}=\sum _{i=0}^{\infty }{x^{i} \over i!}}$$

${\displaystyle \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 .}$$

probabilidadnnnesemilogarítmico

Puede encontrar más información sobre este cálculo y el límite anterior en el artículo sobre 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 trastornos en términos de números de Bell es la siguiente:

$${\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),}$$

número de BellO grande^[9] ${\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 del campo más amplio de permutaciones restringidas. Por ejemplo, el problema del ménage pregunta si n parejas de sexos opuestos están sentadas hombre-mujer-hombre-mujer-... alrededor de una mesa, ¿de cuántas maneras pueden sentarse para 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 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 formada por sólo dos letras diferentes, digamos n letras A y m letras B, la respuesta es, por supuesto, 1 o 0 dependiendo de si n = m o no, ya que es la única forma de formar un anagrama sin letras fijas es intercambiar todas las A por B , lo cual es posible si y solo 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

$${\displaystyle \int _{0}^{\infty }P_{n_{1}}(x)P_{n_{2}}(x)\cdots P_{n_{r}}(x)e^{-x}\,dx,}$$

P _​​nP _nnrP _npolinomios de Laguerrehasta^[10]

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

En particular, para los trastornos clásicos, se tiene que

$${\displaystyle !n={\frac {\Gamma (n+1,-1)}{e}}=\int _{0}^{\infty }(x-1)^{n}e^{-x}dx}$$

función gamma incompleta superior ${\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 trastorno. ^[11]

Referencias

1. El nombre "subfactorial" se origina en William Allen Whitworth ; ver Cajori, Florian (2011), Una historia de las notaciones matemáticas: dos volúmenes en uno, Cosimo, Inc., p. 77, ISBN 9781616405717.
2. Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Matemáticas concretas (1994), Addison – Wesley, Reading MA. ISBN 0-201-55802-5 
3. Hassani, Mehdi (2003). "Trastornos y aplicaciones". Diario de secuencias enteras . 6 (1): Artículo 03.1.2. Código Bib : 2003JIntS...6...12H.
4. de Montmort, PR (1708). Ensayo de análisis sobre los juegos de azar . París: Jacque Quillau. Segunda edición, Revue & augmentée de plusieurs Lettres . París: Jacque Quillau. 1713.
5. Scoville, Richard (1966). "El problema del cheque de sombrero". Mensual Matemático Estadounidense . 73 (3): 262–265. doi :10.2307/2315337. JSTOR  2315337.
6. Stanley, Richard (2012). Combinatoria enumerativa, volumen 1 (2 ed.). Prensa de la Universidad de Cambridge. Ejemplo 2.2.1. ISBN 978-1-107-60262-5.
7. Weisstein, Eric W. "Subfactorial". MundoMatemático .
8. MTL Bizley, Una nota sobre los trastornos, Matemáticas. Gaz., 51 (mayo de 1967), págs. 118-120.
9. Hassani, M. "Trastornos y suma alterna de permutaciones por integración". J. Sec. entera. 23, Artículo 20.7.8, 1 a 9, 2020
10. Incluso, S.; J. Gillis (1976). "Trastornos y polinomios de Laguerre". Actas matemáticas de la Sociedad Filosófica de Cambridge . 79 (1): 135-143. Código Bib : 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 gráficos", 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: ¿un grupo de permutación dado tiene 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 al problema del ménage".
• Weisstein, Eric W. "Trastorno mental". MathWorld: un recurso web de Wolfram.