NA ˇ CELO VKLJU ˇ CITEV IN IZKLJU ˇ CITEV TER NJEGOVA UPORABA

(1)

Univerza v Ljubljani Pedagoˇ ska fakulteta

Ines Medved

NA ˇ CELO VKLJU ˇ CITEV IN IZKLJU ˇ CITEV TER NJEGOVA UPORABA

DIPLOMSKO DELO

Ljubljana, 2013

(2)

Univerza v Ljubljani Pedagoˇ ska fakulteta

UNIVERZITETNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE DVOPREDMETNI U ˇCITELJ SMER: MATEMATIKA - RA ˇCUNALNIˇSTVO

Ines Medved

Mentor : doc. dr. Primoˇ z ˇ Sparl Somentor : as. dr. Boˇ stjan Kuzman

NA ˇ CELO VKLJU ˇ CITEV IN IZKLJU ˇ CITEV TER NJEGOVA UPORABA

DIPLOMSKO DELO

Ljubljana, 2013

(3)

Svoji druˇzini in Tomaˇzu.

(4)

Zahvala

Zahvaljujem se svojemu mentorju doc. dr. Primoˇzu ˇSparlu in somentorju, as. dr. Boˇstjanu Kuzmanu za strokovno pomoˇc, nasvete in spodbujanje pri nastajanju diplomskega dela.

Hvala vsem prijateljicam, Katji, Barbari, Marini, Mojci in fantu Tomaˇzu, ki so mi v ˇcasu ˇstudija stali ob strani, me vzpodbujali in verjeli vame.

Se posebej sem hvaleˇˇ zna starˇsem in sestri Moniki, ki so mi omogoˇcili ˇstudij in tudi ˇcas zanj ter me na tej poti v vseh pogledih podpirali.

(5)

Povzetek

V diplomskem delu se osredotoˇcimo na naˇcelo vkljuˇcitev in izkljuˇcitev ter njegovo uporabo. Gre za kombinatoriˇcno orodje za preˇstevanje. Bolj natanˇcno, gre za orodje, ki omogoˇca doloˇcitev kardinalnosti unije konˇcno mnogo konˇcnih mnoˇzic. Pri tem je potrebno znati doloˇciti kardinalnost posameznih mnoˇzic ter njihovih (veˇckratnih) presekov. V diplomskem delu predstavimo osnove kombinatorike, pokaˇzemo nekaj preprostih dejstev in primere uporabe. Na preprosti nalogi prikaˇzemo tudi uporabo naˇcela vkljuˇcitev in izkljuˇcitev, katerega nato na matematiˇcno korekten naˇcin tudi dokaˇzemo. Preostanek diplomskega dela predstavljajo prikazi uporabe naˇcela vkljuˇcitev in izkljuˇcitev. Konkretno, posvetimo se Stirlingovim ˇstevilom druge vrste, Eulerjevi funkciji ϕter igri Scrabble.

Kljuˇcne besede: naˇcelo vkljuˇcitev in izkljuˇcitev, kombinatorika, Stirlingova ˇstevila druge vrste, Eulerjeva funkcija ϕ, Scrabble.

MSC(2000) Klasifikacija: 05A10, 05A17, 05A99.

(6)

Abstract

In this BSc thesis we focus on the principle of inclusion and exclusion and its applications. This principle is a combinatorial tool for counting. More precisely, it is a tool that allows one to determine the cardinality of unions of finitely many finite sets. To do so one needs to be able to determine the cardinality of each of the sets and their (multiple) intersections. In the thesis we introduce same basic notions in combinatorics, present some simple facts and give examples of applications. We illustrate the principle of inclusion and exclusion on a simple problem.

We give a mathematically correct proof of the theorem. In the remainder of the thesis we give a few demonstrations of the principle of inclusion and exclusion in use. Specifically, we consider to the Stirling numbers of the second kind, the Eulerϕfunction and the game Scrabble.

Keywords: the principle of inclusion and exclusion, combinatorics, Stirling numbers of the second kind, Euler ϕ function, Scrabble.

MSC(2000) Classification: 05A10, 05A17, 05A99.

(7)

Kazalo

Zahvala Povzetek Abstract

1 Uvod 1

2 Osnove kombinatorike 4

3 Naˇcelo vkljuˇcitev in izkljuˇcitev 14

3.1 Dokaz . . . 14

4 Uporaba 17

4.1 Stirlingova ˇstevila druge vrste . . . 17 4.2 Eulerjeva funkcijaϕ . . . 22 4.3 Scrabble . . . 25

5 Sklepne ugotovitve 30

Literatura 31

(8)

Slike

2.1 Kombinatoriˇcno oziroma n odloˇcitveno drevo . . . 6 3.1 Vennov diagram dveh mnoˇzic . . . 15

(9)

Tabele

1.1 Tabela ˇstevil med 1 in 56. . . 2

1.2 Veˇckratniki ˇstevila 3, ki so manjˇsi od 56. . . 2

1.3 Veˇckratniki ˇstevila 7, ki so manjˇsi od 56. . . 2

1.4 Veˇckratniki ˇstevila 3 in 7, ki so manjˇsi od 56. . . 3

4.1 Stirlingova ˇstevila druge vrste. . . 19

(10)

Poglavje 1 Uvod

Za bodoˇco profesorico matematike in raˇcunalniˇstva ni ravno presenetljivo, da me je matematika ˇ

ze od nekdaj zanimala. Nikoli mi ni bilo teˇzko dolgo v noˇc reˇsevati problemov z dvema neznan- kama, prav tako pa sem z veseljem pomagala tistim, ki matematike niso razumeli. Ravno zato sem se tudi odloˇcila za ˇstudij matematike. V vseh letih ˇsolanja so mi bile vse matematiˇcne teme zelo pri srcu, z izjemo ene - kombinatorike. Z njo sem se sreˇcala ˇze v osnovni ˇsoli, nato na gimnaziji in celo na fakulteti, vendar ji nikoli nisem priˇsla do dna. Nikoli je nisem povsem razumela. Tako sem se odloˇcila, da si stvari konˇcno razjasnim. Najprej sem si zadala nalogo, da ustvarim video vodiˇce (video tutoriale) na temo kombinatorike, da bi pomagala vsem tistim sotrpinom srednjeˇsolcem, ki se muˇcijo s permutacijami, variacijami in kombinacijami. Profesor Sparl, ki je kasneje postal moj mentor, mi je predlagal, da naj izvrstno idejo raje prihranimˇ za magistrsko delo, v diplomskem delu pa naj si naberem potrebno teoretiˇcno podlago in se poglobim v nek konkreten del kombinatoriˇcne vsebine. Odloˇcila sva se, da bom v diplomskem delu predstavila naˇcelo vkljuˇcitev in izkljuˇcitev ter prikazala nekaj primerov njegove uporabe.

Kombinatorika se med drugim ukvarja s preˇstevanji. Lahko nas zanima ˇstevilo vseh moˇznih izborov doloˇcenega ˇstevila reˇci iz danega nabora, lahko pa tudi ˇstevilo porazdelitev danih reˇci v dane predale. Razvita so bila razliˇcna orodja za preˇstevanje in eno izmed pomembnejˇsih je naˇcelo vkljuˇcitev in izkljuˇcitev.

Nekoliko poenostavljeno povedano je naˇcelo vkljuˇcitev in izkljuˇcitev kombinatoriˇcno orodje za doloˇcitev kardinalnosti unije danih konˇcnih mnoˇzic. Pri tem moramo znati doloˇciti velikosti teh mnoˇzic, njihovih dvojnih presekov, trojnih presekov itd.

To naˇcelo se pogosto uporablja tudi v verjetnosti, ko je na primer potrebno preˇsteti ˇstevilo ugodnih izidov za nek dani poskus.

Poglejmo si najprej intuitiven naˇcin uporabe naˇcela vkljuˇcitev in izkljuˇcitev na preprostem konkretnem zgledu.

(11)

POGLAVJE 1. UVOD

Primer 1 Koliko je naravnih ˇstevil do 56, ki so deljiva s 3 ali 7?

Zapiˇsimo si vsa ˇstevila od 1 do vkljuˇcno 56.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

Tabela 1.1: Tabela ˇstevil med 1 in 56.

Z modro barvo oznaˇcimo vsa ˇstevila, ki so deljiva s 3 in jih preˇstejmo.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

Tabela 1.2: Veˇckratniki ˇstevila 3, ki so manjˇsi od 56.

Vseh ˇstevil od 1 do 56, ki so deljiva s 3 je 18. Sedaj pa z rdeˇco barvo oznaˇcimo vsa ˇstevila, ki so veˇckratniki ˇstevila 7 in jih preˇstejmo.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

Tabela 1.3: Veˇckratniki ˇstevila 7, ki so manjˇsi od 56.

Stevil, ki so deljiva s 7 in manjˇsa od 56, je 8. Opazimo lahko, da so nekatera ˇstevila obar-ˇ vana v obeh tabelah. To pomeni, da so deljiva s 3 in s 7. V novi tabeli jih oznaˇcimo z vijoliˇcno barvo.

(12)

POGLAVJE 1. UVOD

1 2 3 4 5 6 7 8 9 10 11 12 13 14

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

Tabela 1.4: Veˇckratniki ˇstevila 3 in 7, ki so manjˇsi od 56.

