Derangements, finding best possible $k$

Question

I have to find the best possible $k\in\mathbb{N}$ such that for all sufficiently big $n\in\mathbb{N}$ less than $1$% of all permutations $[n]$ have at least $k$ fixed points.

---

I don't really understand the question to be honest. I already showed that $D(n)=n! \sum_{k=0}^n \frac{(-1)^k}{k!}$ and $\sum_{k=0}^\infty \frac{(-1)^k}{k!}=\frac{1}{e}$

Answer 1

Let $S_n$ be a uniform random permutation in $\mathfrak{S}_n$. Call $F_n$ the number of fixed points of $S_n$. The distribution of $F_n$ can be computed explicitely by enumerating the permutations in $\mathfrak{S}_n$ having exactly $k$ fixed point: for every integer $k \in [0,n]$, $$\mathbb{P}[F_n=k] = \frac{{n \choose k}D(n-k)}{n!} = \frac{D(n-k)}{k!(n-k)!}.$$ Hence, for every $k \in \mathbb{N}$, $\mathbb{P}[F_n=k] \to e^{-1}\frac{1}{k!}$ as $n \to +\infty$: in other words, the distribution of $F_n$ converges to Poisson law with parameter 1.

Hence for every $k \in \mathbb{N}^*$,
$$P[F_n \le k-1] \to \sum_{\ell=0}^{k-1} e^{-1}\frac{1}{\ell!}.$$ If you find the integer $k \ge 2$ such that $$\sum_{\ell=0}^{k-2} e^{-1}\frac{1}{\ell!} < 0,99 < \sum_{\ell=0}^{k-1} e^{-1}\frac{1}{\ell!},$$ you are done.

Answer 2

The number of permutations of $[n]$ with $k$ fixed points is given by:

$$R_{n}(k) = \binom{n}{k}D_{n-k}$$

Where $D_{n}$ is the number of derangements of $n$. For $n - k >> 0$, $D_{n-k} \approx \frac{(n-k)!}{e}$. Thus:

$$R_{n}(k) \approx \frac{n!}{k!(n-k)!}\cdot\frac{(n-k)!}{e} = \frac{n!}{e\cdot k!}$$

For the condition in your problem to be satisfied, we need:

$$\sum_{i = 0}^{k-1}R_{n}(i)> \frac{99}{100}n!$$

In other words, we want to find the smallest $k$ such that more than $99\%$ of the permutations have less than $k$ fixed points. Simplifying:

$$\sum_{i=0}^{k-1}R_{n}(i) = \sum_{i=0}^{k-1}\frac{n!}{e\cdot i!} = \frac{n!}{e}\sum_{i=0}^{k-1}\frac{1}{i!}>\frac{99}{100}n!$$

$$\sum_{i=0}^{k-1}\frac{1}{i!}>\frac{99}{100}e$$

Since $\displaystyle\sum_{i=0}^{\infty}\frac{1}{i!} = e$, this question is really asking about how fast the infinite series converges! In this case, we find that the smallest possible $k$ is $\boxed{5}$.