# Probability that a random permutation has no fixed point among the first $k$ elements

Is it true that $\frac1{n!} \int_0^\infty x^{n-k} (x-1)^k e^{-x}\,dx \approx e^{-k/n}$ when $k$ and $n$ are large integers with $k \le n$?

This quantity is the probability that a random permutation of $n$ elements does not fix any of the first $k$ elements.

-
My few tries on mathematica seem to suggest it is correct. – picakhu Dec 20 '10 at 7:05
Fix $a\in(0,1)$. If $k$ and $n$ go to infinity with $k/n\to a$, Mike's equivalent of $S_{n,k}/n!$ implies that the limit you asked for is $(2-a)/\mathrm{e}$ (I think). On the other hand, Shai's answer implies that this limit is $\mathrm{e}^{-a}$. You accepted Shai's answer and also agreed with the part of Mike's answer which yields the limit $(2-a)/\mathrm{e}$. How is this possible? Which answer do you think is correct? – Did Mar 6 '11 at 12:38

Here's a heuristic idea, based on the strong law of large numbers (SLLN). A rigorous proof can be made using the central limit theorem (CLT), as in my new answer.

First write $$I = \frac{1}{{n!}}\int_0^\infty {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} = \int_0^\infty {\bigg(1 - \frac{1}{x}} \bigg)^k \frac{{x^n e^{ - x} }}{{\Gamma (n + 1)}}\,{\rm d}x.$$ Now, if $X_1,\ldots,X_{n+1}$ are i.i.d. exponential(1) random variables, then their sum $X_1 + \cdots + X_{n+1}$ has gamma density $x^n e^{-x} / \Gamma(n+1)$, $x > 0$. Hence, $$I = {\rm E} \bigg[ 1 - \frac{1}{{X_1 + \cdots + X_{n + 1} }}\bigg]^k = {\rm E}\bigg[1 - \frac{{n + 1}}{{X_1 + \cdots + X_{n + 1} }}\frac{1}{{n + 1}}\bigg]^k .$$ By SLLN, $(n + 1)^{ - 1} \sum\nolimits_{i = 1}^{n + 1} {X_i }$ converges almost surely to ${\rm E}[X_1 ] = 1$ as $n \to \infty$. So this suggests the approximation $$I \approx \bigg(1 - \frac{1}{{n + 1}}\bigg)^k = \bigg(1 - \frac{1}{{n + 1}}\bigg)^{n(k/n)} \approx e^{ - k/n}.$$

-

A rigorous proof can be made using the central limit theorem (CLT), as follows.