Obarvanih ˇstevil je 24, torej je vseh ˇstevil od 1 do 56, ki so deljiva s 3 ali s 7, ravno 24.

Da bi dobili ta rezultat, je potrebno od vsote ˇstevila ˇstevil deljivih s 7 in ˇstevila ˇstevil deljivih s 3, odˇsteti ˇstevilo ˇstevil deljivih s 3 in 7. Slednja smo namreˇc najprej ˇsteli (oz. vkljuˇcili) dvakrat, zato jih je potrebno enkrat odˇsteti (oz. izkljuˇciti). Na tem principu vkljuˇcevanja in izkljuˇcevanja temelji naˇcelo vkljuˇcitev in izkljuˇcitev, ki ga bomo podrobno spoznali v nadaljevanju. Od tod potem dobimo raˇcun 18 + 8−2 = 24.

V nadaljevanju bomo videli, da lahko s pomoˇcjo naˇcela vkljuˇcitev in izkljuˇcitev izpeljemo formulo za Stirlingova ˇstevila druge vrste, formulo za Eulerjevo funkcijo ϕ, lahko preˇstejemo ˇstevilo surjektivnih funkcij med dvema konˇcnima mnoˇzicama, pa tudi preˇstejemo na koliko razliˇcnih naˇcinov lahko dobi prvi igralec pri igri Scrabble svojih zaˇcetnih sedem ploˇsˇcic.

(13)

Poglavje 2

Osnove kombinatorike

Kombinatorika je veja matematike, ki se ukvarja s preuˇcevanjem konˇcnih in ˇstevno neskonˇcnih diskretnih struktur. Ukvarja se predvsem z razporejanjem elementov v konˇcne mnoˇzice in ocenjevanjem ˇstevila takih razporeditev ter ugotavljanjem ali taka porazdelitev ali izbor sploh obstajata.

Velik del kombinatorike predstavljajo problemi preˇstevanj. Tej temi bomo posvetili tudi najveˇc pozornosti v diplomskem delu. Tako nas na primer zanima ˇstevilo vseh moˇznih trimestnih ˇstevil formiranih s podanimi ˇstevkami ali pa ˇstevilo razliˇcnih telefonskih ˇstevilk. Lahko pa ugotavljamo kompleksnost algoritmov, ali raˇcunamo verjetnosti sluˇcajnih dogodkov. V tem poglavju, ki je povzeto po [5], si ogledamo osnovne pojme kombinatorike, ki jih bomo potrebovali v nadaljevanju.

Oglejmo si preprost primer

Primer 2 Dana je mnoˇzica {1,2,3,4}. Koliko razliˇcnih trimestnih ˇstevil, katerih ˇstevke pripadajo tej mnoˇzici, se zaˇcnejo s ˇstevko 2, hkrati pa se v njej ˇstevke ne ponavljajo, lahko skonstruiramo?

Moˇzna ˇstevila lahko po krajˇsem razmisleku kar zapiˇsemo. Vemo, da se ˇstevke znotraj tri- mestnega ˇstevila ne smejo ponavljati in da se vsako ˇstevilo zaˇcne s ˇstevko 2. Na drugem mestu naj bo najprej ˇstevilo 1. Torej nam za zadnje mesto ostaneta samo ˇse ˇstevki 3 in 4, saj se ˇstevke ne smejo ponavljati. ˇStevili, ki nastaneta sta 213 in 214. Analogno dobimo ˇse ˇstevila 231, 234, 241 in 243. Torej lahko skonstruiramo natanko 6 ˇstevil.

Pri tako preprostih nalogah torej ne potrebujemo nobenih posebnih orodij. Pri malce bolj zahtevnih pa je potrebnega nekaj dodatnega znanja. Na primer najosnovnejˇsi pravili kombinatorike, pravilo vsote in pravilo produkta.

(14)

POGLAVJE 2. OSNOVE KOMBINATORIKE

Izrek 1 (Pravilo vsote)

Ce jeˇ A neprazna mnoˇzica in je A=A₁∪A₂∪ · · · ∪A_n, kjer so A_i paroma disjunktne mnoˇzice, je |A|=|A1|+|A2|+· · ·+|An|.

V posebnem primeru, ko je n = 2, to pomeni, da je v primeru, kjer lahko mnoˇzico vseh izborov razbijemo na dva disjunktna dela,ˇstevilo vseh moˇznosti enako vsoti ˇstevila moˇznosti iz prvega in drugega dela. ˇCe se torej pri izbiranju lahko odloˇcimo bodisi za eno od n₁ moˇznosti iz prve mnoˇzice ali pa za eno od n₂ moˇznosti iz druge mnoˇzice, imamo skupaj n = n₁ +n₂ moˇznih izborov.

Primer 3 Doloˇcite ˇstevilo naravnih ˇstevil do vkljuˇcno 200, ki so deljiva z vsaj enim izmed praˇstevil 13, 17 in 19.

Ker nobeno ˇstevilo do 200 ni hkrati deljivo z dvema izmed njih, lahko mnoˇzico A vseh naravnih ˇstevil, manjˇsih od 200 in deljivih z vsaj enim izmed praˇstevil 13, 17 in 19, loˇcimo na tri disjunktne mnoˇzice. V mnoˇzici A₁₃so vsi veˇckratniki ˇstevila 13, vA₁₇ so vsi veˇckratniki ˇstevila 17 in v A₁₉ so vsi veˇckratniki ˇstevila 19. Doloˇcimo sedaj kardinalnosti teh treh mnoˇzic.

Najveˇcje ˇstevilo, ki je ˇse v mnoˇzici A₁₃ je 195 in velja 15·13 = 195. Torej je v mnoˇzici A₁₃ natanko 15 ˇstevil (natanˇcnejˇso razlago kako doloˇciti ˇstevilo naravnih ˇstevil med vkljuˇcno a in b, ki so deljiva s k, bo bralec naˇsel v Primeru 10 ob koncu tega poglavja). V mnoˇzici A₁₇ je najveˇcje ˇstevilo 187, katerega lahko zapiˇsemo kot 187 = 11·17. Moˇc mnoˇzice A₁₇ je potem 11.

V mnoˇziciA₁₉pa je najveˇcje ˇstevilo 190 = 10·19, kar pomeni, da ima ta mnoˇzica 10 elementov.

Ker vemo, da so mnoˇzice paroma disjkunktne, lahko uporabimo pravilo vsote.

|A|=|A₁₃|+|A₁₇|+|A₁₉|

= 15 + 11 + 10

= 36

Torej obstaja natanko 36 naravnih ˇstevil do vkljuˇcno 200, ki so deljiva z vsaj enim izmed praˇstevil 13, 17 in 19.

Izrek 2 (Pravilo produkta)

Ce soˇ A₁,A₂, . . . ,A_n neprazne konˇcne mnoˇzice je |A₁×A₂× · · · ×A_n|=|A₁| · |A₂| · · · |A_n|.

To pravilo nam torej pove: ˇCe so izbori ali porazdelitve odvisne od odloˇcitve v veˇcih korakih in se na vsakem koraku odloˇcimo neodvisno od odloˇcitev na drugih korakih, je ˇstevilo vseh moˇznosti produkt ˇstevila moˇznih odloˇcitev na posameznem koraku.

To pravilo lahko posploˇsimo, tudi na primer, ko je le ˇstevilo moˇznih odloˇcitev na vsakem koraku (ne pa tudi konkretne moˇznosti), neodvisno od ˇstevila moˇznih odloˇcitev na drugih korakih.

(15)

Tudi v tem primeru je ˇstevilo vseh moˇznosti kar produkt vseh moˇznosti po posameznih korakih.

Proces odloˇcanja lahko ponazorimo s kombinatoriˇcnim drevesom.

Slika 2.1: Kombinatoriˇcno oziroma n odloˇcitveno drevo

Primer 4 Kupujemo nov raˇcunalnik z zaslonom. Najprej se moramo odloˇciti za znamko raˇcunalnika. Na voljo imamo naslednje znamke: Apple, Toshiba, Acer, Asus, Dell, HP in MSI. Potem moramo izbrati velikost zaslona in izbiramo lahko med 10, 11, 12, 13, 14, 15 in 17 paliˇcnimi diagonalami. Na koncu pa se moramo odloˇciti ˇse za znamko procesorja. Tu izbiramo samo med Intelom in AMD-jem. Koliko razliˇcnih raˇcunalnikov z monitorjem lahko sestavimo?

Tudi tukaj lahko nalogo razbijemo na manjˇse dele. Intuitivno jo razdelimo na tri kategorije. To soA_znamka,A_diagonala inA_procesor. Velja|A_znamka|= 7, saj imamo sedem razliˇcnih proizvajalcev,

|A_diagonala| = 7, ker imamo sedem razliˇcnih dolˇzin diagonale in |A_procesor| = 2, ker imamo na voljo samo dva proizvajalca procesorjev. Opazimo lahko, da ˇce ˇzelimo imeti celoten raˇcunalnik z zaslonom, moramo iz vsake mnoˇzice izbrati po en element, pri ˇcemer pa naˇsa odloˇcitev v prvi mnoˇzici ne vpliva na izbiro v ostalih mnoˇzicah. To pa pomeni, da lahko uporabimo pravilo produkta.

|A|=|A_znamka| · |A_diagonala| · |A_procesor|

= 7·7·2

