Zobrazenie zdroja stránky Princíp zapojenia a vypojenia

V [[kombinatorika|kombinatorike]] '''princíp zapojenia a vypojenia''' alebo aj '''princíp exklúzie a inklúzie''' hovorí, že ak ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub> sú konečné [[množina|množiny]], tak

:<math>\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|</math><math>+\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}|</math>

kde |''A''| označuje [[mohutnosť (množina)|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 [[Abraham de Moivre|Abrahamovi de Moivrovi]], niekedy sa tiež nazýva po [[Joseph Sylvester|Jozephovi Sylvestrovi]] a [[Henri Poincaré|Henrim Poincarém]].
[[Súbor:Inclusion-exclusion.png|thumb|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 <math>\bigcup_{i=1}^n A_i</math>. Do súčtu <math>\left|\bigcup_{i=1}^n A_i\right|</math> tento prvok prispieva jednotkou. Nech ''x'' sa vyskytuje v ''t'' množinách z ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub>. Potom na pravej strane prispieva číslom
:<math>t-{t\choose 2}+{t\choose 3}-\cdots (-1)^{n+1}{t\choose n}</math>, čo je tiež 1 (napr. podľa [[binomická veta|binomickej vety]]).

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

:<math>g(A)=\sum_{S\,:\,S\subseteq A}f(S)</math>

potom

:<math>f(A)=\sum_{S\,:\,S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)</math>

V takejto forme ho možno vidieť ako [[Möbiusov inverzný vzorec]] pre [[incidenčná algebra|incidenčnú algebru]] [[čiastočne usporiadaná množina|č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ácia|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 <math>\sigma</math> má pevný bod, ak existuje také ''i'', že <math>\sigma(i)=i</math>. 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''

:<math>\left [ \frac {n!}{e} \right ]</math>

kde [x] označuje [[najbližšie celé číslo]].

Toto číslo je známe aj ako [[subfaktoriál]] čísla ''n'', zapisovaného ako <math>!n</math> 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čno|nekonečna]] (e je [[Eulerovo číslo]]).

Princíp zapojenia a vypojenia sa veľmi často používa aj v [[pravdepodobnosť|teórii pravdepodobnosti]] pre výpočet pravdepodobnosti výskytu niektorej z viacerých udalostí:

:<math>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)</math><math>+\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)</math>

== Pozri aj ==

* [[kombinatorické princípy]]
* [[Booleova nerovnosť]]
* [[dvojité vyčísľovanie]]
* [[Problém náhrdelníka]]
* [[Problém šatniarky]]

[[Kategória:Kombinatorika]]