Since $$\frac{1}{{n!}}\int_0^1 {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} \to 0$$ as $n \to \infty$, it suffices to consider the integral from $1$ to $\infty$. Let $c>0$ be arbitrary but fixed, and let $X_i$ be as in my previous answer. Define $f_n {(x)} = x^n e^{-x} / \Gamma(n+1)$, $x>0$, and put $n'=n+1$. Then, since $f_n$ is the density of $\sum\nolimits_{i = 1}^{n'} {X_i }$, $$\frac{1}{{n!}}\int_1^{n' - c\sqrt {n'} } {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} \leq \int_0^{n' - c\sqrt {n'} } {f_n (x)\,{\rm d}x} = {\rm P}\bigg(\frac{{\sum\nolimits_{i = 1}^{n'} {X_i } - n'}}{{\sqrt {n'} }} \le - c \bigg).$$ By the CLT, since the $X_i$ have unit mean and unit variance, the probability on the right-hand side tends to $\Phi(-c)$ as $n \to \infty$, where $\Phi$ denotes the distribution function of the standard normal distribution. Similarly, $$\frac{1}{{n!}}\int_{n' + c\sqrt {n'} }^\infty {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} \leq \int_{{n'} + c\sqrt {n'} }^\infty {f_n (x)\,{\rm d}x} = {\rm P}\bigg(\frac{{\sum\nolimits_{i = 1}^{n'} {X_i } - n'}}{{\sqrt {n'} }} > c \bigg),$$ and, by the CLT, the probability on the right-hand side tends to $1 - \Phi(c)$ as $n \to \infty$. Next, note that $$\bigg(1 - \frac{1}{{n' - c\sqrt {n'} }}\bigg)^k \int_{n' - c\sqrt {n'} }^{n' + c\sqrt {n'} } {f_n (x)\,{\rm d}x} \leq \frac{1}{{n!}}\int_{n' - c\sqrt {n'} }^{n' + c\sqrt {n'} } {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x}$$ and $$\frac{1}{{n!}}\int_{n' - c\sqrt {n'} }^{n' + c\sqrt {n'} } {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} \leq \bigg(1 - \frac{1}{{n' + c\sqrt {n'} }}\bigg)^k \int_{n' - c\sqrt {n'} }^{n' + c\sqrt {n'} } {f_n (x)\,{\rm d}x}.$$ By the CLT, $$\int_{n' - c\sqrt {n'} }^{n' + c\sqrt {n'} } {f_n (x)\,{\rm d}x} = {\rm P}\bigg(-c \leq \frac{{\sum\nolimits_{i = 1}^{n'} {X_i } - n'}}{{\sqrt {n'} }} \leq c \bigg) \to 2 \Phi(c) -1$$ as $n \to \infty$. Combining it all, and noting that $$\bigg(1 - \frac{1}{{n' \pm c\sqrt {n'} }}\bigg)^k = \bigg(1 - \frac{1}{{n' \pm c\sqrt {n'} }}\bigg)^{n(k/n)} \approx e^{ - k/n},$$ the result follows by choosing $c$ sufficiently large. [Note that first we choose $c$ sufficiently large, then we let $n \to \infty$.]

-
Fix $a\in(0,1)$. If $k$ and $n$ go to infinity with $k/n\to a$, Mike's equivalent of $S_{n,k}/n!$ implies that the limit asked by the OP is $(2-a)/\mathrm{e}$ (I think). On the other hand, your answer implies that this limit is $\mathrm{e}^{-a}$. Which one is correct? – Did Mar 6 '11 at 12:34
@Didier: I'll check this, and let you know (hopefully today). – Shai Covo Mar 6 '11 at 13:19
@Didier: I confirmed my answer using WolframAlpha and Wims Function Calculator. – Shai Covo Mar 6 '11 at 16:54
Great. See my comment to Mike's post. – Did Mar 7 '11 at 13:22

Update: This argument only holds for some cases. See italicized additions below.

Let $S_{n,k}$ denote the number of permutations in which the first $k$ elements are not fixed. I published an expository paper on these numbers earlier this year. See "Deranged Exams," (College Mathematics Journal, 41 (3): 197-202, 2010). Aravind's formula is in the paper, as are several others involving $S_{n,k}$ and related numbers.

Theorem 7 (which I also mention in this recent math.SE question) is relevant to this question. It's $$S_{n+k,k} = \sum_{j=0}^n \binom{n}{j} D_{k+j},$$ where $D_n$ is the number of derangements on $n$ elements. See the paper for a simple combinatorial proof of this.

Since $D_n$ grows as $n!$ via $D_n = \frac{n!}{e} + O(1)$ (see Wikipedia's page on the derangement numbers), and if $k$ is much larger than $n$, the dominant terms in the probability $\frac{S_{n+k,k}}{(n+k)!}$ are the $j = n$ and $j = n-1$ terms from the Theorem 7 expression. Thus we have $$\frac{S_{n+k,k}}{(n+k)!} \approx \frac{D_{n+k} + n D_{n+k-1}}{(n+k)!} \approx \frac{1}{e}\left(1 + \frac{n}{n+k}\right) \approx e^{-1} e^{\frac{n}{n+k}} = e^\frac{-k}{n+k},$$ where the second-to-last step uses the first two terms in the Maclaurin series expansion for $e^x$.

Again, this argument holds only for (in my notation) $k$ much larger than $n$.

-
I agree with everything except $1 + \frac{n}{n+k} \approx e^{\frac{n}{n+k}}$, which doesn't hold because $\frac{n}{n+k}$ is not close to 0. – Dave Radcliffe Dec 23 '10 at 4:26
@Dave R: I've thought about this for the past couple of hours and almost posted a more precise estimate, but I think the simplest way past the difficulty really is that my argument works unless $n$ is large relative to $k$ (which would make $\frac{n}{n+k} \approx 1$). But if this is the case, then Hans Lundmark's answer (in my notation) shows that the probability is approximately $1 - \frac{k}{n+k} \approx e^{\frac{-k}{n+k}}$. So I think between my answer and Hans's you have the argument you need. (And I will now upvote Hans's and Aravind's answers accordingly.) – Mike Spivey Dec 23 '10 at 7:08
@Mike Fix $a\in(0,1)$. If $k$ and $n$ go to infinity with $k/n\to a$, your equivalent of $S_{n,k}/n!$ implies that the limit asked by the OP is $(2-a)/\mathrm{e}$ (I think). On the other hand, Shai's answer implies that this limit is $\mathrm{e}^{-a}$. Which one is correct? – Did Mar 6 '11 at 12:34
@Didier: Good question. Let me think about it. – Mike Spivey Mar 6 '11 at 14:13
@Didier: With your comment and the OP's I'm realizing that my argument only applies for certain values of $n$ and $k$. In my notation, we need $k$ to remain much larger than $n$ in order to have the approximation $1 + \frac{n}{n+k} \approx e^{\frac{n}{n+k}}$ be a good one. So one can't hold that ratio you mention constant and then use my argument to get an accurate limiting value. I haven't checked Shai's work myself, but if I had to choose between $(2-a)/e$ and $e^{-a}$ for the limiting value, I would go with the latter. – Mike Spivey Mar 7 '11 at 3:42

This is not an answer but an observation that the quantity is equal to $\sum_{i=0}^{k} \frac{{(-1)}^i}{n!}{k \choose i}(n-i)!$.

-

Continuing Aravind's observation, write it like $$1 - \frac{k}{n} + \frac{1}{2!} \left( \frac{k}{n} \right)^2 \frac{1-1/k}{1-1/n} - \frac{1}{3!} \left( \frac{k}{n} \right)^3 \frac{(1-1/k)(1-2/k)}{(1-1/n)(1-2/n)}$$ $$+ \dots + (-1)^k \frac{1}{k!} \left( \frac{k}{n} \right)^k \frac{(1-1/k)(1-2/k)\dots (1-(k-1)/k)}{(1-1/n)(1-2/n) \dots (1-(k-1)/n)}.$$ If $k$ and $n$ are large, this seems to be close to the $k$th degree Maclaurin polynomial for $e^z$ evaluated at $z=-k/n$ (although I don't have an estimate of the error).

-