= 98

To pomeni, da lahko sestavimo 98 razliˇcnih raˇcunalnikov z zaslonom, ˇce imamo na razpolago 7 razliˇcnih znamk raˇcunalnika, 7 razliˇcnih velikosti diagonale in 2 razliˇcna proizvojalca procesorjev.

Najosnovnejˇsi naˇcini preˇstevanja, ki jih spoznamo ˇze v srednji ˇsoli, so preˇstevanja raznih izborov. Spraˇsujemo se torej, na koliko naˇcinov lahko iz danega nabora reˇci izberemo doloˇceno ˇstevilo reˇci. ˇCe je vrstni red pomemben, govorimo o permutacijah in variacijah, ˇce le-ta ni pomemben, gre za kombinacije.

(16)

Definicija 1 Permutacije so razporeditve vseh elementov dane mnoˇzice A={a₁, a₂, . . . , a_n} v nekem vrstnem redu. Permutacije torej lahko interpretiramo tudi kot bijektivne preslikave dane mnoˇzice nase.

Primer 5 Ena od permutacij mnoˇzice A={1,2,3,4,5,6,7} je preslikava 1 2 3 4 5 6 7

5 7 6 1 3 2 4

! ,

kjer je pomen tega zapisa ta, da je slika elementa i zapisana v spodnji vrstici pod ˇstevilom i.

Stevilo moˇˇ znih permutacij mnoˇzice z n elementi je P(n) = n· (n −1)· · ·2·1 = n!, saj se za vsak element i odloˇcimo katera slika mu pripada. Za element na prvem mestu imamo na voljo n slik, potem pa, ker elementov izbire ne ponavljamo, je v vsaki naslednji fazi odloˇcitve ena izbira manj.

Torej je izbira slike za i-ti element na vsakem koraku neodvisna od odloˇcitve v prejˇsnjem koraku. To pa pomeni, da lahko uporabimo posloˇsitev pravila produkta za izraˇcun ˇstevila moˇznih permutacij. Od tod sledi, da zmnoˇzimo ˇstevilo moˇznosti na vsakem koraku, to pa je ravno n·(n−1)· · ·2·1.

Permutacije sreˇcamo marsikje. Tako jih na primer najdemo v obrazcu za izraˇcun determinante, pri algoritmih za sortiranje, razporedu kart v igri in podobno. Obiˇcajno sklenemo dogovor, da produkt n·(n−1)· · ·2·1 oznaˇcimo z n!, kar preberemo kot n f akulteta.

Definicija 2 Variacije so izbori doloˇcenega ˇstevila elementov iz dane mnoˇzice elementov, kjer je pomemben vrstni red.

Glede na to ali dovolimo, da se elementi ponovljajo ali ne, variacije loˇcimo na variacije brez ponavljanja in na variacije s ponavljanjem. Variacije brez ponavljanja lahko interpretiramo kot injektivne preslikave mnoˇzice {1,2, . . . , k} v dano mnoˇzico (pri tem je k ˇstevilo izbiranj).

Stevilo variacij brez ponavljanja, pri ˇˇ cemer izbiramo k krat, na voljo pa je n elementov dane mnoˇzice, oznaˇcimo z V_kⁿ. ˇStevilo variacij, kjer je ponavljanje dovoljeno, oznaˇcimo z ^(p)V_kⁿ. Primer 6 Koliko razliˇcnih “besed” s k ˇcrkami (pomen torej ni pomemben) lahko sestavimo iz ˇ

crk abecede z n razliˇcnimi ˇcrkami, ˇce se ˇcrke ne smejo ponavljati?

Ker je vrstni red pomemben in ˇcrk ne vraˇcamo, gre za variacije brez ponavljanja. Za prvo ˇ

crko nove besede imamo n moˇznosti, saj je na voljo n ˇcrk. Ker ˇcrk ne ponavljamo, imamo za drugo ˇcrko nove besede ˇse n−1 moˇznosti. Podobno nadaljujemo naprej. Za k-to ˇcrko imamo

(17)

tako samo ˇse n−k+ 1 moˇznosti. Po pravilu produkta je vseh moˇznosti n·(n−1)·(n−2)·. . .·(n−k+ 1) = n!

(n−k)! =V_kⁿ. Torej lahko sestavimo _(n−k)!^n! razliˇcnih besed.

Primer 7 Koliko razliˇcnih “besed” skˇcrkami lahko sestavimo iz naboranˇcrk, ˇce se ˇcrke lahko ponavljajo.

Ker je vrstni red pomemben in ˇcrke ponavljamo, gre za variacije s ponavljanjem. Za prvo ˇ

crko nove besede imamo n moˇznosti, saj je na voljo n ˇcrk. Ker ˇcrke ponavljamo, imamo tudi za drugo ˇcrko nove besede ˇse vedno n moˇznosti, prav tako pa potem za vsako naslednjo. Po pravilu produkta je torej vseh moˇznosti

n·n·n·. . .·n =n^k=^(p)V_kⁿ. Torej lahko sestavimo n^k razliˇcnih besed.

Primer 8 Igralno kocko vrˇzemo petkrat. Na koliko naˇcinov se lahko zgodi, da pade ˇsestica natanko v drugem, tretjem in petem metu?

Kocka ima ˇsest stranic, na katerih so napisane ˇstevke od 1 do 6. Ce pade ˇsestica sevedaˇ ne pade nobeno izmed ostalih petih ˇstevil. Ker imamo natanko doloˇceno kdaj pade ˇsestica, je vrstni red metov pomemben. Zgodi se lahko, da veˇckrat pade ista ˇstevka, torej se dogodki lahko ponavljajo. ˇSestica mora pasti natanko v treh primerih, v ostalih dveh pa ne. Torej imamo opravka z variacijami s ponavljanjem, zanima pa nas na koliko naˇcinov lahko padejo preostale ˇstevke v prvem in ˇcetrtem metu. Zahtevano se torej lahko zgodi na

(p)V₅² = 5² = 25 naˇcinov.

Definicija 3 Kombinacije so izbori doloˇcenega ˇstevila elementov iz celotne mnoˇzice elementov, pri ˇcemer vrstni red izbranih elementov ni pomemben.

Kombinacije so zelo podobne variacijam, s to razliko, da vrstni red ni pomemben. Kot variacije, lahko tudi kombinacije loˇcimo na kombinacije brez ponavljanja in na kombinacije s ponavljanjem.

Vrnimo se na variacije brez ponavljanja, ko izmed n elementov izberemo k elementov. Ker

(18)

neurejen izbor k reˇci ˇsteli k! krat, saj je k! naˇcinov na katere lahko uredimo teh k elementov.

Vseh urejenih izborov je potem k! krat toliko kot neurejenih. Torej je vseh neurejenih izborov natanko _(n−k)!k!^n! , kar obiˇcajno oznaˇcimo z ⁿ_k

. ˇStevilo kombinacij brez ponavljanja oznaˇcimo tudi kot C_n^k.

Primer 9 Na koliko naˇcinov lahko izmed 5 fantov in 5 deklet izberemo skupino 3 fantov in 2 deklet?

Ker lahko fante in dekleta obravnavamo kot dve popolnoma loˇceni skupini in je izbor fantov neodvisen od izbora deklet, lahko uporabimo pravilo produkta.

C₅³·C₅² = 5

3 5

2

= 10·10 = 100

Preostanejo nam ˇse kombinacije s ponavljanjem. Iz nabora n razliˇcnih ˇcrk izberemo k ˇcrk, pri ˇcemer se lahko ˇcrke ponavljajo. Zanima nas kolikokrat smo izvlekli prvo ˇcrko, drugo ˇcrko, . . ., n-to ˇcrko. Naj k₁ oznaˇcuje kolikokrat smo izbrali prvo ˇcrko, k₂ drugo ˇcrko, . . ., k_n n-to ˇ

crko. Velja torej, da so ki nenegativna cela ˇstevila in velja k1+k2+· · ·+kn =k.

Vpraˇsanje o ˇstevilu neurejenih izborovk ˇcrk iz nabora nˇcrk s ponavljanjem je torej ekvivalentno vpraˇsanju o ˇstevilu reˇsitev enaˇcbek₁+k₂+· · ·+k_n=k v nenegativnih celih ˇstevilih, kjer so k_i neznanke. To pa je ekvivalentno ˇstevilu naˇcinov, na katere lahko med k enic ter levo ali desno od vseh postavimo n−1 navpiˇcnih meja.

Ker se moramo odloˇciti na katerihn−1 izmedn+k−1 mest postavimo navpiˇcne ˇcrte, je torej neurejenih izborov k ˇcrk iz nabora n ˇcrk s ponavljanjem

n+k−1 n−1

=

n+k−1 k

.

(19)

Za konec poglavja si oglejmo ˇse nalogo, ki bo nakazala kaj se dogaja pri naˇcelu vkljuˇcitev in izkljuˇcitev.

Primer 10 Koliko naravnih ˇstevil od 14 do 2013 je deljivih z vsaj enim izmed ˇstevil 2, 3 in 5?

Zaˇcnimo najprej z laˇzjim vpraˇsanjem. Koliko ˇstevil od 14 do 2013 je deljivih z 2?

