20
$\begingroup$

Motivation:

A permutation of a set with no fixed points is called a derangement. The number of derangements of $n$ elements is notated as $!n$ or "$n$ subfactorial".

The relation $$!n=(n-1)(!(n-1)+!(n-2))$$ implies that $!n\equiv0\pmod{n-1}$. Likewise, $$!n=n(!(n-1))+(-1)^n$$ implies that $!n\equiv(-1)^n\pmod{n}$. I wanted to see if there was any similar relation involving other factors $n+k$. I wasn't able to find one; instead, I stumbled upon something weirder.

A weird pattern:

When looking at the table of $!n\pmod{n+1}$ (where by $\text{mod}$ we mean the least non-negative residue), there's no apparent pattern. However, if you look close enough, you'll notice that a disproportionate amount of elements are multiples of $2$. After calculating the first $5000$ values, this number seems to converge to around $76\%$, greater than the $50\%$ you'd expect if this sequence was random.

Proportion of !n (mod n+1) that are multiples of 2

Likewise, a disproportionate amount of elements in the table of $!n\pmod{n+2}$ are multiples of $3$: $56\%$, contrasted to the expected $33\%$.

Proportion of !n (mod n+2) that are multiples of 3

This trend continues: there's no single $k\leq1000$ for which there are less than the expected $\frac1{k+1}$ from the first $\require{cancel}\cancel{5000}$ $50000$ values of $!n\pmod{n+k}$ that are multiples of $k+1$. Looking at the data, I'd even argue that the trend gets more pronounced the farther you go. Here's a Pastebin with my data [edit: and with the predicted data from Haran's answer].

My question:

Why does this pattern hold? Why is $!n\pmod{n+k}$ a multiple of $k+1$ so much more often than it would be by chance? And where do these percentages come from?

$\endgroup$
  • 2
    $\begingroup$ +1 very interesting question $\endgroup$ – Lucas Henrique Dec 27 '19 at 3:57
11
$\begingroup$

Here is a table of the first few derangement values: $$ \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} $$

First, we can observe that all odd inputs of $n$ are giving even outputs while all even inputs of $n$ are giving odd outputs. This can be justified using induction. It clearly works for the first few cases from the above table. Now, by induction hypothesis, $!n+!(n-1) \equiv 1 \pmod{2}$ which shows that $!(n+1) \equiv n \pmod{2}$ which shows that odd inputs give even outputs while even inputs give odd outputs.

For all odd values of $n$, we can see that $!n$ and $n+1$ are even which shows that the residue $!n \pmod{n+1}$ is also even. Thus, we have already acquired $50\%$ of the multiples of $2$. On the other hand, for even values of $n$, it seems like there is a $50\%$ chance of the least residue being odd or even, as expected. This gives us an expected ratio of $50\%+\frac{1}{2}(50\%)=75\%$ of even least residues which agrees with your data.

For modulo $3$, you can observe that $!n \pmod{3}$ is $0,1,2,0,2,1 \pmod{3}$ based on $n \pmod{6}$. As our formula is based on recursion, it is easy to see that similar to the above case, we can evaluate $!n \pmod{3}$ using $n \pmod{6}$. Again, like the above case, whenever $n \equiv 1,4 \pmod{6}$ i.e. whenever $n \equiv 1 \pmod{3}$, we have $!n \equiv 0 \pmod{3}$. Thus, the least residue of $!n \pmod{n+2}$ will be divisible by $3$. This is $1$ out of every $3$ cases. That gives an expected ratio of $\frac{1}{3}(100\%)+\frac{2}{3}(33.33\%)=55.55\%$, agreeing with your data.

We would like to show that in general, $!n \equiv 0 \pmod{m}$ for $n\equiv 1 \pmod{m}$. This holds for base case $n=1$ as $!1=0$. We can use the summation formula for derangements to prove this easily- $$!(qm+1)=(qm+1)!\sum_{i=0}^{qm+1} \frac{(-1)^i}{i!}$$ We only need to consider the last two terms as the rest of the terms are divisible by $qm$. So- $$!(qm+1) \equiv (qm+1)(-1)^{qm}+(-1)^{qm+1} \equiv (-1)^{qm}+(-1)^{qm+1} \equiv 0 \pmod{m}$$

We have proved our hypothesis that if $n \equiv 1 \pmod{m}$ then $!n \equiv 0 \pmod{m}$. When we take $!n \pmod{n+k}$ and check its value $\pmod{k+1}$, if $\gcd(k+1,n+k)=1$, we can always expect equal chance for all values $\pmod{k+1}$. So, if $k+1$ is prime, we would expect the expected ratio to be- $$\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}$$

which agrees with values such as $k=1,2,4,6$ where $k+1$ is prime.

When $k+1=\prod_{i=1}^tp_i^{a_i}$ is composite, we cannot always say that $\gcd(k+1,n+k)=1$. Thus, we must check for all possible $\gcd$ values. If we have $\gcd(k+1,n+k)=\prod_{i=1}^tp_i^{b_i}$, we have $n \equiv 1 \pmod{\prod_{i=1}^tp_i^{b_i}}$ and $n+k \equiv 0 \pmod{\prod_{i=1}^tp_i^{b_i}}$. This $\gcd$ is seen for $\phi(\prod_{i=1}^tp_i^{a_i-b_i})$ cases. Moreover, we must also have divisibility by $\prod_{i=1}^tp_i^{a_i}$ given divisibility by $\prod_{i=1}^tp_i^{b_i}$, which happens with a chance of $1$ in $\prod_{i=1}^tp_i^{a_i-b_i}$. Thus our expected value is: $$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)$$

Thus, we conclude that for $k+1=\prod_{i=1}^tp_i^{a_i}$, the expected value (in fraction) is: $$E=\frac{1}{k+1} \cdot \prod_{i=1}^t \bigg(1+\frac{p_i-1}{p_i} \cdot a_i\bigg)$$

This seems to agree with all values of $k$ settling the problem.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think this interprets the phenomenon pretty well. Great job! $\endgroup$ – URL Dec 27 '19 at 7:17
  • $\begingroup$ @URL I have completed my answer. The formula below gives you the expected value for any $k$. I have checked for a few values whether it agrees with your data. The answer looks promising. You could check for all the $k$ values with a program if you want (because I have no idea how to check). $\endgroup$ – Haran Dec 27 '19 at 7:38
  • $\begingroup$ @URL Could you join me in chat? chat.stackexchange.com/rooms/102606/room-for-haran-and-url $\endgroup$ – Haran Dec 27 '19 at 7:51
3
$\begingroup$

Possible explanation for $k=1$ case:

It is easy to prove that $!n$ is even iff $n$ is odd. For such $n$, the expression $!n \pmod{n+1}$ means you're dividing an even number by another even number - the remainder must therefore be even. (I assume you count a remainder of $0$ as even / a multiple of $2$.)

Therefore, every odd $n$ satisfies your condition. I have no idea if even $n$ values satisfy your condition, but if those behave randomly, you'd get approximately half the even $n$ values, plus all the odd $n$ values, to satisfy your condition. This would make up a proportion of $3/4$, very close to your observed $76\%$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.