Lukumääriä ja kombinatoriikkaa
Joukon mahtavuus eli kardinaliteetti [-]
Jos A on joukko niin |A| on A:n alkioden lukumäärä, eli kardinaliteetti eli mahtavuus. Jos tämä luku on äärellinen niin ainoa, mutta usein kaikkea muuta kuin yksinkertainen, ongelma voi olla miten tämä luku määritetään, ja tätä varten käytetään usein erilaisia kombinatorisia menetelmiä.
Mutta jos se ei ole äärellinen niin osoittautuu, ettei vastaukseksi aina kelpaa "ääretön" ja sen sijaan lähtökohdaksi otetaan huomio, että jos kahden äärellisen joukon välillä on bijektio, niin joukoissa on yhtä monta elementtiä.
Täsmällisemmin: [+]- Kahdella joukolla A ja B on sama lukumäärä alkioita eli ne ovat yhtä mahtavia ja |A|=|B|, jos on olemassa bijektio A→B.
- Joukolla A on vähemmän tai yhtä monta alkiota kuin joukolla B, eli |A|≤|B|, jos on olemassa injektio A→B. Erityisesti, |A|≤|B| jos A⊆B.
- Joukolla A on vähemmän alkioita kuin joukolla B, eli |A|<|B|, jos on olemassa injektio A→B mutta ei bijektiota A→B.
- Jos A={0,1,2,…,n−1} niin |A|=n ja |∅|=0.
- Joukko A on äärellinen jos on olemassa n∈N0 siten, että |A|=n.
- Joukko A on numeroituva jos |A|=|N0| ja ylinumeroituva jos |N0|<|A|.
Esimerkki: |Z|=|N0| [+]
Äärettömän joukon karakteristinen
ominaisuus onkin, että siitä voidaan poistaa alkioita
ilman, että jäljelle jäävien
alkioiden "lukumäärä" muuttuu.

Esimerkki: |Q|=|Z| [+]
Olkoon Q+={x∈Q:x>0} ja N+={n∈Z:n>0}. Jos konstruoimme surjektion h:N+→Q+ niin saamme injektion f:Q+→N+ määrittelemällä f(x)=min{j∈N+:h(j)=x}, ja siitä injektion f:Q→Z määrittelemällä f(0)=0 ja f(−x)=−f(x) kun x∈Q+ joten |Q|≤|Z|. Koska selvästikin |Z|≤|Q| niin |Q|=|Z|.
Meidän pitää siis konstruoida surjektio h:N+→Q+ ja tämän
teemme seuraavalla tavalla:
Kun n≥0 on parillinen niin
h(n⋅(n+1)2+j)=jn+2−j,j=1,…,n+1,
ja kun n≥0 on pariton niin
h(n⋅(n+1)2+j)=n+2−jj,j=1,…,n+1.
Huomaa, että
n(n+1)2+(n+1)=(n+1)((n+1)+1)2.
Tämä funktio on surjektio koska jos x∈Q+ niin x=pq
missä p≥1 ja q≥1 ja jos
valitsemme n=p+q−2 niin p≤n+1 ja
q≤n+1 joten jos
n on parillinen niin
h(n⋅(n+1)2+p)=pq=x,
ja jos n on pariton niin
h(n⋅(n+1)2+q)=pq=x.

Summaperiaate [-]
Yksinkertaisin muoto:
Jos A ja B ovat kaksi (äärellistä) joukkoa
siten, että A∩B=∅ niin
|A∪B|=|A|+|B|.
Tästä seuraa, että jos B⊆A niin |A∖B|=|A|−|B|.
Yleinen tapaus eli seulaperiaate [-]

