¿Por qué es $!n\pmod{n+k}$ un múltiplo de $k+1$ ¿tan a menudo?

Question

Motivación:

Una permutación de un conjunto sin puntos fijos se llama derangement . El número de desórdenes de $n$ se anota como $!n$ o " $n$ subfactorial".

La relación $$!n=(n-1)(!(n-1)+!(n-2))$$ implica que $!n\equiv0\pmod{n-1}$ . Igualmente, $$!n=n(!(n-1))+(-1)^n$$ implica que $!n\equiv(-1)^n\pmod{n}$ . Quería ver si había alguna relación similar con otros factores $n+k$ . No pude encontrar ninguno; en cambio, me topé con algo más extraño.

Un patrón extraño:

Al mirar la tabla de $!n\pmod{n+1}$ (donde por $\text{mod}$ nos referimos al menor residuo no negativo), no hay ningún patrón aparente. Sin embargo, si te fijas bien, verás que una cantidad desproporcionada de elementos son múltiplos de $2$ . Después de calcular el primer $5000$ este número parece converger a alrededor de $76\%$ mayor que el $50\%$ que esperarías si esta secuencia fuera aleatoria.

Asimismo, una cantidad desproporcionada de elementos en la tabla de $!n\pmod{n+2}$ son múltiplos de $3$ : $56\%$ , en contraste con lo esperado $33\%$ .

Esta tendencia continúa: no hay un solo $k\leq1000$ para los que hay menos de lo esperado $\frac1{k+1}$ de la primera $\require{cancel}\cancel{5000}$ $50000$ valores de $!n\pmod{n+k}$ que son múltiplos de $k+1$ . Mirando los datos, incluso diría que la tendencia es más pronunciada cuanto más lejos se va. Aquí hay un Pastebin con mis datos [ editar: y con los datos previstos de La respuesta de Haran ].

Mi pregunta:

¿Por qué se mantiene este patrón? ¿Por qué es $!n\pmod{n+k}$ un múltiplo de $k+1$ mucho más a menudo de lo que sería por casualidad? ¿Y de dónde salen estos porcentajes?

Answer 1

Aquí hay una tabla de los primeros valores de enajenación: $$ \begin{array}{c}\\ n & !n \\ \hline 1 & 0 \\ 2 & 1\\ 3 & 2 \\ 4 & 9 \\ 5 & 44 \\ 6 & 265 \\ 7 & 1854 \\ 8 & 14833 \\ 9 & 133496 \\ 10 & 1334961 \\ \end{array} $$

En primer lugar, podemos observar que todas las entradas impar de $n$ dan salidas pares mientras que todas las entradas pares de $n$ están dando salidas a impar. Esto se puede justificar utilizando la inducción. Está claro que funciona para los primeros casos de la tabla anterior. Ahora, por hipótesis de inducción, $!n+!(n-1) \equiv 1 \pmod{2}$ que muestra que $!(n+1) \equiv n \pmod{2}$ que muestra que las entradas Impares dan salidas pares mientras que las entradas pares dan salidas Impares.

Para todos los valores impar de $n$ podemos ver que $!n$ y $n+1$ son pares, lo que demuestra que el residuo $!n \pmod{n+1}$ también es par. Por lo tanto, ya hemos adquirido $50\%$ de los múltiplos de $2$ . Por otro lado, para valores pares de $n$ Parece que hay un $50\%$ posibilidad de que el menor residuo sea impar o incluso, como se esperaba. Esto nos da una proporción esperada de $50\%+\frac{1}{2}(50\%)=75\%$ de los residuos más pequeños, lo que concuerda con sus datos.

Para el módulo $3$ se puede observar que $!n \pmod{3}$ es $0,1,2,0,2,1 \pmod{3}$ basado en $n \pmod{6}$ . Como nuestra fórmula se basa en la recursión, es fácil ver que, de forma similar al caso anterior, podemos evaluar $!n \pmod{3}$ utilizando $n \pmod{6}$ . De nuevo, como en el caso anterior, siempre que $n \equiv 1,4 \pmod{6}$ es decir, siempre que $n \equiv 1 \pmod{3}$ tenemos $!n \equiv 0 \pmod{3}$ . Así, el menor residuo de $!n \pmod{n+2}$ será divisible por $3$ . Esto es $1$ de cada $3$ casos. Esto da una proporción esperada de $\frac{1}{3}(100\%)+\frac{2}{3}(33.33\%)=55.55\%$ , de acuerdo con sus datos.

