Princíp zapojenia a vypojenia

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 . 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  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í:

Kategória:Kombinatorika