Pari epäyhtälöä [+]
-
Koska A1∩A2∩A3⊆A1∩A2 niin |A1∩A2∩A3|≤|A1∩A2|.
Samoin pätee |A1∩A2∩A3|≤|A2∩A3| ja |A1∩A2∩A3|≤|A1∩A3|. - Koska (A1∩A2)∪(A1∩A3)=A1∩(A2∪A3)⊆A1 niin |A1|≥|(A1∩A2)∪(A1∩A3)|=|A1∩A2|+|A1∩A3|−|A1∩A2∩A1∩A3|, josta seuraa, että |A1∩A2∩A3|≥|A1∩A2|+|A1∩A3|−|A1|. Vaihtamalla A1, A2 ja A3 keskenään saamme myös epäyhtälöt |A1∩A2∩A3|≥|A1∩A2|+|A2∩A3|−|A2| ja |A1∩A2∩A3|≥|A1∩A3|+|A2∩A3|−|A3|.


Tuloperiaate [-]
Yksinkertaisin muoto:
Jos A ja B ovat kaksi (äärellistä) joukkoa niin
|A×B|=|A|⋅|B|.
Yleinen tapaus[-]
Esimerkki [+]
Opiskelijat P, Q ja R tulevat tietokonesaliin, missä on 4 vapaata paikkaa a, b, c ja d. Jos haluamme laskea monellako tavalla he voivat valita paikkansa niin ensin toteamme, että jos P saa ensimmäisenä valita paikkansa niin hänellä on vaihtoehtoa.
Jos Q tekee valintansa seuraavana hänellä on vaihtoehtoa.
Jos R tekee valintansa viimeisenä hänellä on enää vain vaihtoehtoa.
Näin ollen vaihtoehtojen lukumäärä on 4⋅3⋅2=24.


Lokero- eli kyyhkyslakkaperiaate [+]
Jos m≥1 esinettä laitetaan n≥1 lokeroon niin ainakin yhdessä lokerossa on vähintään ⌈mn⌉ esinettä!
Miksi? [+]
Esimerkki [+]
Olkoon S joukon {1,2,…,2⋅n−1,2⋅n} osajoukko siten, että |S|=n+1. Silloin joukkoon S kuuluu kaksi eri lukua a ja b siten, että joko a jakaa b:n tai b jakaa a:n (eli b=a⋅m tai a=b⋅n).
Miksi? [+]- Voimme esittää S:n luvut muodossa 2kj⋅qj missä kj≥0, 1≤qj≤2⋅n, qj on pariton, j=1,2,…,n+1 ja lisäksi [ki,qi]≠[kj,qj] kun i≠j.
- Parittomat luvut qj, j=1,…,n+1 kuuluvat siis joukkoon {1,2,…,2⋅n−1,2⋅n} ja tässä joukossa on n paritonta lukua 1,3,5,…,2⋅n−1.
- Lokeroperiaatteen nojalla on olemassa luvut i≠j siten, että qi=qj jolloin ki≠kj koska [ki,qi]≠[kj,qj].
- Voimme valita a=2ki⋅qi ja
b=2kj⋅qj jolloin väite pätee koska joko ki<kj jolloin b=a⋅2kj−ki tai kj<ki jolloin
a=b⋅2ki−kj.


Kertoma n! [+]

Binomikerroin (nk)[+]

Otokset: Järjestetty - järjestämätön, palauttamatta - palauttaen [+]
Yhteenveto [-]
Kun joukosta, jossa on n alkiota valitaan k alkiota niin tämä voidaan tehdä joko palauttamatta tai palauttaen ja otos voi olla järjestetty tai järjestämätön jolloin vaihtoehtojen lukumäärät ovat seuraavat:
Palauttamatta | Palauttaen | |
Järjestetty | n!(n−k)! | nk |
Järjestämätön | (nk) | (k+n−1n−1) |

Järjestetty otos palauttamatta [-]

Järjestetty otos palauttaen [-]

Järjestämätön otos palauttamatta eli osajoukon valinta [-]


