Fix some n. Suppose we choose a permutation on n elements uniformly and at random. What is its average number of fixed points?
Group theory classes usually have some convoluted argument which establishes this result -- usually using the fixed point formula for a finite group acting on a finite set. Here's a very simple probability theory argument.
Take some i. What is the probability that a randomly-chosen permutation fixes i? A little thought shows that it's 1/n -- for instance, you can just consider the symmetry. Define random variables:
- N = number of fixed points
- Ni = 1 if i is a fixed point, 0 otherwise.
Then N is the sum of all the Ni:
N = ∑i=1,...,n Ni.
The expected value of Ni is just the probability of i being a fixed point, or 1/n. Since expectation is linear, the average value of N is the sum of the average values of the Ni. This is a sum of n times 1/n, or just 1.
QED.
| 
