Načelo vključitev in izključitev je v kombinatoriki, veji matematike, preštevalna tehnika, ki posploši pogosto metodo pridobivanja števila elementov unije dveh končnih množic. S simboli se to zapiše:

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|\!\,,}$

kjer sta A in B dve končni množici, |S| pa označuje kardinalnost množice S (ki se lahko pri končni množici obravnava kot število elementov). Formula izraža dejstvo, da je včasih vsota elementov dveh množic prevelika, saj se je lahko nekaj elementov štelo dvakrat. Ti elementi se nahajajo v preseku dveh množic. Izračun se popravi z odštevanjem velikosti preseka.

Načelo se veliko bolje vidi na primeru treh množic, ki je za tri množice A, B in C podano s:

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\!\,.}$

Ta formula se lahko potrdi s tem, da se prešteje kolikokrat se je preštelo vsako območje Vennovega diagrama na desni strani formule. V tem primeru, ko se odstrani prevečkrat štete elemente, je treba nazaj prišteti, saj sse je odštelo prevečkrat.

Rezultate zgornjih primerov, ki so se podali za razlago načela vključitev in izključitev, se sedaj posploši. Da se najde kardinalnost unije n množic:

1. se vključi kardinalnost vseh množic.
2. izključi se kardinalnosti presekov med pari.
3. vključi se kardinalnosti presekov med trojicami.
4. izključi se kardinalnosti presekov med četvericami.
5. vključimo se kardinalnosti presekov med petimi množicami.
6. se nadaljuje, dokler se ne vključi (če je n lih) ali izključi (če je n sod) kardinalnosti presekov med n množicami.

Ime prihaja iz zamisli, da načelo temelji na pretiranem vključevanju, ki mu sledi pretirano izključevanje. Koncept je zasnoval Abraham de Moivre leta 1718,^[1] toda v delu se je prvič pojavilo pri matematiku Danielu da Silvi leta 1854,^[2] kasneje pa v delu Jamesa Josepha Sylvestra leta 1883.^[3] Zaradi te uporabe se včasih formulo pripisuje Da Silvi ali Sylvestru. Načelo je primer metode sita, ki se zelo uporablja v teoriji števil in se včasih navede kot formula sita,^[3] toda Legendre je že uporabil podobno napravo v kontekstu sita leta 1808.

V svoji splošni obliki, načelo vključitev in izključitev za končne množice A₁, ..., A_n pravi:

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|+\sum _{1\leqslant i<j<k\leqslant n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.}$

(1)

To se lahko zapiše kot:

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)\!\,,}$

ali:

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,\ldots ,n\}}(-1)^{|J|+1}\left|\bigcap _{j\in J}A_{j}\right|\!\,.}$

Drugače rečeno z besedami: če se želi prešteti število elementov v končni uniji končnih množic, je treba najprej sešteti vse kardinalnosti posameznih množic, potem odšteti število elementov, ki se pojavijo v najmanj dveh množicah, nato je treba prišteti število elementov, ki se pojavijo v najmanj treh množicah in odšteti število elementov, ki se pojavijo v najmanj štirih množicah ter tako naprej. Ta proces se vedno konča, saj na koncu ni več elementov, ki bi se pojavili v več množicah, kot jih je v uniji množic. (Na primer za ${\displaystyle n=4\!\,}$ ne more biti nobenih elementov več, ki bi se pojavili v več kot ${\displaystyle 4\!\,}$ množicah; enako ne more biti več elementov, ki bi se pojavili v najmanj ${\displaystyle 5\!\,}$ množicah.)

V uporabi je pogosto, da je načelo izraženo v komplementarni obliki. Naj bo S končna univerzalna množica, ki vsebuje vse A_i in naj bo ${\displaystyle {\bar {A_{i}}}}$ komplement od A_i v S. Po De Morganovih zakonih se dobi:

${\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|\!\,.}$

Naslednja različica izreka je taka: naj bodo P₁, ..., P_n značilnosti, ki jih elementi iz S lahko imajo ali pa ne. Po tem načelo vključitev in izključitev poda način izračuna števila elementov iz S, ki nimajo nobene izmed teh značilnosti. Naj bo A_i podmnožica elementov iz S, ki imajo značilnost P_i, uporabi pa se načelo v svoji komplementarni obliki. To različico odkril Sylvester.^[1]

Če se vzame le prvih m<n vsot na desni (v splošni obliki načela), potem bo rešitev prevelika, če je m lih in premajhen, če je m sod.

Kot preprost primer načela vključitve in izključitve, sledi naslednje vprašanje:^[2]

Koliko naravnih števil iz {1,...,100} ni deljivih z 2, 3 ali 5?

Naj bo S = {1,...,100} in P₁ značilnost, da je naravno število deljivo z 2, P₂ značilnost za deljivost s 3 in P₃ značilnost za deljivost s 5. Če je A_i podmnožica od S, katerih elementi imajo značilnost P_i, se dobi elementarno štetje: |A₁| = 50, |A₂| = 33 in |A₃| = 20. Obstaja 16 izmed teh naravnih števil, ki so deljiva s 6 in 10, ki so deljiva z 10 ter 5, ki so deljiva s 15. Na koncu so le 3 naravna števila, ki so deljiva s 30, torej je število vse naravnih števil, ki niso deljiva z 2, 3, ali 5 podano z:

100 − (50 + 33 + 20) + (16 + 10 + 6) - 3 = 26.

• kombinatorična načela
• Boolova neenakost
• problem ogrlice
• Schuette–Nesbittova formula
• identiteta maksimumov in minimumov

Ta članek vsebuje material iz principle of inclusion–exclusion na PlanetMath, ki ima licenco Creative Commons Attribution/Share-Alike License.