8 votos

Contando algunos derangements especiales

Una alteración de una lista de $n$ distintas entradas es una permutación de la lista para que no correspondientes entradas del partido. Es bien sabido que el número de estas alteraciones es el entero más cercano a $n!/e$ donde $e$ es la base de los logaritmos naturales.

Digamos que una permutación de una lista es una $\mu$-alteración si tanto ella como su inversa pedido son alteraciones. Equivalentemente, si la permutación es una alteración tanto de la lista original y de la inversa de la lista original.

Cuántas $\mu$-alteraciones de la lista $[1,2,..,n]$ hay? Hay una fórmula exacta? Una buena aproximación o atado?

Hay no $\mu$-alteraciones de $n \lt 4$, salvo en el caso trivial de una lista vacía. Tengo cuenta para $n \le 10$ a continuación mediante la enumeración de posibilidades con un poco de código de Prólogo:

 n | # of µ-derangements 
---+----------------------
 4 |           4
 5 |          16
 6 |          80
 7 |         672
 8 |        4752
 9 |       48768
10 |      440192

La OEIS tiene esta secuencia como A003471, con una recurrencia de la relación que sugiere una cierta separación en par o impar de términos podría simplificar las cosas.

8voto

JiminyCricket Puntos 143

Para $n=2k$, esto es equivalente a Lo que es la Expresión General Para la Probabilidad de Error de Intercambio de Regalos Dibujar, con una ranura y su inversa socio de la formación de una pareja, la respuesta para este caso es

$$\int_0^\infty\left(x^2-4x+2\right)^k\mathrm e^{-x}\mathrm dx\;,$$

y me derivaron en la respuesta a la otra pregunta de que esto va como $n!/\mathrm e^2$ grandes $n$.

Para $n=2k+1$, hay una sola ranura sin pareja, que conduce a un factor de $-L_1(x)=x-1$, así que la respuesta para este caso es

$$\int_0^\infty\left(x^2-4x+2\right)^k(x-1)\mathrm e^{-x}\mathrm dx\;.$$

El análisis asintótico se mantiene esencialmente sin cambios, así que esto también va de la $n!/\mathrm e^2$ grandes $n$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X