4
$\begingroup$

Let $p_{n,k}$ be the probability that a random permutation from $S_n$, the symmetric group of order $n!$, has exactly $k$ fixed points. I am trying to compute $\lim _{n\to \infty}p_{n,k}$. After playing with it a bit, I am relatively confident the limit is $\frac{1}{k!}$, although I have yet to come up with a proof.

Here's what I've tried so far. If $a_{n,k}$ is the number of elements of $S_n$ with $k$ fixed points, then we have that

$ a_{n,k}=\binom{n}{k}a_{n-k,0} $

That is, there are $\binom{n}{k}$ ways to choose $k$ fixed points, and after those are chosen, there are $a_{n-k,0}$ to permute the remaining $n-k$ elements with $0$ fixed points. After computing $a_{n,0}$ by hand for small values of $n$, I was able to look up the recursion formula $a_n=na_{n-1}+(-1)^n$ from oeis.org. Using this, I was able to come up with my "guess" of $\frac{1}{k!}$, but this direction doesn't seem to be leading me towards finding a proof.

Any ideas how to proceed? Group theory is not my strong point, so I would not be surprised if there is a result that makes this problem almost trivial. A pointer to any such results would be excellent.

2 Answers 2

5

Here's a different take that continues along the lines you've already been going. Use a different formula for $a_{n,0}$ from the OEIS; use $a_{n,0} = n! \sum_{j=0}^n \frac{(-1)^j}{j!}.$ This is a well-known formula for $a_{n,0}$ (the derangement numbers) and can be proved using inclusion-exclusion. (Added: You might also want to look at the proof and general argument given by Qiaochu Yuan in his answer to a similar question.)

As $n \to \infty$, the sum in the expression for $a_{n,0}$ approaches $e^{-1}$. With this and your expression $a_{n,k} = \binom{n}{k} a_{n-k,0}$, you're almost to the correct answer of $e^{-1}/k!$ as given by Yuval Filmus.

  • 1
    That's much easier!2011-05-17
6

The number of fixed points is roughly Poisson, so the correct probability is $e^{-1}/k!$. You should be able to derive this using an appropriate inclusion-exclusion formula.

First go over all $k$-sets and sum the probabilities of having fixed point there - in the limit this part contributes $1/k!$. Every $(k+1)$-set was counted $k+1$ times instead of $0$, so remove $k+1$ times the contribution of all $(k+1)$-sets - this part contributes $(k+1) \cdot -1/(k+1)! = -1/k!$ in the limit. Every $(k+2)$-set is now counted $\binom{k+2}{2} - (k+2)\cdot (k+1) = -\binom{k+2}{2}$ times instead of $0$, so add $\binom{k+2}{2}$ times the contribution of all $(k+2)$-sets - this part contributes $\binom{k+2}{2} \cdot 1/(k+2)! = 1/2k!$ in the limit. Continuing the pattern, we get $ \frac{1}{k!} \left( 1 - 1 + \frac{1}{2} - \frac{1}{6} + \cdots \right) = \frac{e^{-1}}{k!}. $ I'll let you work out the details.