Järjestämätön otos palauttaen [-]
Olkoon esimerkiksi n=6 ja A={x1,x2,…,x6}. Kun valitsemme esimerkiksi k=11 kertaa alkion joukosta A eikä valintajärjestyksellä ole merkitystä niin tulos voi olla esimerkiksi seuraava: x1x1x2x4x4x4x5x5x6x6x6 Sen sijaan, että kirjoitamme auki alaindeksit niin voimme käyttää erotusmerkkiä | osoittamaan missä kohdissa indeksi muuttuu jolloin lista näyttää seuraavanlaiselta: xx|x||xxx|xx|xxx ja || tarkoittaa, ettemme ole valinneet alkiota x3 kertaakaan.
Jos siis muodostamme jonon, jonka pituus on
k+(n−1) ja jossa on k kertaa x ja n−1
kertaa | niin saamme otoksen, jonka koko on k
ja joka on otettu palauttaen joukosta
A={x1,x2,…,xn} missä
valintajärjestyksellä ei ole merkitystaä. Jonot
missä x:t ja |:t ovat eri paikoissa määrittävät
erilaiset otokset ja konstruimme tällaisen jonon
valitsemalla (palauttamatta ja ilman järjestystä)
ne k paikkaa k+(n−1)-pituisesta jonosta joihin
tulee x tai vastaavasti ne n−1 paikkaa, joihin
tulee |. Näin ollen vaihtoehtojen lukumääräksi
tulee (k+n−1n−1)=(k+n−1k).

Allokointimalli eli vaihtoehtoinen ajattelutapa [-]
- Numeroidut pallot ↔ Järjestetty otos
- Identtiset pallot ↔ Järjestämätön otos
- Jokaiseen laatikkoon korkeintaan yksi pallo ↔ Otos palauttamatta
- Jokaiseen laatikkoon mielivaltainen määrä palloja ↔ Otos palauttaen
Pallojen lukumäärä laatikoissa | ||
korkeintaan 1 | ei rajoituksia | |
Numeroidut pallot | n!(n−k)! | nk |
Identtiset pallot | (nk) | (k+n−1n−1) |

Esimerkki [+]
Tässä oletetaan, että tehtäväpaperit ovat identtiset mutta tenttijät eivät ole.
Ensimmäinen, järkevä, vaihtoehto on että jokaiselle tenttijälle annetaan korkeintaan yksi paperi. Silloin on kysymys siitä monellako tavalla voimme 160 henkilön joukosta valita ne 150, jotka saavat paperin. Tässä on kyse järjestämättömästä otoksesta palauttamatta joten vaihtoehtoja on (160150)=(16010).
Toinen, vähemmän järkevä, vaihtoehto on, ettei aseteta mitään
rajoituksia sille montako paperia sama henkilö voi saada. Silloin
valvojat valitsevat 150 kertaa tenttijän, jolle
paperi annetaan, joukosta, jossa on 160 alkiota, ''palauttaen'' eikä
valintajärjestyksellä ole merkitystä. Vaihtoehtojen lukumääräksi tulee
silloin (150+160−1160−1)=309!159!⋅150!.

Esimerkki [+]


Esimerkki [+]



Multinomikerroin [+]
- (nn1,n2,…,nm) on vaihtoehtojen lukumäärä kun joukko A jaetaan osajoukoiksi Aj, j=1,…,m siten, että ∪mj=1Aj=A, Ai∩Aj=∅ kun i≠j, ja |Aj|=nj.
- (nn1,n2,…,nm) on vaihtoehtojen lukumäärärä kun järjestetään n1 oliota tyyppiä y1, n2 tyyppiä y2 jne. missä n=n1+n2+…+nm ja samaa tyyppiä olevat oliot ovat identtiset.
- Jos A on joukko, jossa on n alkiota ja B={y1,…,ym} on joukko, jossa on m alkiota ja n1,n2,…,nm ovat ei-negatiivisia lukuja siten, että n1+n2+…nm=n niin (nn1,n2,…,nm) on niiden funktioiden f:A→B lukumäärä joille pätee |{x∈A:f(x)=yj}|=nj.
Esimerkki [+]



