Princíp zapojenia a vypojenia

V kombinatorike princíp zapojenia a vypojenia alebo aj princíp exklúzie a inklúzie hovorí, že ak A₁, ..., A_n sú konečné množiny, tak

\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,i<j}\left|A_{i}\cap A_{j}\right|

+\sum _{i,j,k\,:\,i<j<k}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \cdots \ +(-1)^{n}\left|A_{1}\cap \cdots \cap A_{n}\right|=\sum _{k=1}^{n}\sum _{1\leq i_{1}<\ldots <i_{k}\leq n}(-1)^{k+1}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|

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.

Prípad troch množín A, B a C princípu exklúzie a inklúzie.

Jeden z dôkazov princípu zapojenia a vypojenia je takýto: nech x je ľubovoľný prvok zjednotenia $\bigcup _{i=1}^{n}A_{i}$ . Do súčtu $\left|\bigcup _{i=1}^{n}A_{i}\right|$ tento prvok prispieva jednotkou. Nech x sa vyskytuje v t množinách z A₁, ..., A_n. Potom na pravej strane prispieva číslom

t-{t \choose 2}+{t \choose 3}-\cdots (-1)^{n+1}{t \choose n}

, čo je tiež 1 (napr. podľa binomickej vety).

Princíp zapojenia a vypojenia sa niekedy uvádza v podobe, ktorá hovorí, že ak

g(A)=\sum _{S\,:\,S\subseteq A}f(S)

potom

f(A)=\sum _{S\,:\,S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)

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 $\sigma$ má pevný bod, ak existuje také i, že $\sigma (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

\left[{\frac {n!}{e}}\right]

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

P\left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{i=1}^{n}P\left(A_{i}\right)-\sum _{i,j\,:\,i\neq j}P\left(A_{i}\cap A_{j}\right)

+\sum _{i,j,k\,:\,i\neq j\neq k\neq i}P\left(A_{i}\cap A_{j}\cap A_{k}\right)-\ \cdots \cdots \ \pm P\left(\bigcap _{i=1}^{n}A_{i}\right)

Princíp zapojenia a vypojenia

Pozri aj