Načelo vključitev in izključitev

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

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

$|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.

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 Predloga:Mvar 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 Predloga:Mvar lih) ali izključi (če je Predloga:Mvar sod) kardinalnosti presekov med Predloga:Mvar 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,Predloga:R toda v delu se je prvič pojavilo pri matematiku Danielu da Silvi leta 1854,Predloga:R kasneje pa v delu Jamesa Josepha Sylvestra leta 1883.Predloga:R 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,Predloga:R toda 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 Predloga:Matematična formula pravi:Predloga:NumBlk

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:

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{k=1}^n(-1{)}^{k+1}(\sum _{1⩽i_1<\cdots <i_k⩽n}|A_{i_1}\cap \cdots \cap A_{i_k}|),$

ali:

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{\mathrm{\varnothing }\ne J\subseteq \{1,\dots ,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 $n=4$ ne more biti nobenih elementov več, ki bi se pojavili v več kot $4$ množicah; enako ne more biti več elementov, ki bi se pojavili v najmanj $5$ množicah.)

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

$\left|\bigcap _{i=1}^n\overline{A_i}\right|=|S-\bigcup _{i=1}^n{A}_i|=|S|-\sum _{i=1}^n|A_i|+\sum _{1⩽i<j⩽n}|A_i\cap A_j|-\cdots +(-1{)}^n|A_1\cap \cdots \cap A_n|.$

Naslednja različica izreka je taka: naj bodo Predloga:Matematična formula značilnosti, ki jih elementi iz Predloga:Mvar lahko imajo ali pa ne. Po tem načelo vključitev in izključitev poda način izračuna števila elementov iz Predloga:Mvar, ki nimajo nobene izmed teh značilnosti. Naj bo Predloga:Matematična formula podmnožica elementov iz Predloga:Mvar, ki imajo značilnost Predloga:Matematična formula, uporabi pa se načelo v svoji komplementarni obliki. To različico odkril Sylvester.Predloga:R

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

Zgledi

Štetje celih števil

Kot preprost primer načela vključitve in izključitve, sledi naslednje vprašanje:Predloga:R

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.

Glej tudi

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

Viri

• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:SpringerEOM
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat