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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze