Načelo vključitev in izključitev

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search
Vennov diagram, ki prikazuje unijo množic A in B, ki je vse ostalo, kar ni belo

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

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 smo lahko nekaj elementov šteli dvakrat. Te 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

Ta formula se lahko potrdi s tem, da preštejemo kolikokrat smo prešteli vsako območje Vennovega diagrama na desni strani formule. V tem primeru, ko odstranimo prevečkrat štete elemente, moramo nazaj prišteti, saj smo odšteli prevečkrat.

Načelo vključitev in izključitev na Vennovem diagramu za tri množice

Sedaj posplošimo rezultate zgornjih primerov, ki smo jih podali za razlago načela vključitev in izključitev. Da bi našli kardinalnost unije n množic:

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

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

Izrek[uredi | uredi kodo]

V svoji splošni obliki, nam načelo vključitev in izključitev za končne množice A1, ..., An pravi

 

 

 

 

(1)

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

ali

Drugače rečeno z besedami: če želimo prešteti število elementov v končni uniji končnih množic, moramo najprej sešteti vse kardinalnosti posameznih množic, potem odšteti število elementov, ki se pojavijo v najmanj dveh množicah, nato moramo 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 ne more biti nobenih elementov več, ki bi se pojavili v več kot množicah; enako ne more biti več elementov, ki bi se pojavili v najmanj 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 Ai in naj bo komplement od Ai v S. Po De Morganovih zakonih dobimo

Naslednja varianta izreka je taka: naj bodo P1, ..., Pn lastnosti, ki jih elementi iz S lahko imajo ali pa ne. Po tem nam načelo vključitev in izključitev poda način izračuna števila elementov iz S, ki nimajo nobene izmed teh lastnosti. Naj bo Ai podmnožica elementov iz S, ki imajo lastnost Pi, uporabimo pa načelo v svoji komplementarni obliki. To varianto je odkril J. J. Sylvester.[1]

Če 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.

Primeri[uredi | uredi kodo]

Štetje celih števil[uredi | uredi kodo]

Kot preprost primer načela vključitve in izključitve, si oglej to vprašanje:[5]

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

Naj bo S = {1,...,100} in P1 lastnost, da je naravno število deljivo z 2, P2 lastnost za deljivost s 3 in P3 lastnost za deljivost s 5. Če je Ai podmnožica od S, katerih elementi imajo lastnost Pi, dobimo elementarno štetje: |A1| = 50, |A2| = 33 in |A3| = 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[uredi | uredi kodo]

Opombe[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

  • Allenby, R.B.J.T.; Slomson, Alan (2010), How to Count: An Introduction to Combinatorics, Discrete Mathematics and Its Applications (2 izd.), CRC Press, str. 51–60, ISBN 9781420082609
  • Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), "Set partitioning via inclusion–exclusion", SIAM Journal on Computing, 39 (2): 546–563, doi:10.1137/070683933
  • Brualdi, Richard A. (2010), Introductory Combinatorics (5th izd.), Prentice–Hall, ISBN 9780136020400
  • Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 0-521-45761-0
  • Fernández, Roberto; Fröhlich, Jürg; Alan D., Sokal (1992), Random Walks, Critical Phenomena, and Triviality in Quantum Field Theory, Texts an Monographs in Physics, Berlin: Springer-Verlag, str. xviii+444, ISBN 3-540-54358-9, MR 1219313, Zbl 0761.60061
  • Graham, R.L.; Grötschel, M.; Lovász, L. (1995), Hand Book of Combinatorics (volume-2), MIT Press – North Holland, ISBN 9780262071710
  • Gross, Jonathan L. (2008), Combinatorial Methods with Computer Applications, Chapman&Hall/CRC, ISBN 9781584887430
  • "Inclusion-and-exclusion principle", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
  • Mazur, David R. (2010), Combinatorics A Guided Tour, The Mathematical Association of America, ISBN 9780883857625
  • Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd izd.), CRC Press, ISBN 9781420099829
  • Stanley, Richard P. (1986), Enumerative Combinatorics Volume I, Wadsworth & Brooks/Cole, ISBN 0534065465
  • van Lint, J.H.; Wilson, R.M. (1992), A Course in Combinatorics, Cambridge University Press, ISBN 0521422604

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