Premislimo najprej koliko je ˇstevil med vkljuˇcno 14 in 2013. To izraˇcunamo tako, da od zadnjega ˇstevila odˇstejemo prvo ˇstevilo in priˇstejemo 1, saj ˇstejemo tudi prvega. Torej je vseh ˇstevil ravno 2013−14 + 1 = 2000.

Dogovorimo se, da v nadaljevanju z A_k oznaˇcimo mnoˇzico tistih naravnih ˇstevil med 14 in 2013, ki so deljiva s k. Mnoˇzica A₂ je torej mnoˇzica vseh tistih ˇstevil, ki so deljiva z 2. Vemo, da so s ˇstevilom 2 deljiva vsa soda ˇstevila, torej ravno polovica vseh ˇstevil. Torej je med 14 in 2013 natanko 1000 ˇstevil deljivih z 2, to je |A2|= 1000.

Koliko ˇstevil med 14 in 2013 je deljivih s 5?

Ugotoviti moramo, katero je prvo in katero zadnje ˇstevilo, ki je ˇze oziroma ˇse deljivo s 5.

Poiˇsˇcimo najmanjˇse ˇstevilo med 14 in 2013, ki je deljivo s 5. Dobimo ga tako, da 14 delimo s 5 ter koliˇcnik zaokroˇzimo navzgor, nato pa dobljeno zopet pomnoˇzimo s 5. Dobimo

14 : 5 = 2,8.

Torej je najmanjˇse ˇstevilo med 14 in 2013, ki je deljivo s 5, enako 5·3 = 15.

Poiˇsˇcimo sedaj ˇse najveˇcje ˇstevilo med 14 in 2013, ki je ˇse deljivo s 5. Dobimo ga tako, da 2013 delimo s 5 ter koliˇcnik zaokroˇzimo navzdol, nato pa dobljeno zopet pomnoˇzimo s 5. Dobimo

2013 : 5 = 402,6.

Torej je iskano ˇstevilo 5·402 = 2010.

Sedaj lahko izraˇcunamo koliko ˇstevil med 14 in 2013 je deljivih s 5 tako, da od 402 odˇstejemo 3 in priˇstejemo 1.

402−3 + 1 = 400.

Torej je med 14 in 2013 natanko 400 ˇstevil deljivih s 5. To pa pomeni, da ima mnoˇzica A₅ 400 elementov.

(20)

Koliko ˇstevil med 14 in 2013 pa je deljivih z 2 ali s 5?

To so vsa tista ˇstevila, ki so v mnoˇzici A2 ali v mnoˇzici A5, torej nas zanima velikost mnoˇzice A₂ ∪A₅. Nekoliko naivno bi morda rekli, da moramo kar seˇsteti ˇstevilo ˇstevil, ki so deljiva z 2 in ˇstevilo ˇstevil, ki so deljiva s 5 ter tako dobimo odgovor. Med 14 in 2013 je natanko 1400 ˇstevil deljivih z 2 ali s 5.

Vendar pa hitro opazimo, da obstajajo ˇstevila, kot na primer ˇstevilo 10, ki so deljiva tako z 2 kot tudi s 5. To pa pomeni, da smo jih na ta naˇcin “ˇsteli dvakrat”. Torej moramo od omenjene vsote odˇsteti ˇse ˇstevilo tistih ˇstevil, ki so v preseku A2∩A5.

Gre ravno za ˇstevila, ki so hkrati deljiva z 2 in s 5. Lahko je videti, da so to ravno ˇstevila, ki so deljiva z 10, torej velja A₂∩A₅ =A₁₀.

Dokaˇzimo, da 10|n⇔2|n in 5 |n.

Najprej dokaˇzimo implikacijo v smeri z leve proti desni. Naj 10 | n. Tedaj lahko n zapiˇsemo kot n = 10·i za nek i∈N. Seveda je 10 = 2·5. Torej dobimo

n = 10·i= 2·5·i.

Ker je mnoˇzenje asociativno in komutativno lahko zapiˇsemo n kot n = 2·(5·i) = 5·(2·i),

to pa pomeni, da je n deljiv z 2 in s 5.

Sedaj pa dokaˇzimo ˇse implikacijo v obratno smer. Privzemimo torej, da 2 | n in 5 | n. Tedaj lahko nzapiˇsemo kot n = 2·l za nekl ∈N, hkrati pa kotn= 5·m za nek m∈N. Torej lahko n zapiˇsemo kot

n= 2·l= 5·m.

Po osnovnem izreku aritmetike vemo, da se da vsako ˇstevilo enoliˇcno razcepiti na produkt praˇstevil. Od tod sledi, da 5 | l in 2 | m. To potem pomeni, da lahko m zapiˇsemo kot m= 2·m₁ za nek m₁ ∈N. Dobimo

n = 5·m = 5·2·m₁ = 10·m₁.

Dokazali smo, da 10 deli ˇstevilo n natanko tedaj, ko je n hkrati deljivo z 2 in s 5.

Pokaˇzimo sedaj, da rezultat, ki smo ga pravkar dokazali, ni sluˇcajen, to je, dokaˇzimo da velja A_i∩A_j =A_v(i,j).

Dokazati moramo, da veljaA_i∩A_j ⊆A_v(i,j) inA_v(i,j) ⊆A_i∩A_j.Najprej dokaˇzimo vsebovanost

(21)

preseka A_i∩A_j v mnoˇzici A_v(i,j).

Naj bo m∈A_i∩A_j.Piˇsimo i=D(i,j)·i₁ in j =D(i,j)·j₁.Seveda je tedaj D(i₁,j₁) = 1. Ker je i·j =v(i,j)·D(i,j),sledi i·j =D(i,j)²·i·j, to je v(i,j) =i1·j1 ·D(i,j).

Zaradi m∈A_i∩A_j obstajata naravni ˇstevili k₁, k₂ ∈N,da je m =i·k₁ =j·k₂. Potemtakem je D(i,j)·i₁·k₁ =D(i,j)·j₁·k₂ in tako velja i₁·k₁ =j₁·k₂. Zaradi D(i₁,j₁) = 1 sledi i₁ | k₂ in tako je k₂ =i₁·l za nek l∈N. Tako konˇcno dobimo m=j₁·i₁·l·D(i,j) =v(i,j)·l in tako res velja m∈A_i∩A_j.

Sedaj dokaˇzimo ˇse obrat, to je A_v(i,j) ⊆Ai∩Aj.

Naj bom ∈A_v(i,j). Potem lahkomzapiˇsemo kotm=v(i,j)·r. Od prej ˇze vemo, da lahkov(i,j) zapiˇsemo kot v(i,j) =D(i,j)·i₁ ·j₁i·j₁ =j ·i₁. Tako smo pokazali, da velja A_i∩A_j =A_v(i,j) Kaj pa, ˇce imamo veˇc presekov? Poglejmo si na primeru treh. Dobimo

Ai∩Aj ∩Ak =Ai∩(Aj∩Ak) =Ai ∩A_v(j,k)=A_v(i,j,k). Analogno seveda lahko naredimo tudi za veˇc presekov.

Kot ˇze prej lahko sedaj izraˇcunamo koliko je ˇstevil med 14 in 2013, ki so deljiva z 10. To so vsa ˇstevila, ki imajo zadnjo ˇstevko 0. Dobimo

2013 : 10 = 201,3, torej je najveˇcje tako ˇstevilo 201·10 = 2010, 14 : 10 = 1,4, torej je najmanjˇse tako ˇstevilo 2·10 = 20.

Vseh takih ˇstevil je torej 201−2 + 1 = 200, to je

|A10|= 200.

Ce povzamemo, ˇstevilo naravnih ˇstevil med 14 in 2013, ki so deljiva z 2 ali s 5, izraˇˇ cunamo kot:

|A₂∪A₅|=|A₂|+|A₅| − |A₂∩A₅|

= 1000 + 400−200

= 1200.

Torej je vseh ˇstevil med 14 in 2013, ki so deljiva z 2 ali s 5, ravno 1200 in ne 1400, kot bi sprva lahko mislili.

(22)

Posvetimo se sedaj ˇse zaˇcetnemu vpraˇsanju. Premislimo koliko ˇstevil med 14 in 2013 je deljivih z 2, 3 ali s 5?

Izraˇcunati ˇzelimo kardinalnost unije treh mnoˇzicA₂, A₃inA₅. Vemo ˇze, da je|A₂|= 1000,|A₅|= 400 in |A₂∩A₅|= 200.

Kot zgoraj izraˇcunamo |A₃| = 61−5 + 1 = 667. Ze iz primera dveh mnoˇˇ zic lahko sklepamo, da odgovor|A₂∪A₃∪A₅|=|A₂|+|A₃|+|A₅| ne bo pravilen. Zopet imamo ˇstevila, ki smo jih ˇsteli veˇckrat. Nekatera ˇstevila smo ˇsteli enkrat, druga dvakrat in spet tretja trikrat, ker imamo tri mnoˇzice. Doloˇcimo velikosti presekov.

Za mnoˇzicoA₂∩A₅ˇze vemo, da je enaka mnoˇziciA₁₀in da vsebuje 200 elementov. Potrebujemo ˇse kardinalnosti |A₂ ∩A₃|,|A₂ ∩A₅|,|A₃ ∩A₅|, potrebovali pa bomo ˇse kardinalnost trojnega preseka |A₂∩A₃∩A₅|, ki jo moramo priˇsteti nazaj, saj smo nekatera ˇstevila res ˇsteli trikrat, vendar jih bomo s kardinalnostmi dvojnih presekov trikrat tudi odˇsteli. Seveda gre ravno za ˇstevila, ki so v trojnem preseku.

