Seminář PHP – Gymnázium Kolín

Úloha 29: Rozdělení pravděpodobnosti permutací (subfaktoriál)

Pokročilý subfaktoriál (!n) kombinatorika pravděpodobnost MathML

Cíl úlohy

Vytvořte skript, který pro zadaný počet n prvků spočítá rozdělení pravděpodobnosti, kolik prvků zůstane při náhodném seřazení na svém původním místě (počet pevných bodů permutace). Klasickým příkladem je anonymní degustace vzorků, šatnářka náhodně rozdávající kabáty nebo losování tajného Ježíška (Secret Santa).

Kombinatorická teorie a subfaktoriál (MathML)

1. Celkový počet všech možných seřazení n prvků je $n!$ .

2. Subfaktoriál $! m$ (derangement): Počet seřazení $m$ prvků tak, že žádný prvek nezůstane na svém původním místě, je dán rekurencí:

! 0 = 1,! 1 = 0,! m = (m - 1) \cdot (! (m - 1) +! (m - 2))

3. Počet způsobů, jak vybrat právě k prvků na správném místě a zbytek $n - k$ prvků na nesprávném místě:

P_{k} = (\binom{n}{k}) \cdot! (n - k) P (X = k) = \frac{(\binom{n}{k}) \cdot! (n - k)}{n!}

Úvahy: Matematika vs. Hrubá síla (Brute Force)

Proč nepoužít hrubou sílu? Pro $n = 10$ existuje 3,6 milionu permutací. Pro $n = 20$ je to už $2,4 \cdot 10^{18}$ možností! Hrubou silou by počítač počítal tisíce let.
Kombinatorický přístup: Díky vzorcům subfaktoriálu a kombinačních čísel spočítáme výsledek pro $n = 20$ v PHP za méně než 1 milisekundu!

Doplňující otázky k zamyšlení a náměty na rozšíření

1. K jaké hodnotě konverguje pravděpodobnost, že nikdo netrefí svůj kabát ( $k = 0$ ), když $n \to \infty$ ? (K hodnotě $\frac{1}{e} \approx 36,7879 %$ , kde $e$ je Eulerovo číslo!).
2. Jaká je střední hodnota (očekávaný počet) správně trefených prvků bez ohledu na velikost n? (Překvapivě přesně 1!).

Vyzkoušejte funkční řešení: Otevřít vzorovou úlohu permutace.php