Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
1  
That's much easier! –  Yuval Filmus May 17 '11 at 0:53

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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