Princíp zapojenia a vypojenia
Z Wikipédie
V kombinatorike princíp zapojenia a vypojenia alebo aj princíp exklúzie a inklúzie hovorí, že ak A1, ..., An sú konečné množiny, tak
kde |A| označuje kardinalitu množiny A. Názov pochádza z prípadu pre n=2, kde mohutnosť zjednotenia dvoch množín získame súčtom mohutností oboch množín (zapojením) a odpočítaním mohutnosti ich prieniku (vypojením).
Objavenie princípu zapojenia a vypojenia sa pripisuje Abrahamovi de Moivrovi, niekedy sa tiež nazýva po Jozephovi Sylvestrovi a Henrim Poincarém.
Jeden z dôkazov princípu zapojenia a vypojenia je takýto: nech x je ľubovoľný prvok zjednotenia . Do súčtu
tento prvok prispieva jednotkou. Nech x sa vyskytuje v t množinách z A1, ..., An. Potom na pravej strane prispieva číslom
, čo je tiež 1 (napr. podľa binomickej vety).
Princíp zapojenia a vypojenia sa niekedy uvádza v podobe, ktorá hovorí, že ak
potom
V takejto forme ho možno vidieť ako Möbiusov inverzný vzorec pre incidenčnú algebru čiastočne usporiadanej množiny všetkých podmnožín množiny A.
Vynechaním niekoľkých posledných členov pravej strany rovnosti vo vzorci je možné získať alternujúco horné a dolné odhady ľavej strany, čo môže byť užitočné, ak výpočet celej pravej strany je náročný.
Pravdepodobne najznámejšou aplikáciou princípu zapojenia a vypojenia je však riešenie kombinatorického problému počítania všetkých permutácií konečnej množiny, ktoré nemajú žiaden pevný bod, známy aj ako problém šatniarky či problém vyhodených klobúkov. Hovoríme, že permutácia σ má pevný bod, ak existuje také i, že σ(i) = i. Pomocou princípu exklúzie a inkúzie je možné dokázať, že mohutnosť tejto množiny permutácií bez pevného bodu n-prvkovej konečnej množiny konverguje pre veľké n
kde [x] označuje najbližšie celé číslo.
Toto číslo je známe aj ako subfaktoriál čísla n, zapisovaného ako !n alebo ako n, za ktorým nasleduje symbol výkričníka otočeného naopak. Z toho celého vyplýva, že pravdepodobnosť, že náhodne vybraná permutácia nebude mať žiaden pevný bod konverguje k 1/e ako n rastie do nekonečna (e je Eulerovo číslo).
Princíp zapojenia a vypojenia sa veľmi často používa aj v teórii pravdepodobnosti pre výpočet pravdepodobnosti výskytu niektorej z viacerých udalostí:
[úprava] Pozri aj
- kombinatorické princípy
- Booleova nerovnosť
- dvojité vyčísľovanie
- Problém náhrdelníka
- Problém šatniarky