If we are given that a list of $n$ numbers has $11,660$ derangements, what is the value of $n$?

Question

The Full Question

For the positive integers $1,2,3,\dots n-1,n$, there are $11,660$ where $1,2,3,4,5$ appear in the first five positions. What is the value of $n$?

My Work

First I considered all derangements of the first $5$, this is just all the derangements of integers $1$ to $5$. Which is $44$. I'll say that $N = 44$ for the rest of the question. If we let $P$ represent all the derangments of the remaining $n-5$ numbers, then we clearly have $N\times P = 11,660 \iff 44P = 11,660 \implies P = \frac{11,660}{44} = 265$.

My Problem

It seems I have reduced it into a simple algebra exercise. However looking closely we have $P = 265 = (n-5)! - \binom{n-5}{1}[n-6]! + \binom{n-5}{2}[n-7]! - \binom{n-5}{3}[n-8]! + \cdots (-1)^{n-5}[0!]$ and we have to solve for $n$. I can't figure out a way how to solve for $n$ in this equation. Can anyone give me some help?

Answer 1

We can find $m=n-5$ by solving $d_m=265$, where $d_m$ is the number of derangements of an $m$-element set. There's perhaps two ways to go about this:

• Compute $d_i$ for $i=1,2,\ldots$ until you find $d_i=265$. There's recursive formulas for $d_m$ which make it easier, e.g.: $d_m=(m-1) \times (d_{m-1}+d_{m-2})$ and $d_1=0$ and $d_2=1$.

• Estimate that $m! \approx d_m \times e \approx 720$ and then deduce which $m!=720$. (This is perhaps less rigorous than the first approach, but you can check the answer is correct.)

Answer 2

The number of derangements of $n$ items is $\left[\dfrac{n!}{e}\right]$ where $[x]$ is rounding to the nearest integer to $x$

so you are trying to solve $\left[\dfrac{5!}{e}\right]\left[\dfrac{(n-5)!}{e}\right] = 11660$ or $(n-5)!\approx e^2 \dfrac{11660}{120} \approx 717.97$

and since $6!=720$ this means $n-5=6$ and thus $n=11$