Binomi- ja multinomikaavat [+]
(x+y)n=n∑j=0(nj)xjyn−j ja (x1+…+xm)n=∑n1+…+nm=nnj≥0(nn1,n2,…,nm)xn11⋅…⋅xnmm.
Miksi? [+]


Funktioiden lukumäärä [+]
- Funktioden A→B lukumäärä on
|BA|=|B||A|=nm.
Miksi? [+]
Funktio f:A→B on järjestetty m-kokoinen otos palauttaen joukosta, jossa on n alkiota.
- Injektioiden A→B lukumäärä on n⋅(n−1)⋅…⋅(n−m+1)=n!(n−m)! kun m≤n
ja 0 kun m>n.
Miksi? [+]
Injektio A→B on järjestetty m-kokoinen otos palauttamatta joukosta, jossa on n alkiota.
- Surjektioiden A→B lukumäärä on n∑k=0(nk)(−1)n−kkm.
Miksi? [+]
Olkoon B={b1,b2,…,bn}, F=BA kaikkien funktioiden A→B joukko ja Fj=(B∖{bj})A⊂F kaikkien funktioiden A:→B∖{bj} joukko eli niiden F:n alkioiden f joukko joille pätee, että f(x)≠bj kaikilla x∈A. Surjektioiden joukko on siten F∖∪nj=1Fj.
Nyt Fj1∩Fj2∩…∩Fjr on joukko (B∖{bj1,bj2,…bjr})A johon kuuluvat kaikki funktiot A→B jotka eivät saa arvoja bj1,…,bjr. Jos 1≤j1<…<jr≤n niin |Fj1∩Fj2∩…∩Fjr|=(n−r)m. Koska on (nr) eri tapaa valita indeksit 1≤j1<…<jr≤n niin seulaperiaatteesta seuraa, että surjektioiden A→B lukumäärä on nm−(n∑r=1(−1)r+1(nr)(n−r)m)=n∑r=0(−1)r(nr)(n−r)mn−r=k=n∑k=0(nk)(−1)n−kkm. Huomaa, että kun m<n ei ole surjektioita A→B joten silloin ∑nk=0(nk)(−1)n−kkm=0, mikä ehkä ei ole aivan ilmeistä.

Sekalaisia esimerkkejä [+]
Korttiesimerkki [+]
- Valitsemme ensin ne kaksi paikkaa, joihin kuningattaret tulevat. Vaihtoehtoja on (52)=10.
- Sitten valitsemme kuningattaret näihin paikkoihin ja nyt vaihtoehtojen lukumäärä on 4⋅3=12 koska on otettava huomioon missä järjestyksessä ne tulevat.
- Lopuksi valitsemme muut kolme korttia 48:n kortin joukosta jolloin vaihtoehtojen lukumääräksi tulee 48⋅47⋅46=103776
- Tuloperiaatteen nojalla erilaisten rivien lukumääräksi tulee 10⋅12⋅103776=12453120.


Osajoukkojen lukumäärä: |P(A)|=2|A| [+]

Montako vertailua tarvitaan järjestämisalgoritmissa? [+]
Jos meillä on n erisuurta lukua ja haluamme järjestää ne suuruusjärjestykseen niin on olemassa algoritmi, joka pahimmassakin tapauksessa tekee korkeintaan nlog2(n) vertailua (esimerkiksi niin, että ensin jaetaan luvut kahteen joukkoon, nämä laitetaan järjestykseen tällä algoritmilla ja sitten joukot yhdistetään niin että järjestys säilyy.)
Mutta onko olemassa algoritmi, joka käyttää oleellisesti vähemmän, (esim. O(nlog(log(n)))) vertailuja, pahimmassakin tapauksessa?
Vastaus [+]
- Koska voimme järjestää n lukua n! eri tavalla järjestämisalgoritmin pitää pystyä tuottamaan n! eri vastausta.
- Koska jokaisen vertailun tuloksena on korkeintaan kaksi vaihtoehtoa niin tuloperiaatteen takia algoritmi, joka tekee korkeintaan m vertailua tuottaa korkeintaan 2m eri vastausta.
- Jos järjestysalgoritmi toimii niin 2m≥n! eli m≥log2(n!). Koska
log2(n!)=log2(1⋅2⋅…⋅n)=n∑j=1log2(j)≥n∑j=⌊n2⌋log2(j)≥n2log2(n3)=n2log2(n)−n2log2(3)≥n3log2(n),
kun n≥33 joten
oleellisesti parempi tulos kuin nlog2(n) ei ole
mahdollinen.