Po zgornjem je |A₂ ∩A₃| = |A₆|, |A₃ ∩A₅| = |A₁₅| in |A₂ ∩A₃ ∩A₅| = |A₃₀|. Kot zgoraj izraˇcunamo |A₆|= 335−3 + 1 = 333,|A₁₅|= 134−1 + 1 = 134 in |A₃₀|= 67−1 + 1 = 67.

Sedaj, ko imamo izraˇcunane vse moˇci potrebnih mnoˇzic, lahko izraˇcunamo|A₂∪A₃ ∪A₅|.

|A₂∪A₃∪A₅|=|A₂|+|A₃|+|A₅| −(|A₂∩A₃|+|A₂∩A₅|+|A₃∩A₅|) +|A₂∩A₃∩A₅|

=|A₂|+|A₃|+|A₅| − |A₆| − |A₁₀| − |A₁₅|+|A₃₀|

= 1000 + 667 + 400−333−200−134 + 67

= 1467

Torej je vseh ˇstevil med 14 in 2013, ki so deljiva z 2, 3 ali s 5, natanko 1467.

Kot bomo kmalu videli, smo v tem primeru v resnici ˇze uporabili naˇcelo vkljuˇcitev in izkljuˇcitev.

(23)

Poglavje 3

Naˇ celo vkljuˇ citev in izkljuˇ citev

V tem poglavju se bomo osredotoˇcili na naˇcelo vkljuˇcitev in izkljuˇcitev. Najprej ga bomo ma- tematiˇcno korektno zapisali, nato pa ˇse dokazali. Poglavje je povzeto po [4].

Oglejmo si najprej matematiˇcno formulacijo naˇcela vkljuˇcitev in izkljuˇcitev.

Izrek 3 Naj bo n ∈N in naj bodo A₁,A₂, . . . , A_n poljubne konˇcne mnoˇzice. Tedaj velja:

|A₁∪A₂∪. . .∪A_n|= X

1≤i≤n

|A_i|

− X

1≤i<j≤n

|A_i∩A_j|

+ X

1≤i<j<k≤n

|A_i∩A_j ∩A_k|

+· · ·

+ (−1)ⁿ⁺¹|A₁∩A₂∩ · · · ∩A_n|.

Opazimo, da smo torej v nalogi iz prejˇsnjega poglavja uporabili ravno ta izrek zan = 3.

3.1 Dokaz

Dokaz naˇcela vkljuˇcitev in izkljuˇcitev gre najbolj naravno z indukcijo na ˇstevilo mnoˇzic v uniji.

Za n = 1 nimamo niˇcesar dokazovati. Prvi kljuˇcen korak torej predstavlja primer n = 2. V tem primeru izrek 3 pravi, da za poljubni konˇcni mnoˇzici velja

|A∪B|=|A|+|B| − |A∩B|.

(24)

3.1. DOKAZ POGLAVJE 3. NA ˇCELO VKLJU ˇCITEV IN IZKLJU ˇCITEV

Ceprav se mnoˇˇ zici A in B naˇceloma delno prekrivata, lahko njuno unijo zapiˇsemo kot unijo

Slika 3.1: Vennov diagram dveh mnoˇzic

dveh diskjunktnih mnoˇzic. To sta mnoˇzica A in obmoˇcje mnoˇzice B brez A, kar zapiˇsemo kot B\A. Torej lahko celotno unijo A∪B zapiˇsemo kot A∪(B\A). Po pravilu vsote velja

|A∪B|=|A|+|B\A|.

Tudi mnoˇzicoB lahko zapiˇsemo kot disjunktno unijo dveh mnoˇzic in sicerB = (B\A)∪(A∩B).

Ker sta ti dve mnoˇzici disjunktni, lahko zopet uporabimo pravilo vsote in zapiˇsemo |B| =

|B\A|+|A∩B|. Od tod sledi|B\A|=|B| − |A∩B|. Ce sedaj to vstavimo v zgornjo enaˇˇ cbo, dobimo

|A∪B|=|A|+|B\A|=

=|A|+|B| − |A∩B|.

Tako smo dokazali veljavnost izreka 3 zan = 2. Sedaj se lahko osredotoˇcimo na preverjanje ali lahko iz poljubnega n ∈Nsklepamo na njegovega naslednika. Po pravkar dokazanem, velja

|A₁∪A₂∪ · · · ∪A_n∪A_n+1|=|(A₁∪. . .∪A_n)∪A_n+1|=

=|A₁∪A₂∪. . .∪A_n|+|A_n+1| − |(A₁∪A₂∪. . .∪A_n)∩A_n+1|.

Uporabimo distributivnostni zakon na mnoˇzicah: A∩(B ∪C) = (A∩B)∪(A∩C). Ker za presek velja tudi komutativnostni zakon, je vseeno ali imamo presek na levi ali na desni strani.

Zgornji izraz je torej enak

|A₁∪A₂∪. . .∪A_n|+|A_n+1| − |(A₁∩A_n+1)∪(A₂∩A_n+1)∪. . .∪(A_n∩A_n+1)|.

Prvi ˇclen je kardinalnost unijen mnoˇzic, zato po indukcijski predpostavki velja

|A₁∪A₂∪. . .∪A_n|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩A_j|+· · ·+ (−1)ⁿ⁺¹|A₁∩A₂∩ · · · ∩A_n|.

(25)

3.1. DOKAZ POGLAVJE 3. NA ˇCELO VKLJU ˇCITEV IN IZKLJU ˇCITEV

Prav tako je zadnji ˇclen unija n mnoˇzic, zato po indukcijski predpostavki velja tudi

|(A₁∩A_n+1)∪(A₂∩A_n+1)∪. . .∪(A_n∩A_n+1)|

= X

1≤i≤n

|A_i∩A_n+1| − X

1≤i<j≤n

|A_i∩A_j∩A_n+1|+· · ·+ (−1)ⁿ⁺¹|A₁∩A₂∩ · · · ∩A_n∩A_n+1|.

Sedaj pa obe ugotovitvi uporabimo v zgornjem izrazu:

|A₁ ∪A₂∪ · · · ∪A_n+1|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩A_j|+· · ·+ (−1)ⁿ⁺¹|A₁∩A₂ ∩ · · · ∩A_n|+

+|A_n+1| − X

1≤i≤n

|A_i∩A_n+1| − X

1≤i<j≤n

|A_i∩A_j∩A_n+1|+· · ·+

−(−1)ⁿ⁺¹|A₁ ∩A₂∩ · · · ∩A_n∩A_n+1|.

Poiskusimo zdruˇziti podobne ˇclene. NamestoP

1<i<n|A_i|+|A_n+1|lahko piˇsemoP

1<i<n+1|A_i|.

Pri vsoti P

1<i<n|A_i∩A_n+1| seˇstejemo preseke mnoˇzic A_i z A_n+1 za i∈ {1,2, . . . ,n}, pri vsoti P

1≤i<j≤n|A_i∩A_j| pa preseke vseh parov moˇznih kombinacij, ki imajo indeks manjˇsi ali enak odn. Obe vsoti lahko zdruˇzimo v vse preseke parov moˇznih kombinacij, ki imajo indeks manjˇsi ali enak od n+ 1. Torej dobimo P

1<i<j<n+1|A_i∩A_j|. Podobno velja tudi za vse ostale vsote.

Od tod sledi

|A1∪ · · · ∪An+1|= X

1≤i≤n+1

|Ai| − X

1≤i<j≤n+1

|Ai∩Aj|+ X

1≤i<j<k≤n+1

|Ai∩Aj∩Ak|+

· · ·+ (−1)ⁿ⁺¹|A1∩A2∩ · · · ∩An∩An+1|,

s ˇcimer je indukcijski korak dokazan. S tem pa je dokazan tudi izrek 3.

(26)

Poglavje 4 Uporaba

V tem poglavju se bomo osredotoˇcili na primere uporabe naˇcela vkljuˇcitev in izkljuˇcitev. To naˇcelo je izjemno uporabno. Z njim tako lahko doloˇcimo ˇstevilo deranˇzmajev, to je permutacij brez fiksnih toˇck, izpeljemo formulo za Eulerjevo funkcijoϕin za Stirlingova ˇstevila druge vrste.

Poslediˇcno lahko doloˇcimo tudi ˇstevilo surjektivnih funkcij med danima konˇcnima mnoˇzicama.

Zal okvir tega diplomskega dela ne dopuˇsˇˇ ca, da bi si ogledali vse omenjene zglede uporabe naˇcela vkljuˇcitev in izkljuˇcitev, bomo pa podrobno predstavili tri. Obravnava je povzeta po [4].

4.1 Stirlingova ˇ stevila druge vrste

Da bi lahko povedali, kaj so Stirlingova ˇstevila druge vrste, moramo najprej povedati kaj je razbitje mnoˇzice.

Definicija 4 Razbitje mnoˇzice A je druˇzina < ={A₁, A₂, . . . , A_s} nepraznih, paroma disjunk- tnih podmnoˇzic mnoˇzice A, katerih unija je enaka mnoˇzici A. Mnoˇzicam A_i reˇcemo tudi deli razbitja.

