Ogled vira Načelo vključitev in izključitev

[[Slika:Венов_дијаграм.svg|sličica|[[Vennov diagram]], ki prikazuje unijo množic ''A'' in ''B'', ki je vse ostalo, kar ni belo]]
'''Načelo vključitev in izključitev''' je v [[kombinatorika|kombinatoriki]], veji [[matematika|matematike]], [[štetje|preštevalna]] tehnika, ki posploši pogosto metodo pridobivanja števila elementov [[unija množic|unije]] dveh [[končna množica|končnih množic]]. S simboli se to zapiše:

: <math> |A \cup B| = |A| + |B| - |A \cap B| \!\, , </math>

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 [[presek množic|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:

: <math>|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \!\, . </math>

Ta formula se lahko potrdi s tem, da se prešteje kolikokrat se je preštelo vsako območje [[Vennov diagram|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.
[[Slika:Inclusion-exclusion.svg|sličica|Načelo vključitev in izključitev na Vennovem diagramu za tri množice]]
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]] {{Mvar|n}} množic:

# se vključi kardinalnost vseh množic.
# izključi se kardinalnosti presekov med pari.
# vključi se kardinalnosti presekov med trojicami.
# izključi se kardinalnosti presekov med četvericami.
# vključimo se kardinalnosti presekov med petimi množicami.
# se nadaljuje, dokler se ne vključi (če je {{Mvar|n}} lih) ali izključi (če je {{Mvar|n}} sod) kardinalnosti presekov med {{Mvar|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,{{r|robe_2009}} toda v delu se je prvič pojavilo pri matematiku [[Daniel da Silva (matematik)|Danielu da Silvi]] leta 1854,{{r|mazu_2010}} kasneje pa v delu [[James Joseph Sylvester|Jamesa Josepha Sylvestra]] leta 1883.{{r|vanl_1992}} Zaradi te uporabe se včasih formulo pripisuje Da Silvi ali Sylvestru. Načelo je primer [[teorija sita|metode sita]], ki se zelo uporablja v [[teorija števil|teoriji števil]] in se včasih navede kot ''formula sita,''{{r|vanl_1992}} toda [[Adrien-Marie Legendre|Legendre]] je že uporabil podobno napravo v kontekstu sita leta 1808.

== Izrek ==

V svoji splošni obliki, načelo vključitev in izključitev za končne množice {{Matematična formula|''A''<sub>1</sub>, ..., ''A<sub>n</sub>''}} pravi:{{NumBlk|:|<math>\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|.</math>|{{EquationRef|1}}}}
[[Slika:Inclusion-exclusion-3sets.png|sličica|Vsak člen v formuli načelu vključitev in izključitev se postopoma popravi, dokler niso vsa območja Vennovega diagrama prešteta točno enkrat.]]
To se lahko zapiše kot:

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

ali:

: <math> \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| \!\, . </math>

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 <math> n = 4 \!\, </math> ne more biti nobenih elementov več, ki bi se pojavili v več kot <math> 4 \!\, </math> množicah; enako ne more biti več elementov, ki bi se pojavili v najmanj <math> 5 \!\, </math> množicah.)

V uporabi je pogosto, da je načelo izraženo v komplementarni obliki. Naj bo {{Mvar|S}} končna [[univerzalna množica]], ki vsebuje vse {{Matematična formula|''A<sub>i</sub>''}} in naj bo <math>\bar{A_i}</math> komplement od {{Matematična formula|''A<sub>i</sub>''}} v {{Mvar|S}}. Po [[De Morganovi zakoni|De Morganovih zakonih]] se dobi:

: <math> \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| \!\, . </math>

Naslednja različica izreka je taka: naj bodo {{Matematična formula|''P''<sub>1</sub>, ..., ''P<sub>n</sub>''}} značilnosti, ki jih elementi iz {{Mvar|S}} lahko imajo ali pa ne. Po tem načelo vključitev in izključitev poda način izračuna števila elementov iz {{Mvar|S}}, ki nimajo nobene izmed teh značilnosti. Naj bo {{Matematična formula|''A<sub>i</sub>''}} podmnožica elementov iz {{Mvar|S}}, ki imajo značilnost {{Matematična formula|''P<sub>i</sub>''}}, uporabi pa se načelo v svoji komplementarni obliki. To različico odkril Sylvester.{{r|robe_2009}}

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

== Zgledi ==

=== Štetje celih števil ===

Kot preprost primer načela vključitve in izključitve, sledi naslednje vprašanje:{{r|mazu_2010}}

: Koliko [[naravno število|naravnih števil]] iz {1,...,100} ni deljivih z 2, 3 ali 5?

Naj bo ''S'' = {1,...,100} in ''P''<sub>1</sub> značilnost, da je naravno število deljivo z 2, ''P''<sub>2</sub> značilnost za deljivost s 3 in ''P''<sub>3</sub> značilnost za deljivost s 5. Če je ''A''<sub>i</sub> podmnožica od ''S,'' katerih elementi imajo značilnost ''P''<sub>i</sub>, se dobi elementarno štetje: |''A''<sub>1</sub>| = 50, |''A''<sub>2</sub>| = 33 in |''A''<sub>3</sub>| = 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.

== Glej tudi ==

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

== Sklici ==

{{refbegin|4|normalfont=yes}}
{{sklici|refs=
<ref name="mazu_2010">{{sktxt|Mazur|2010}}.</ref>
<ref name="robe_2009">{{sktxt|Roberts|Tesman|2009}}.</ref>
<ref name="vanl_1992">{{sktxt|van Lint|Wilson|1992}}.</ref>
}}
{{refend}}

== Viri ==

{{refbegin|4|normalfont=yes}}
* {{citat|last1= Adams|first1= Henry|last2= Emmrich|first2= Kelly|last3= Gillespie|first3= Maria|last4= Golden|first4= Shannon|last5= Pries|first5= Rachel|title= Counting Rocks! An Introduction to Combinatorics|date= 2021|work= [[Državna univerza Kolorada]]|arxiv= 2108.04902}}
* {{citat|last1= Allenby|first1= R. B. J. T.|last2= Slomson|first2= Alan|title= How to Count: An Introduction to Combinatorics|publisher= CRC Press|date= 2010|series= Discrete Mathematics and Its Applications|pages= 51–60|isbn= 9781420082609|url= http://www.crcpress.com/product/isbn/9781420082609|edition= 2}}
* {{citat|last1= Björklund|first1= A.|last2= Husfeldt|first2= T.|last3= Koivisto|first3= M.|journal= [[SIAM Journal on Computing]]|pages= 546–563|title= Set partitioning via inclusion–exclusion|volume= 39|date= 2009|doi= 10.1137/070683933|issue= 2}}
* {{citat|last1= Brualdi|first1= Richard A.|title= Introductory Combinatorics|edition= 5.|publisher= Prentice–Hall|date= 2010|isbn= 9780136020400}}
* {{citat|last1= Cameron|first1= Peter J.|title= Combinatorics: Topics, Techniques, Algorithms|publisher= Cambridge University Press|date= 1994|isbn= 0-521-45761-0}}
* {{citat|last1= Fernández|first1= Roberto|location= Berlin|mr= 1219313|isbn= 3-540-54358-9|pages= xviii+444|date= 1992|series= Texts an Monographs in Physics|publisher= [[Springer-Verlag]]|title= Random Walks, Critical Phenomena, and Triviality in Quantum Field Theory|authorlink2= Alan Sokal|first2= Sokal|last2= Alan D.|authorlink3= Jürg Fröhlich|first3= Jürg|last3= Fröhlich|zbl= 0761.60061}}
* {{citat|last1= Graham|first1= R. L.|last2= Grötschel|first2= M.|authorlink2= Martin Grötschel|last3= Lovász|first3= L.|title= Hand Book of Combinatorics (volume-2)|publisher= MIT Press – North Holland|date= 1995|isbn= 9780262071710}}
* {{citat|last1= Gross|first1= Jonathan L.|title= Combinatorial Methods with Computer Applications|publisher= Chapman&Hall/CRC|date= 2008|isbn= 9781584887430}}
* {{SpringerEOM|title=Inclusion-and-exclusion principle}}
* {{citat|last1= Mazur|first1= David R.|title= Combinatorics A Guided Tour|publisher= The Mathematical Association of America|date= 2010|isbn= 9780883857625}}
* {{citat|last1= Roberts|first1= Fred S.|last2= Tesman|first2= Barry|title= Applied Combinatorics|edition= 2.|publisher= CRC Press|date= 2009|isbn= 9781420099829}}
* {{citat|last1= Stanley|first1= Richard P.|title= Enumerative Combinatorics Volume I|publisher= Wadsworth & Brooks/Cole|date= 1986|isbn= 0534065465}}
* {{citat|last1= van Lint|first1= J. H.|last2= Wilson|first2= R. M.|title= A Course in Combinatorics|publisher= Cambridge University Press|date= 1992|isbn= 0521422604}}
{{refend}}

{{PlanetMath attribution|id=2803|title=principle of inclusion–exclusion}}

[[Kategorija:Teorija verjetnosti]]