Esimerkki: Monellako tavalla voidaan jakaa joukko, johon kuuluu n alkiota, k:hon ei-tyhjään osajoukkoon? [+]
Toisella tavalla: Monellako tavalla voimme laittaa n numeroitua palloa k:hon identtiseen laatikkoon, siten, että jokaiseen laatikkoon tulee ainakin yksi pallo? Oleellista on siis tässä, että pallot (eli alkuperäisen joukon alkiot) on numeroitu mutta laatikot ovat identtiset (eli osajoukkoja ei numeroida).
Olkoon tämä lukumäärä S(n,k), ns. Stirlingin (2. lajin) luku. Mitä voimme sanoa näistä luvuista?
- Selvästikin (?) S(n,1)=S(n,n)=1 ja S(n,k)=0 jos k>n.
- S(n,k)=S(n−1,k−1)+kS(n−1,k) kun 2≤k≤n−1.
Miksi? [+]
Olkoon x kyseisen joukon tietty alkio. Silloin meillä on kaksi toisiaan poissulkevaa tapausta:
- {x} on yksi osajoukoista (johon siis ei kuulu muita alkioita): Muut n−1 alkiota on jaettava k−1:een ei-tyhjään osajoukkoon ja vaihtoehtojen lukumäärä on S(n−1,k−1).
- {x} ei ole yksi osajoukoista: Jaetaan ensin muut
n−1 alkiota k:hon ei-tyhjään osajoukkoon (S(n−1,k)
vaihtoehtoa) jonka jälkeen x sijoitetaan
johonkin näistä osajoukoista (k
vaihtoehtoa) jolloin kaikkien vaihtoehtojen
lukumäärä on kS(n−1,k).
- S(n,k)=1k!k∑j=0(kj)(−1)k−jjn. Miksi? [+]
Voimme numeroida k osajoukkoa k! eri tavalla ja jako ei-tyhjiin numeroituihin osajoukkoihin määrittelee funktion f alkuperäisestä joukosta joukkoon {1,2,…,k} siten, että f(x)=m jos x kuuluu osajoukkoon, jonka numero on m. Tämä funktio f on surjektio koska osajoukot ovat ei-tyhjät ja jokainen tällainen surjektio määrittää osituksen ei-tyhjiin osajoukkoihin. Tästä seuraa, että Sur(n,k)=k!S(n,k) missä Sur(n,k) on surjektioiden lukumäärä joukosta, jossa on n alkiota joukkoon, jossa on k alkiota. Sur-funktiolle johdetun kaavan avulla saamme väiteen.
- S(n,2)=2n−1−1.
Miksi? [+]
Olkoon x tietty joukon alkio. Muut n−1 alkiota laitetaan joko samaan joukkoon kuin x tai sitten toiseen, eli n−1 kertaa on valittava kahden vaihtoehdon väliltä joten vaihtoehtoja on 2n−1 mutta yksi ei kelpaa koska joukkojen pitää olla ei-tyhjiä joten S(n,2)=2n−1−1.
- S(n,n−1)=1(n−1)!n−1∑j=0(n−1j)(−1)k−jjn=(n2).
Miksi? [+]Kun osajoukkoja on n−1 kappaletta niin yhteen joukkoon tulee kaksi alkiota ja vaihtoehdot eroavat toisistaan ainoastaan siinä, mitkä kaksi alkiota laitetaan samaan osajoukkoon ja joukosta, jossa on n alkiota voidaan valita osajoukko, johon kuuluu kaksi alkiota (n2):lla eri tavalla.