Na primer, ˇce je A={a,b,c,d}je primer razbitja <={{a,b},{c,d}}

Definicija 5 Stirlingovo ˇstevilo druge vrste je ˇstevilo vseh razbitij n-elementne mnoˇzice A na k nepraznih podmnoˇzic. Oznaˇcimo ga s S(n,k), mnoˇzico teh razbitij pa oznaˇcimo s S(A,k)

Oˇcitno velja naslednje:

• S(n,k) = 0 za k > n, saj ne moremo razbiti mnoˇzice z n elementi na k razredov, ko je k veˇcji odn.

• S(n,n) = 1, ker lahko mnoˇzico z n elementi razbijemo na n razredov samo na en naˇcin, to je, da je vsak element v svojem razredu.

(27)

4.1. STIRLINGOVA ˇSTEVILA DRUGE VRSTE POGLAVJE 4. UPORABA

• S(n,1) = 1, ker lahko mnoˇzico z n elementi razbijemo na 1 razred samo na en naˇcin, to je, da so vsi elementi v enem razredu.

• S(n,0) = 0, za∀ n≥1, saj ne moremo razbiti mnoˇzice z n elementi na 0 razredov.

• Po dogovoru pa velja tudi S(0,0) = 1.

Z raˇcunskega staliˇsˇca je najvaˇznejˇsa povezava med Stirlingovimi ˇstevili druge vrste naslednja rekurzivna formula.

Trditev 1 Za vsak par n,k ∈N,1≤k≤n velja

S(n,k) = S(n−1, k−1) +k·S(n−1,k).

Dokaz:

Kot reˇceno gre za razbitje mnoˇzice z n elementi n k nepraznih delov. Oznaˇcimo poljuben element te mnoˇzice z a₀. Mnoˇzico vseh razbitij loˇcimo na dva dela. Na tiste, v katerih je a₀ sam v svojem delu, in na tiste, kjer ni. Tistih, kjer je a₀ sam v svojem delu je oˇcitno S(n−1,k−1), ker nam je preostalo n−1 stvari, ki jih moramo nato razporediti vk−1 delov.

Tistih, kjer paa₀ ni v svojem delu je k·S(n−1,k). Najprej namreˇc ostale elemente razdelimo nakdelov, nato pa se moramo ˇse odloˇciti, v katerega izmedk kosov bomo dali elementa0. Ker sta dobljeni mnoˇzici moˇznosti seveda disjunktni, dobimo formulo za S(n,k) po pravilu vsote.

S(n,k) = S(n−1, k−1) +k·S(n−1,k).

S pomoˇcjo zgornje rekurzivne formule in ˇze prej navedenih robnih pogojev lahko sestavimo tabelo, ki predstavlja Stirlingova ˇstevila druge vrste. ˇStevilo S(n,k) predstavlja ˇstevilo v n-ti vrstici in k-tem stolpcu.

(28)

n/k 0 1 2 3 4 5 6 7

0 1 0 0 0 0 0 0 0

1 0 1 0 0 0 0 0 0

2 0 1 1 0 0 0 0 0

3 0 1 3 1 0 0 0 0

4 0 1 7 6 1 0 0 0

5 0 1 15 25 10 1 0 0

6 0 1 31 90 65 15 1 0

7 0 1 63 301 350 140 21 1 Tabela 4.1: Stirlingova ˇstevila druge vrste.

Tabelo lahko gradimo induktivno po vrsticah. Ko smo na primer doloˇcili koeficiente v vrsticah od n= 0 do n= 4, dobimo S(5,3) =S(4,2) + 3·S(4,3) = 7 + 3·6 = 7 + 18 = 25.

Stirlingova ˇstevila druge vrste se pojavljajo tudi pri problemih preˇstevanja funkcij med dvema konˇcnima mnoˇzicama. O tem govori naslednja trditev.

Trditev 2 Naj bosta N in K poljubni konˇcni mnoˇzici moˇci n in k. Tedaj je ˇstevilo vseh surjektivnih preslikav iz mnoˇzice N v mnoˇzico K enako

k!S(n,k).

Dokaz:

Naj bo f : N → K poljubna surjektivna preslikava. Tedaj f mnoˇzico N na naraven naˇcin razbije na k nepraznih delov, pri ˇcemer so v posameznem delu elementi z isto f-sliko. Vsako konkretno razbitje mnoˇzice N na k delov torej da k! razliˇcnih surjektivnih funkcij iz N v K.

Treba se je namreˇc odloˇciti v katere elemente mnoˇzice K se preslikajo posamezni deli razbitja.

Tako dobimo, da je ˇstevilo surjektivnih preslikav iz N v K resk!·S(n,k).

Zgoraj smo videli, da za Stirlingovih ˇstevil druge vrste velja rekurzivna zveza, s ˇcimer si lahko pomagamo pri iraˇcunu teh ˇstevil. ˇSe vedno pa je potrebnega veliko ˇcasa za izraˇcunanje nekega S(n,k), saj je potrebno poznati vrednosti prejˇsnjih S(n,k). S pomoˇcjo naˇcela vkljuˇcitev in izkljuˇcitev lahko ˇsteviloS(n,k) zapiˇsemo kot doloˇceno vrsto.

(29)

Izrek 4 Za poljubni naravni ˇstevili n,k, kjer je k ≤n, velja

S(n,k) = 1 k!

k

X

i=1

k i

(−1)^k−i·iⁿ.

Dokaz:

To trditev bomo dokazali s pomoˇcjo rekurzivne formule iz trditve 1 in naˇcela vkljuˇcitev in izkljuˇcitev. Kot pri trditvi 2 naj bosta N in K poljubni mnoˇzici za kateri velja |N| = n in

|K| = k. A naj oznaˇcuje mnoˇzico vseh preslikav iz N v K, ki niso surjektivne. Vemo, da je vseh preslikav iz N v K po pravilu produkta natanko kⁿ, saj se lahko vsak izmed n elementov mnoˇzice N preslika v kateregakoli izmed k elementov mnoˇzice K. Tako je dovolj doloˇciti kardinalnost |A|.Po trditvi 2 velja, da je vseh surjektivnih funkcij iz N v K natanko k!S(n,k), torej je moˇc mnoˇzice A enaka kⁿ−k!S(n,k).

Sedaj pa preˇstejmo elemente mnoˇzice A ˇse na drug naˇcin.

Naj bo K = {b₁, b₂, . . . , b_n}. Za vsak i ∈ {1,2, . . . , k} naj tedaj A_i predstavlja mnoˇzico vseh tistih funkcij iz N v K, ki elementa b_i nimajo v svoji sliki. Tedaj je mnoˇzica A oˇcitno ravno unija vseh mnoˇzic Ai.

Naj boi≥1. Vzemimo poljubnoi-elementno podmnoˇzico={j₁, j₂, . . . , j_i}mnoˇzice{1,2, . . . ,k}.

Seveda gre za neurejene izbore brez ponavljanja, torej lahko to naredimo na ^k_i

naˇcinov. Tedaj presekT

j∈A_j vsebuje natanko vse funkcije iz mnoˇziceN v mnoˇzicoK\{b_j₁, b_j₂, . . . , b_j_i}in zato premore natanko (k−i)ⁿ elementov, saj se lahko vsak izmed n elementov mnoˇzice N preslika v kateregakoli izmed k−ielementov mnoˇzice K\{bj1, bj2, . . . , bji}.

Vsak tak presek ima torej (k−i)ⁿ elementov, imamo pa jih ^k_i

. Zato je vsota moˇci presekov T

j∈A_j po vseh i-elementnih podmnoˇzicah  mnoˇzice {1,2, . . . ,k} enaka k

i

(k−i)ⁿ. Po naˇcelu vkljuˇcitev in izkljuˇcitev tako dobimo, da je

|A|=

k

X

i=1

(−1)ⁱ⁺¹ k

i

(k−i)ⁿ. Tako je

k!S(n,k) =kⁿ−

k

X

i=1

(−1)ⁱ⁺¹ k

i

(k−i)ⁿ

(30)

in tako

S(n,k) = 1 k!

k

X

i=0

(−1)ⁱ k

i

(k−i)ⁿ

= 1 k!

k

X

j=0

(−1)^k−j k

k−j

jⁿ

= 1 k!

k

X

j=0

(−1)^k−j k

j

jⁿ,

pri ˇcemer smo v predzadnji enakosti uvedli substitucijoj =k−i, v zadnji pa upoˇstevali enakost

k k−j

= ^k_j .

S tem je izrek 4 dokazan.

(31)

4.2. EULERJEVA FUNKCIJA ϕ POGLAVJE 4. UPORABA

4.2 Eulerjeva funkcija ϕ

Eulerjeva funkcijaϕje dobila ime po ˇsvicarskem matematiku Leonhardu Eulerju, ki je ˇzivel in ustvarjal v 18. stoletju. Gre za enega najplodnejˇsih matematikov Evrope. V angleˇski literaturi se za Eulerjevo funkcijo ϕpogosto uporablja ime totientna funkcija. To ime je leta 1882 uvedel angleˇski matematik James Joseph Sylvester.

Funkcija ϕ ˇsteje ˇstevilo pozitivnih ˇstevil, ki so manjˇsa ali enaka n in so tuja k n. Predno izpeljemo sploˇsno formulo si oglejmo konkreten primer.

