Počet pevných bodů v náhodné permutaci
Úloha číslo: 3512
Mějme náhodnou permutaci \(n\) prvků. Určete střední hodnotu počtu pevných bodů takové permutace (tj. počet prvků \(i\) takových, že \(\pi(i) = i\), je-li \(\pi\) ona náhodná permutace).
Řešení
Zavedeme indikátor \(I_i\) značící, že \(i\) je pevný bod permutace.
Platí \(EI_i=P(\pi(i)=i)=\frac{(n-1)!}{n!}=\frac{1}{n}\).
Odtud \(EX=EI_1+…+EI_n=1\).
Odpověď
V průměrném případě bude náhodná permutace obsahovat jeden pevný bod.