Derrangements

Consider a permutation \sigma of [n], and let X^n_j be the random variable that takes the value 1 if this permutation fixes j, and takes the value zero elsewhen. Set X_n= \sum X_n^j.

  1. Express P(X_n=k) in terms of P(X_m=0) for a suitable m.
  2. Find P(X_n >0), and hence find P(X_n=0).
  3. Find P(X_n=0) as n\to\infty, and deduce that X_n converges in distribution to a Poission variable. Of what weight?
Advertisements
Derrangements