Primer 11 :

Pokaˇzimo, da velja ϕ(8) = 4.

Ce naj bo ˇsteviloˇ i, kjer je 1 ≤i ≤ 8, tuje 8, ne sme biti deljivo z 2. Primerna so torej ravno vsa liha ˇstevilo, torej 1,3,5,7. Tako res velja ϕ(8) = 4.

Izrek 5 Naj bo n ∈N in naj bodo p₁, p₂, . . . p_r vsa praˇstevila, ki delijo n. Tedaj velja

ϕ(n) =n−

r

X

i=1

n p_i +

r

X

1≤i<j≤r

n

p_i·p_j − · · ·+ (−1)^r n

p₁p₂. . . p_r =n·

r

Y

i=1

1− 1

p_i

.

Dokaz:

Po osnovnem izreku aritmetike ima vsako naravno ˇstevilo enoliˇcno faktorizacijo na praˇstevila, zato lahko n zapiˇsemo kot n=pû₁¹pû₂²· · ·pû_r^r.

Za vsak i∈ {1,2, . . . , r} naj bo P_i (konˇcna) mnoˇzica vseh naravnih ˇstevil do vkljuˇcno n, ki so deljiva sp_i. Po naˇcelu vkljuˇcitev in izkljuˇcitev tedaj velja

| [

1≤i≤r

Pi | = X

1≤i≤r

|Pi| − X

1≤i<j≤r

|Pi∩Pj|+· · ·+ (−1)^r+1|P1∩P2 ∩ · · · ∩Pr|.

Seveda pa nas zanima ϕ(n), torej ˇstevilo ˇstevil med 1 in n, ki so tuja n. To so torej ravno vsa tista ˇstevila, ki niso deljiva z nobenim izmed praˇstevil p_i,1≤i≤r. To torej pomeni, da velja

ϕ(n) =n– X

1≤i≤r

|P_i| − X

1≤i<j≤r

|P_i∩P_j|+· · ·+ (−1)^r+1|P₁∩P₂∩ · · · ∩P_r|

!

=n– X

1≤i≤r

|P_i|+ X

1≤i<j≤r

|P_i∩P_j| − · · ·+ (−1)^r|P₁∩P₂∩ · · · ∩P_r|.

(32)

Doloˇcimo sedaj kardinalnosti mnoˇzic P_i ter njihovih (veˇckratnih) presekov.

Najmanjˇse ˇstevilo v P_i je 1·p_i, najveˇcji pa _pⁿ

i ·p_i.Torej je

|P_i|= n pi

−1 + 1 = n pi

.

Kot v primeru 10 v 2. poglavju zlahka ugotovimo, da je neko ˇstevilo deljivo s p_i inp_j natanko tedaj, ko je deljivo s p_ip_j. Torej je najmanjˇse ˇstevilo v P_i ∩P_j enako1·p_i ·p_j, najveˇcje pa

n

pipj ·pipj. Tako je |Pi∩Pj |= _pⁿ

ipj. Podobno doloˇcimo ˇse velikosti ostalih veˇckratnih preslikav in konˇcno dobimo

ϕ(n) =n– X

1≤i≤r

n pi

+ X

1≤i<j≤r

n pi ·pj

− · · ·+ (−1)^r n p1·p2·. . . ·pr

=n

1− 1 p1

− 1 p2

−. . . − 1 pm

+ 1

p1 ·p2

+. . . + 1 pm−1·pm

−. . . −(−1)^m 1

p1 ·p2·. . . ·pm

=n·

1− 1 p1

·

1− 1 p2

·. . .·

1− 1 pm

kot smo trdili.

Primer 12 Doloˇcimo ˇstevilo ˇstevil, ki so manjˇsa od 210 in so tuja 210, to je, izraˇcunajmo ϕ(210).

Ce ˇstevilo 210 razbijemo na produkt samih praˇstevil, dobimo 210 = 2ˇ ·3·5· 7. Po izreku 4 lahko izraˇcunamoϕ(210) kot

ϕ(210) = 210·(1− 1

2)·(1− 1

3)·(1−1

5)·(1− 1 7)

= 210· 1 2· 2

3· 4 5 · 6

7

= 48.

(33)

Primer 13 Izraˇcunajmo ˇse ϕ(243).

Ce ˇstevilo 243 razbijemo na produkt samih praˇstevil, dobimo 243 = 3ˇ · 3· 3 ·3 · 3 = 3⁵. Po izreku 3 lahko izraˇcunamoϕ(243) kot

ϕ(243) = 243·

1− 1 3

= 243· 2 3

= 162.

V doloˇcenih posebnih primerih je formula za ϕ(n) ˇse posebej preprosta:

• Ce jeˇ p praˇstevilo, potem velja ϕ(p) = p−1.

• Ce staˇ pin q razliˇcni praˇstevili, potem nam naˇsa formula da naslednje pravilo ϕ(p·q) = (p–1)·(q–1).

• Ce jeˇ n =p^m(m≥1) potenca nekega praˇstevila, potem veljaϕ(n) = ϕ(p^m) =p^m–p^m−1 = p^m−1(p–1).

(34)

4.3. SCRABBLE POGLAVJE 4. UPORABA

4.3 Scrabble

Oglejmo si ˇse vpraˇsanje, povezano s ˇcrkovno igro Scrabble, katero je leta 1938 izumil arhitekt Alfred Mosher Buts. Predvsem v angleˇsko govoreˇcih drˇzavah je zelo popularna, kjer imajo celo turnirje v igranju. Igra poteka tako, da nekaj igralcev skuˇsa zbrati ˇcimveˇc toˇck s sestavljanjem besed vodoravno in navpiˇcno kot pri kriˇzanki. V igri uporabljamo 98 ploˇsˇcic s ˇcrkami in 2 prazni, s katerima lahko nadomestimo poljubno ˇcrko. Spodnja tabela predstavlja ˇstevilo posameznih ˇ

crk v slovenski razliˇcici igre.

A B C Cˇ D E F G H I J K L

10 2 1 1 4 11 1 2 1 9 4 3 4

M N O P R S Sˇ T U V Z Zˇ

2 7 8 2 6 6 1 4 2 4 2 1

Reˇsimo naslednjo nalogo:

Ploˇsˇcice so v neprozorni vreˇcki in vsak igralec na slepo izvleˇce sedem ploˇsˇcic. Na koliko naˇcinov lahko za prvega igralca izberemo njegovih sedem ploˇsˇcic?

Poiˇsˇcimo primerno interpretacijo naloge. V vreˇcki imamo ploˇsˇcice 25 + 1 razliˇcnih ”tipov”, saj je v slovenski abecedi 25 ˇcrk, imamo pa tudi ploˇsˇcice, ki so prazne. Ker vrstni red izbiranja ploˇsˇcic ni pomemben, gre za neurejene izbore, ker pa lahko izvleˇcemo veˇc ploˇsˇcic z isto ˇcrko, gre za neurejene izbore s ponavljanjem. Spomnimo se, da je takih izborov v primeru, da izmed n razliˇcnih reˇci izbiramo k-krat, natanko

n+k−1 n−1

=

n+k−1 k

.

Vendar pa v naˇsem primeru temu ni tako, saj je ploˇsˇcic nekaterih “tipov” manj kot 7. Nalogo bomo zato reˇsili tako, da bomo od vseh izborov sedmih ˇcrk, ne glede na omejitve, odˇsteli tiste izbore, ki se ne morejo zgoditi zaradi nezadostnega ˇstevila zahtevanih ploˇsˇcic. Imamo torej situacijo, ko imamo ploˇsˇcice n razliˇcnih tipov,s1 ploˇsˇcic tipa 1,s2 ploˇsˇcic tipa 2, . . . ,sn ploˇsˇcic tipa n. Neurejeno izberemo k ploˇsˇcic, pri ˇcemer velja k ≤s₁+s₂+. . .+s_n. V naˇsem primeru je k enak 7, vsotas₁+s₂+. . .+s_n pa 100.

Kardinalnost unije |A1 ∪A2 ∪ · · · ∪An| lahko izraˇcunamo s pomoˇcjo naˇcela vkljuˇcitev in iz- kljuˇcitev. Za uspeˇsno uporabo pa je potrebno najprej doloˇciti kardinalnosti mnoˇzic A_i in

(35)

njihovih (veˇckratnih) presekov. Velja

|A_i|=

n+ (k−s_i−1)−1 n−1

=

n+k−s_i−2 n−1

,

saj s_i+ 1 ploˇsˇcic tipai izberemo ”brez izbiranja”, preostalih k−s_i−1 pa izberemo poljubno.

Podobno velja za dvojne preseke A_i∩A_j, ko poleg preveˇc ploˇsˇcic tipa i izberemo tudi preveˇc ploˇsˇcic tipa j. Dobimo

|A_i∩A_j|=

n+ (k−s_i−1−s_j −1)−1 n−1

=

n+k−s_i−s_j−3 n−1

.

Podobno izraˇcunamo ˇse kardinalnosti ostalih veˇckratnih presekov.

Mnoˇzica A v naˇsem primeru predstavlja vse izbore sedmih ˇcrk, ne glede na omejitve ˇstevila posameznih ˇcrk. To pomeni, da je moˇc mnoˇzice A enaka

|A|=

26 + 7−1 26−1

= 32

25

= 32!

25!·7! = 3 365 856.

Zgoraj smo zaradi jasnosti uporabljali mnoˇzice A₁, A₂, . . ., sedaj pa bodo indeksi mnoˇzic ˇcrke.

Tako bo na primerAC mnoˇzica vseh izborov brez omejitev, pri katerih smo izbrali preveˇc ploˇsˇcic s ˇcrkoC. Dogovorimo se ˇse, da je mnoˇzicaA₀ mnoˇzica vseh izborov s preveˇc izbranimi praznimi ploˇsˇcicami.

Kardinalnosti posameznih mnoˇzic A_X so seveda odvisne od ˇstevila ploˇsˇcic pripadajoˇcega tipa, ki so na voljo. Loˇcimo primere glede na ˇstevilo t ploˇsˇcic posameznega tipa.

t= 1 : |A_C|=|ACˇ|=|A_F|=|A_H|=|ASˇ|=|AZˇ|=

26 + (7−1)−2 25

= 30

25

= 142 506.

Kardinalnost dvojnih presekov dveh mnoˇzic takˇsnih tipov:

|AX1 ∩AX2|=

26 + (7−1−1)−3 25

= 28

25

= 23 751.

(36)

4.3. SCRABBLE POGLAVJE 4. UPORABA Sedaj moramo ugotoviti ˇse koliko je takih presekov. Imamo 6 takih tipov izmed njih pa moramo izbrati dva. Vseh naˇcinov je natanko ⁶₂

= 15. Tako tukaj dobimo 15 razliˇcnih dvojnih presekov, vsak izmed katerih je velikosti 23 751.

Kardinalnost trojnih presekov treh takih je

|A_X₁ ∩A_X₂ ∩A_X₃|=

26 + (7−1−1−1)−4 25

= 26

25

= 26

1

= 26.

Podobno kot za dvojne preseke, ugotovimo, da je takih trojnih presekov ⁶₃

= 20.

Vsi nadaljni veˇckratni preseki so seveda prazni, saj pri sedmih ploˇsˇcicah ne moremo veˇc kot za tri razliˇcne tipe vzeti vsaj dveh.

t= 2 :|A₀|=|A_B|=|A_G|=|A_M|=|A_P|=|A_U|=|A_Z|=

26 + (7−2)−2 25

= 29

25

= 23751.

|AX1 ∩AX2|=

26 + (7−2−2)−3 25

= 26

25

= 26

1

= 26.

Dvojnih presekov takih mnoˇzic je ⁷₂

= 21.

Kot zgoraj so nadaljni veˇckratni preseki takih mnoˇzic prazni.

t= 3 : |A_K|= ^{26+(7−3)−2}₂₅

= ²⁸₂₅

= 3276.

t= 4 : |AD|=|AJ|=|AL|=|AT|=|AV|= ^{26+(7−4)−2}₂₅

= ²⁷₂₅

= 351.

Dvojni in nadaljni veˇckratni preseki so seveda prazni.

Ker nimamo nobene ˇcrke, ki bi se pojavila petkrat, spustimo t = 5.

(37)

t= 6 : |A_R|=|A_S|= ^{26+(7−6)−2}₂₅

= ²⁵₂₅

= 1.

Preseki so seveda prazni.

Sedaj imamo samo ˇse ˇcrke, ki se pojavijo sedem ali veˇc kot sedemkrat. Mnoˇzice A_X za X, ki se pojavi vsaj na sedmih ploˇsˇcicah, so seveda prazne.

Ostalo nam je ˇse nekaj moˇznih dvojnih in trojnih presekov med mnoˇzicami za ˇcrke z razliˇcnimi kratnostmi ploˇsˇcic. Naj mnoˇzica A_t=i predstavlja poljubno mnoˇzico A_X, kjer imamo i ploˇsˇcic tipa X. Tedaj velja

|At=1∩At=2|=

26 + (7−1−2)−3 25

= 27

25

= 351.

Sedaj moramo izraˇcunati ˇse koliko je takih presekov. Imamo 6 mnoˇzic za tip t= 1 in 7 mnoˇzic za t = 2. Potrebujemo po eno mnoˇzico vsake vrste, torej moramo izbrati po eno mnoˇzico posamezne vrste. Ker sta ti izbiri oˇcitno neodvisni, velja pravilo produkta. Torej je takih dvojnih presekov ⁶₁

· ⁷₁

= 6·7 = 42, vsak izmed katerih je velikosti 351.

|A_t=1∩A_t=3|=

26 + (7−1−3)−3 25

= 26

25

= 26

Takih dvojnih presekov je, po podobnem premisleku kot zgoraj, ⁶₁

· ¹₁

= 6·1 = 6.

|A_t=1∩A_t=4|=

26 + (7−1−4)−3 25

= 25

25

= 1.

Dvojnih presekov take vrste je ⁶₁

· ⁵₁

= 6·5 = 30.

|At=2∩At=3|=

26 + (7−2−3)−3 25

= 25

25

= 1,

dvojnih presekov, take vrste pa je ⁷₁

· ¹₁

= 7·1 = 7.

Seveda so vsi ostali dvojni preseki prazni, saj izbiramo samo sedem ploˇsˇcic.

Obstaja samo ena vrsta nepraznih trojnih presekov med mnoˇzicami za ˇcrke z razliˇcnimi kratnostmi ploˇsˇcic:

|A_t=1∩A_t=2∩A_t=1|=

26 + (7−1−2−1)−4 25

= 25

25

= 1.

(38)

Takih trojnih presekov mnoˇzic je ⁶₂

· ⁷₁

= 105.

Sedaj moramo le ˇse zdruˇziti vse delne rezultate v en raˇcun in tako izraˇcunamo, kar nas zanima ˇ

ze od zaˇcetka. Naj moˇc mnoˇzice B predstavlja ˇstevilo naˇcinov, na katerega lahko za prvega igralca izberemo sedem ploˇsˇcic. Tedaj velja

|B|=|A| − |A₀∪A_A∪. . .∪AZˇ|

=|A| −6· |A_t=1| −7· |A_t=2| − |A_t=3| −5· |A_t=4| −2· |A_t=6|+ 15· |A_t=1∩A_t=1|

+ 21· |At=2∩At=2|+ 42· |At=1∩At=2|+ 6· |At=1∩At=3|+ 30· |At=1∩At=4|+ 7· |At=2∩At=3|

−20· |A_t=1∩A_t=1∩A_t=1| −105· |A_t=1∩A_t=2∩A_t=1|)