Nos gustaría demostrarlo en general, $!n \equiv 0 \pmod{m}$ para $n\equiv 1 \pmod{m}$ . Esto es válido para el caso base $n=1$ como $!1=0$ . Podemos utilizar la fórmula de la suma para las derivaciones para demostrar esto fácilmente. $$!(qm+1)=(qm+1)!\sum_{i=0}^{qm+1} \frac{(-1)^i}{i!}$$ Sólo tenemos que considerar los dos últimos términos, ya que el resto de los términos son divisibles por $qm$ . Así que- $$!(qm+1) \equiv (qm+1)(-1)^{qm}+(-1)^{qm+1} \equiv (-1)^{qm}+(-1)^{qm+1} \equiv 0 \pmod{m}$$

Hemos comprobado nuestra hipótesis de que si $n \equiv 1 \pmod{m}$ entonces $!n \equiv 0 \pmod{m}$ . Cuando tomamos $!n \pmod{n+k}$ y comprobar su valor $\pmod{k+1}$ , si $\gcd(k+1,n+k)=1$ podemos esperar siempre la misma probabilidad para todos los valores $\pmod{k+1}$ . Por lo tanto, si $k+1$ es primo, esperaríamos que la relación esperada fuera $$\frac{1}{k+1}(100\%)+\frac{k}{k+1}\bigg(\frac{1}{k+1} \cdot 100\%\bigg) = \frac{2k+1}{(k+1)^2}(100\%)=\bigg(1-\frac{k^2}{(k+1)^2}\bigg)(100\%)>\frac{100\%}{k+1}$$

que coincide con valores como $k=1,2,4,6$ donde $k+1$ es primo.

Cuando $k+1=\prod_{i=1}^tp_i^{a_i}$ es compuesto, no podemos decir siempre que $\gcd(k+1,n+k)=1$ . Por lo tanto, debemos comprobar todas las posibles $\gcd$ valores. Si tenemos $\gcd(k+1,n+k)=\prod_{i=1}^tp_i^{b_i}$ tenemos $n \equiv 1 \pmod{\prod_{i=1}^tp_i^{b_i}}$ y $n+k \equiv 0 \pmod{\prod_{i=1}^tp_i^{b_i}}$ . Este $\gcd$ se ve para $\phi(\prod_{i=1}^tp_i^{a_i-b_i})$ casos. Además, debemos tener también la divisibilidad por $\prod_{i=1}^tp_i^{a_i}$ dada la divisibilidad por $\prod_{i=1}^tp_i^{b_i}$ que ocurre con una probabilidad de $1$ en $\prod_{i=1}^tp_i^{a_i-b_i}$ . Por lo tanto, nuestro valor esperado es: $$E=\frac{1}{\prod_{i=1}^tp_i^{a_i}}\sum \frac{\phi(\prod_{i=1}^tp_i^{a_i-b_i})}{\prod_{i=1}^tp_i^{a_i-b_i}}=\frac{1}{k+1} \cdot \sum_{d \mid (k+1)} \frac{\phi(d)}{d}=\frac{1}{k+1} \cdot \prod_{i=1}^t \bigg(1+\frac{p_i-1}{p_i} \cdot a_i\bigg)$$

Por lo tanto, concluimos que para $k+1=\prod_{i=1}^tp_i^{a_i}$ el valor esperado (en fracción) es: $$E=\frac{1}{k+1} \cdot \prod_{i=1}^t \bigg(1+\frac{p_i-1}{p_i} \cdot a_i\bigg)$$

Esto parece coincidir con todos los valores de $k$ resolver el problema.

Answer 2

Posible explicación de $k=1$ caso:

Es fácil demostrar que $!n$ es par si $n$ es impar. Para tales $n$ la expresión $!n \pmod{n+1}$ significa que estás dividiendo un número par entre otro número par, por lo que el resto debe ser par. (Supongo que cuentas un resto de $0$ como par / múltiplo de $2$ .)

Por lo tanto, cada impar $n$ satisface su condición. No tengo ni idea de si incluso $n$ valores satisfacen su condición, pero si estos se comportan de forma aleatoria, obtendría aproximadamente la mitad de los valores pares $n$ más todos los valores de impar $n$ valores, para satisfacer su condición. Esto supondría una proporción de $3/4$ , muy cerca de su observado $76\%$ .