Number of fixed points in a random permuation

Task number: 3546

Consider a random permutation of \(n\) elements. Determine the expected value of the number of fixed points of such a permutation (i.e. the number of elements \(i\) such that \(\pi(i) = i\), if \(\pi\) is the random permutation).

  • Solution

    We introduce an indicator variable \(I_i\) indicatinng that \(i\) is a fixed point of the permutation.

    We have \(EI_i=P(\pi(i)=i)=\frac{(n-1)!}{n!}=\frac{1}{n}\).

    From there, \(EX=EI_1+…+EI_n=1\).

  • Answer

    In the average case a random permutation will contain one fixed point.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Complex task
Cs translation
Send comment on task by email