= 3 365 856−6·142 506−7·23 751−3276−5·351−2·1 + 15·3276 + 21·26 + 42·351 + 6·26 + 30·1 + 7·1−20·26−105·1

= 2 403 526

Za prvega igralca lahko torej nakljuˇcno izberemo sedem ploˇsˇcic iz vreˇcke, ki vsebuje 100 ploˇsˇcic, na 2 403 526 naˇcinov.

(39)

Poglavje 5

Sklepne ugotovitve

Tekom pisanja smo ugotovili, da na temo naˇcela vkljuˇcitev in izkljuˇcitev ter njegove uporabe obstaja obseˇzna literatura, ki je veˇcinoma v tujem jeziku. Ravno to je bil motiv za pisanje tega diplomskega dela. Dodaten motiv je predstavljala tudi razumljivost teme, saj se veˇcina srednjeˇsolcev muˇci z razumevanjem kombinatorike.

V diplomskem delu smo raziskali teoretiˇcno ozadje, preuˇcili dokaz in si ogledali nekaj kon- kretnih primerov uporabe kombinatoriˇcnega orodja za doloˇcitev kardinalnosti unije mnoˇzice po imenu naˇcelo vkljuˇcitev in izkljuˇcitev. Ugotovili smo, da je naˇcelo vkljuˇcitev in izkljuˇcitev moˇcno in uporabno orodje, s katerim lahko na relativno lahek naˇcin izpeljemo nekatere rezultate, ki bi jih sicer, le steˇzka dobili. Zaradi nekoliko veˇcje zahtevnosti, se tekom srednjeˇsolskega izobraˇzevanje z njim ne seznanimo.

Upam, da smo v tem diplomskem delu predstavili naˇcelo vkljuˇcitev in izkljuˇcitev na naˇcin, ki bo razumljiv tudi nadebudnim osnovnoˇsolcem in srednjeˇsolcem.

(40)

Literatura

[1] Juvan, M. in Potoˇcnik, P. (2007).Teorija grafov in kombinatorika: primeri in reˇsene naloge, Ljubljana: DMFA.

[2] Slomson, A. (1991). An introduction to combinatorics, London: Chapman and Hall

[3] ˇSparl, P. (2009). Reˇsene naloge iz raˇcunalniˇske matematike: ˇstudijsko gradivo, Ljubljana:

samozaloˇzba.

[4] ˇSparl, P. (ˇstudijsko leto 2012/2013). Zapiski predavanj iz diskretne matematike

[5] Wallis, W. D. in George, J. C. (2011).Introduction to combinatorics, New York: CRC Press.

(41)

Izjava o avtorstvu

Spodaj podpisana Ines Medved izjavljam, da sem avtorica tega diplomskega dela, ki sem ga napisala pod vodstvom doc. dr. Primoˇza ˇSparla in as. dr. Boˇstjana Kuzmana.

Ines Medved

Ljubljana, september 2013