Diskreetin matematiikan perusteet

Lukumääriä ja kombinatoriikkaa

Joukon mahtavuus eli kardinaliteetti [-]

Jos $A$ on joukko niin $\card{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 $\card A =\card B$ , jos on olemassa bijektio $A\to B$ .
Joukolla $A$ on vähemmän tai yhtä monta alkiota kuin joukolla $B$ , eli $\card A\leq \card B$ , jos on olemassa injektio $A\to B$ . Erityisesti, $\card{A}\leq \card{B}$ jos $A\subseteq B$ .
Joukolla $A$ on vähemmän alkioita kuin joukolla $B$ , eli $\card A< \card B$ , jos on olemassa injektio $A\to B$ mutta ei bijektiota $A\to B$ .
Jos $A=\{0,1,2,\ldots ,n-1\}$ niin $\card A=n$ ja $\card\emptyset =0$ .
Joukko $A$ on äärellinen jos on olemassa $n\in \N_0$ siten, että $\card A=n$ .
Joukko $A$ on numeroituva jos $\card{A}=\card{\N_0}$ ja ylinumeroituva jos $\card{\N_0} < \card{A}$ .

Esimerkki: $\card{\Z}=\card{\N_0}$ [+]

Luonnollisten lukujen joukko

$N_0$ on (tietenkin) kokonaislukujen joukon

$\Z$ aito osajoukko mutta siitä huolimatta esimerkiksi seuraava funktio

$f$ on bijektio

$N_0\to \Z$ :

$\begin{align*} f(0) &= 0,\\ f(2\cdot k-1) &= k, \quad k\geq 1,\\ f(2\cdot k)&= -k, \quad k\geq 1. \end{align*}$ Huom [+]

Esimerkki: $\card{\Q}= \card{\Z}$ [+]

Olkoon $\Q_+=\set{x\in \Q\mid x>0}$ ja $\N_+=\set {n\in\Z\mid n>0}$ . Jos konstruoimme surjektion $h:\N_+\to \Q_+$ niin saamme injektion $f:\Q_+\to N_+$ määrittelemällä $f(x)= \min\set{j\in \N_+\mid h(j)=x},$ ja siitä injektion $f:\Q\to \Z$ määrittelemällä $f(0)=0$ ja $f(-x)= -f(x)$ kun $x\in \Q_+$ joten $\card{\Q}\leq \card{\Z}$ . Koska selvästikin $\card{\Z} \leq \card{\Q}$ niin $\card{\Q}= \card{\Z}$ .

Meidän pitää siis konstruoida surjektio $h: \N_+\to \Q_+$ ja tämän teemme seuraavalla tavalla:
Kun $n\geq 0$ on parillinen niin $h\left(\frac {n\cdot(n+1)}2+j\right )= \frac j{n+2-j}, \quad j=1,\ldots,n+1,$ ja kun $n\geq 0$ on pariton niin $h\left(\frac {n\cdot(n+1)}2+j\right )= \frac {n+2-j}j, \quad j=1,\ldots,n+1.$ Huomaa, että $\dfrac {n(n+1)}2+(n+1)= \dfrac {(n+1)((n+1)+1)}2$ .

Tämä funktio on surjektio koska jos $x\in \Q_+$ niin $x=\frac pq$ missä $p\geq 1$ ja $q\geq 1$ ja jos valitsemme $n=p+q-2$ niin $p\leq n+1$ ja $q\leq n+1$ joten jos $n$ on parillinen niin $h\left(\frac {n\cdot(n+1)}2+p\right )= \frac pq=x,$ ja jos $n$ on pariton niin $h\left(\frac {n\cdot(n+1)}2+q\right )=\frac pq=x.$

Summaperiaate [-]

Yksinkertaisin muoto:
Jos $A$ ja $B$ ovat kaksi (äärellistä) joukkoa siten, että $A\cap B=\emptyset$ niin $\begin{equation*} \card{A\cup B}= \card A + \card B. \end{equation*}$ Tästä seuraa, että jos $B\subseteq A$ niin $\card{A\setminus B} = \card{A}-\card{B}$ .

Yleinen tapaus eli seulaperiaate [-]

Jos

$A_j$ ,

$j=1,2,\ldots$ ovat äärellisiä joukkoja niin

$\begin{align*} &\card{A_1\cup A_2} = \card{A_1} +\card{A_2}-\card{A_1\cap A_2},\\ &\card{A_1\cup A_2\cup A_3}= \card{A_1} +\card{A_2}+\card{A_3}\\ &\quad -\card{A_1\cap A_2} -\card{A_1\cap A_3} -\card{A_2\cap A_3}\\ &\quad + \card{A_1\cap A_2\cap A_3}, \\ &\abs{\bigcup_{j=1}^k A_j} = \sum_{r=1}^k (-1)^{r+1} \sum_{1\leq {j_1}<{j_2}<\ldots < {j_r}\leq k} \abs{\bigcap_{i=1}^r A_{j_i}}. \end{align*}$

Pari epäyhtälöä [+]

Olkoot

$A_1$ ,

$A_2$ ja

$A_3$ kolme joukkoa.

Koska $A_1\cap A_2\cap A_3 \subseteq A_1\cap A_2$ niin $\card{A_1\cap A_2\cap A_3} \leq \card{A_1\cap A_2}$ .
Samoin pätee $\card{A_1\cap A_2\cap A_3} \leq \card{A_2\cap A_3}$ ja $\card{A_1\cap A_2\cap A_3} \leq \card{A_1\cap A_3}$ .
Koska $(A_1\cap A_2)\cup (A_1\cap A_3)= A_1\cap (A_2\cup A_3)\subseteq A_1$ niin josta seuraa, että $\card{A_1\cap A_2\cap A_3} \geq \card{A_1\cap A_2} + \card{A_1\cap A_3} - \card {A_1}.$ Vaihtamalla $A_1$ , $A_2$ ja $A_3$ keskenään saamme myös epäyhtälöt $\card{A_1\cap A_2\cap A_3} \geq \card{A_1\cap A_2} + \card{A_2\cap A_3} - \card {A_2}$ ja $\card{A_1\cap A_2\cap A_3} \geq \card{A_1\cap A_3} + \card{A_2\cap A_3} - \card {A_3}.$

Tuloperiaate [-]

Yksinkertaisin muoto:
Jos $A$ ja $B$ ovat kaksi (äärellistä) joukkoa niin $\begin{equation*} \card{A\times B} = \card A \cdot \card B. \end{equation*}$

Yleinen tapaus[-]

Jos valinta- tai päätösprosessissa on

$k$ vaihetta ja vaiheessa

$j$ on

$n_j$ vaihtoehtoa, riippumatta siitä mitä valintoja tai päätöksiä on aikaisemmissa vaiheissa tehty, ja jos kaikki valinnat johtavat erilaisiin lopputuloksiin, niin kaikkien vaihtoehtojen lukumääräksi tulee

$\begin{equation*} n_1\cdot n_2\cdot \ldots \cdot n_k. \end{equation*}$

Esimerkki [+]

0,0

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.

Näin ollen vaihtoehtojen lukumäärä on $4\cdot 3\cdot 2=24$ .

Lokero- eli kyyhkyslakkaperiaate [+]

Jos $m\geq 1$ esinettä laitetaan $n\geq 1$ lokeroon niin ainakin yhdessä lokerossa on vähintään $\displaystyle \left\lceil\frac mn\right\rceil$ esinettä!

Miksi? [+]

Jos samassa lokerossa on korkeintaan

$k$ esinettä niin

$k\cdot n \geq m$ joten

$k\geq \frac mn$ ja koska määritelmän mukaan

$\lceil\frac mn\rceil$ on pienin kokonaisluku joka on suurempi tai yhtäsuuri kuin

$\frac mn$ niin

$k\geq \lceil\frac mn\rceil$ .

Esimerkki [+]

Olkoon $S$ joukon $\{1,2,\ldots,2\cdot n-1,2\cdot n\}$ osajoukko siten, että $\card{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\cdot m$ tai $a=b\cdot n$ ).

Miksi? [+]

Voimme esittää $S$ :n luvut muodossa $2^{k_j}\cdot q_j$ missä $k_j\geq 0$ , $1\leq q_j\leq 2\cdot n$ , $q_j$ on pariton, $j=1,2,\ldots, n+1$ ja lisäksi $[k_i,q_i]\neq [k_j,q_j]$ kun $i\neq j$ .
Parittomat luvut $q_j$ , $j=1,\ldots ,n+1$ kuuluvat siis joukkoon $\{1,2,\ldots,2\cdot n-1,2\cdot n\}$ ja tässä joukossa on $n$ paritonta lukua $1,3,5,\ldots, 2\cdot n-1$ .
Lokeroperiaatteen nojalla on olemassa luvut $i\neq j$ siten, että $q_i=q_j$ jolloin $k_i\neq k_j$ koska $[k_i,q_i]\neq [k_j,q_j]$ .
Voimme valita $a=2^{k_i}\cdot q_i$ ja $b=2^{k_j}\cdot q_j$ jolloin väite pätee koska joko $k_i< k_j$ jolloin $b=a\cdot 2^{k_j-k_i}$ tai $k_j< k_i$ jolloin $a=b\cdot 2^{k_i-k_j}$ .

Kertoma $n!$ [+]

Jos

$n$ on positiivinen kokonaisluku niin

$\begin{equation*} n!= 1\cdot 2\cdot \ldots \cdot (n-1)\cdot n. \end{equation*}$ Lisäksi

$0!=1$ .

Binomikerroin $\binom nk$ [+]

Jos

$n$ ja

$k$ ovat kokonaislukuja siten, että

$0\leq k \leq n$ niin

$\begin{equation*} \binom nk= \frac {n!}{k!\, (n-k)!} \end{equation*}$ jolloin

$\binom nk= \binom n{n-k}$ .

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	$\dfrac {n!}{(n-k)!}$	$\displaystyle n^k$
Järjestämätön	$\dbinom {n}{k}$	$\dbinom {k+n-1}{n-1}$

Järjestetty otos palauttamatta [-]

Jos valitaan

$k$ alkiota joukosta

$A$ , jossa on

$n$ alkiota, eli

$\card{A}=n$ ja muodostetaan niistä jono

$[x_1,x_2,\ldots,x_k]$ ja tehdään tämä palauttamatta, eli samaa alkiota ei valita monta kertaa jolloin

$x_i\neq x_j$ kun

$i\neq j$ niin saadaan ns.

$k$ -permutaatio. Näiden jonojen eli

$k$ -permutaatioiden lukumäärä on tuloperiaatteen nojalla

$\begin{equation*} n\cdot (n-1)\cdot \ldots \cdot (n-k+1)= \frac {n!}{(n-k)!} \end{equation*}$

Järjestetty otos palauttaen [-]

Jos valitaan

$k$ alkiota joukosta

$A$ , jossa on

$n$ alkiota, eli

$\card{A}=n$ ja muodostetaan niistä jono

$[x_1,x_2,\ldots,x_k]$ ja tehdään tämä palauttaen, eli sama alkio voidaan valita monta kertaa jonossa jolloin ainoa vaatimus on, että

$x_j\in A$ kun

$1\leq j\leq k$ niin tuloperiaatteen nojalla näiden jonojen lukumäärä on

$\begin{equation*} \card{A}^k= n^k. \end{equation*}$

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

Jos joukosta, jossa on

$n$ alkiota, valitaan osajoukko johon kuuluu

$k$ alkiota, eli valitaan

$k$ alkiota palauttamatta, (jokaista alkiota voidaan valita korkeintaan kerran), eikä valintajärjestyksellä ole merkitystä niin vaihtoehtojen lukumäärä on

$\begin{equation*} \binom {n}{k}=\binom{n}{n-k}. \end{equation*}$ Miksi? [+]

Jos kyseinen lukumäärä on

$b(n,k)$ niin palauttamatta otettujen järjestettyjen otosten lukumäärä on

$b(n,k)\cdot k!$ koska

$k$ alkiota voidaan järjestää jonoksi

$k!$ eri tavalla. Näin ollen

$b(n,k)\cdot k! = \frac {n!}{(n-k)!}$ joten

$b(n,k)=\binom nk$ .

Järjestämätön otos palauttaen [-]

Jos joukosta, jossa on

$n$ alkiota, valitaan

$k$ alkiota palauttaen, eli sama alkio voidaan valita monta kertaa, eikä valintajärjestyksellä ole merkitystä, niin vaihtoehtojen lukumäärä on

$\begin{equation*} \binom {k+n-1}{n-1}=\binom{k+n-1}{k}. \end{equation*}$ Miksi? [+]

Olkoon esimerkiksi $n=6$ ja $A=\{x_1,x_2,\ldots,x_6\}$ . Kun valitsemme esimerkiksi $k=11$ kertaa alkion joukosta $A$ eikä valintajärjestyksellä ole merkitystä niin tulos voi olla esimerkiksi seuraava: $\begin{equation*} x_1\; x_1\; x_2\; x_4\; x_4\; x_4\; x_5\; x_5\; x_6\; x_6\; x_6 \end{equation*}$ Sen sijaan, että kirjoitamme auki alaindeksit niin voimme käyttää erotusmerkkiä $|$ osoittamaan missä kohdissa indeksi muuttuu jolloin lista näyttää seuraavanlaiselta: $x\; x\; |\; x\; |\;| \; x\;x\;x\;|\: x\;x\;|\; x\;x\;x$ ja $|\;|$ tarkoittaa, ettemme ole valinneet alkiota $x_3$ 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=\{x_1,x_2,\ldots,x_n\}$ 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 $\binom {k+n-1}{n-1}=\binom{k+n-1}{k}$ .

Allokointimalli eli vaihtoehtoinen ajattelutapa [-]

On sijoitettava

$k$ palloa

$n$ :ään numeroituun laatikkoon.

Numeroidut pallot $\leftrightarrow$ Järjestetty otos
Identtiset pallot $\leftrightarrow$ Järjestämätön otos
Jokaiseen laatikkoon korkeintaan yksi pallo $\leftrightarrow$ Otos palauttamatta
Jokaiseen laatikkoon mielivaltainen määrä palloja $\leftrightarrow$ Otos palauttaen

	Pallojen lukumäärä laatikoissa
	korkeintaan $1$	ei rajoituksia
Numeroidut pallot	$\dfrac {n!}{(n-k)!}$	$\displaystyle n^k$
Identtiset pallot	$\dbinom {n}{k}$	$\dbinom {k+n-1}{n-1}$

Esimerkki [+]

Tentissä valvojat jakavat

$150$ tehtäväpaperia

$160$ :lle tenttijälle. Monellako tavalla tämä on mahdollista? Vastaus [+]

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 $\displaystyle \binom {160}{150}=\binom{160}{10}$ .

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 $\displaystyle \binom {150+ 160-1}{160-1} = \frac {309!}{159!\cdot 150!}$ .

Esimerkki [+]

Monellako tavalla voimme järjestää luvut

$1$ ,

$2$ ,

$3$ ,

$4$ ,

$5$ ,

$6$ ,

$7$ ,

$8$ ,

$9$ ja

$10$ jos vaaditaan, ettei kahden parillisen luvun välissä ole yhtään paritonta lukua? Vastaus [+]

$5$ parillista lukua ja

$5$ paritonta. Parillisten lukujen jonon voimme sijoittaa parittomien lukujen sekaan siten, että parillisten lukujen jälkeen tulee

$j$ paritonta lukua missä

$j=0,1,\ldots,5$ (jolloin muut parittomat luvut tulevat jonossa ensimmäisinä). Tämä antaa

$6$ eri vaihtoehtoa. Parilliset luvut voimme asettaa järjestykseen

$5!$ :lla eri tavalla ja samoin parittomat luvut voimme asettaa järjestykseen

$5!$ :lla eri tavalla. Näin ollen vaihtoehtojen lukumääräksi tulee

$5!\cdot 5! \cdot 6=86400.$

Esimerkki [+]

Monellako tavalla voimme järjestää luvut

$1$ ,

$2$ ,

$3$ ,

$4$ ,

$5$ ,

$6$ ,

$7$ ,

$8$ ja

$9$ jos vaaditaan, että kahden parillisen luvun välissä on ainakin yksi pariton luku? Vastaus [+]

Kahden parillisen luvun välissä on oltava ainakin yksi pariton luku ja siihen tarvitaan

$3$ paritonta lukua koska parillisia lukuja on

$4$ . Nyt on

$5$ paikkaa minne voimme sijoittaa jäljellä olevat parittomat luvut, eli ensimmäiseksi, viimeiseksi tai kahden parillisen luvun väliin. Koska meillä on kaksi paritonta lukua, jotka on sijoitettava näihin viiteen paikkaan niin kyse on kahden alkion järjestämättömästä otoksesta palauttaen palauttaen joukosta, jossa on

$5$ alkiota. Näin ollen vaihtoehtojen lukumäärä on

$\dbinom{2+5-1}{2}=15$ . Koska voimme asettaa parilliset luvut järjestykseen

$4!$ :lla eri tavalla ja voimme asettaa parittomat luvut järjestykseen

$5!$ :lla eri tavalla niin kaiken kaikkian vaihtoehtojen lukumääräksi tulee

$15\cdot 4!\cdot 5!=43200.$

Multinomikerroin [+]

Jos

$n_j\geq 0$ kun

$j=1,2,\ldots,m$ ja

$n=n_1+n_2+ \ldots n_m$ niin

$\binom{n}{n_1,n_2,\ldots, n_m} = \frac{n!}{n_1!\cdot n_2!\cdot \ldots \cdot n_m!}.$

$\dbinom {n}{n_1,n_2,\ldots,n_m}$ on vaihtoehtojen lukumäärä kun joukko $A$ jaetaan osajoukoiksi $A_j$ , $j=1,\ldots,m$ siten, että $\cup_{j=1}^m A_j=A$ , $A_i\cap A_j=\emptyset$ kun $i\neq j$ , ja $\card{A_j}=n_j$ .
$\dbinom{n}{n_1,n_2,\ldots, n_m}$ on vaihtoehtojen lukumäärärä kun järjestetään $n_1$ oliota tyyppiä $y_1$ , $n_2$ tyyppiä $y_2$ jne. missä $n=n_1+n_2+\ldots +n_m$ ja samaa tyyppiä olevat oliot ovat identtiset.
Jos $A$ on joukko, jossa on $n$ alkiota ja $B=\{y_1,\ldots ,y_m\}$ on joukko, jossa on $m$ alkiota ja $n_1, n_2,\ldots,n_m$ ovat ei-negatiivisia lukuja siten, että $n_1+n_2+\ldots n_m=n$ niin $\dbinom{n}{n_1,n_2,\ldots, n_m}$ on niiden funktioiden $f:A\to B$ lukumäärä joille pätee $\card{\set{x\in A\mid f(x)=y_j}}=n_j$ .

Esimerkki [+]

Kurssiin osallistuu

$15$ opiskelija ja heille annetaan

$4$ eri ongelmaa tutkittaviksi jolloin he muodostavat

$4$ ryhmää joissa on

$5$ ,

$4$ ,

$3$ ja

$3$ opiskelijaa. Monellako tavalla tämä jako ryhmiin voidaan suorittaa? Vastaus [+]

Tässä siis on kyse siitä että joukko jaetaan neljään (numeroituun) joukkoon jolloin vastaus saadaan suoraan multinomikertoimen avulla eli se on

$\binom {15}{5,4,3,3}=12\,612\,600.$ Jos sen sijaan kaikille ryhmille annetaan sama tehtävä niin silloin ei ole mitään väliä mihin kolmen hengen ryhmään opiskelija tulee valituksi jolloin vaihtoehtojen lukumäärä onkin

$\frac 12\binom {15}{5,4,3,3}$ .

Binomi- ja multinomikaavat [+]

$(x+y)^n = \sum_{j=0}^n \binom nj x^jy^{n-j}$ ja $(x_1+\ldots +x_m)^n = \sum_{\substack{n_1+\ldots+n_m=n\\ n_j\geq 0}} \binom{n}{n_1,n_2,\ldots, n_m} x_1^{n_1}\cdot \ldots \cdot x_m^{n_m}.$

Miksi? [+]

Binomikaava on erikoistapaus multinomikaavasta koska

$\binom nj= \binom n{j,n-j}$ ja multinomikaava pätee koska

$(x_1+\ldots +x_m)^n$ voidaan kirjoittaa summana jossa on

$m^n$ termiä jotka ovat tyyppiä

$y_1\cdot y_2\cdot \ldots\cdot y_n$ missä jokainen

$y_i\in \{x_1,x_2,\ldots,x_m\}$ . Jokainen muotoa

$x_1^{n_1}\cdot \ldots \cdot x_m^{n_m}$ termi syntyy siitä, että joukko

$\{1,\ldots,n\}$ jaetaan osajoukkoihin

$A_j$ ,

$j=1,\ldots, m$ siten että

$i\in A_j$ jos ja vain jos

$y_i=x_j$ jolloin siis

$\card{A_j}= n_j$ . Tällaisia osituksia on täsmälleen

$\binom{n}{n_1,n_2,\ldots, n_m}$ kappaletta.

Funktioiden lukumäärä [+]

Olkoot

$A$ ja

$B$ kaksi joukkoa,

$\card{A}=m$ ja

$\card{B}=n$ .

Funktioden $A\to B$ lukumäärä on $\card {B^A}=\card{B}^{\card{A}}=n^m$ . Miksi? [+]
Funktio $f:A\to B$ on järjestetty $m$ -kokoinen otos palauttaen joukosta, jossa on $n$ alkiota.
Injektioiden $A\to B$ lukumäärä on $\displaystyle n\cdot (n-1)\cdot \ldots \cdot (n-m+1)=\frac {n!}{(n-m)!}$ kun $m\leq n$ ja $0$ kun $m>n$ . Miksi? [+]
Injektio $A\to B$ on järjestetty $m$ -kokoinen otos palauttamatta joukosta, jossa on $n$ alkiota.
Surjektioiden $A\to B$ lukumäärä on $\displaystyle \sum_{k=0}^n \binom nk(-1)^{n-k} k^m$ . Miksi? [+]
Olkoon $B=\{b_1,b_2,\ldots,b_n\}$ , $F=B^A$ kaikkien funktioiden $A\to B$ joukko ja $F_j=(B\setminus\{b_j\})^A\subset F$ kaikkien funktioiden $A:\to B\setminus\{b_j\}$ joukko eli niiden $F$ :n alkioiden $f$ joukko joille pätee, että $f(x)\neq b_j$ kaikilla $x\in A$ . Surjektioiden joukko on siten $F\setminus \cup_{j=1}^n F_j$ .
Nyt $F_{j_1}\cap F_{j_2}\cap \ldots \cap F_{j_r}$ on joukko $(B\setminus\{b_{j_1},b_{j_2},\ldots b_{j_r}\})^A$ johon kuuluvat kaikki funktiot $A\to B$ jotka eivät saa arvoja $b_{j_1},\ldots,b_{j_r}$ . Jos $1\leq j_1 < \ldots < j_r\leq n$ niin $\card{F_{j_1}\cap F_{j_2}\cap \ldots \cap F_{j_r}} = (n-r)^m$ . Koska on $\binom nr$ eri tapaa valita indeksit $1\leq j_1<\ldots < j_r\leq n$ niin seulaperiaatteesta seuraa, että surjektioiden $A\to B$ lukumäärä on $n^m - \biggl( \sum_{r=1}^n (-1)^{r+1}\binom nr (n-r)^m\biggr) \\= \sum_{r=0}^n (-1)^r \binom nr (n-r)^m\\ \mathrel {\buildrel {\small n-r=k}\over{=}\;\; } \sum_{k=0}^n \binom nk (-1)^{n-k} k^m.$ Huomaa, että kun $m< n$ ei ole surjektioita $A\to B$ joten silloin $\sum_{k=0}^n \binom nk (-1)^{n-k} k^m=0$ , mikä ehkä ei ole aivan ilmeistä.

Sekalaisia esimerkkejä [+]

Korttiesimerkki [+]

Montako erilaista sellaista viiden pelikortin riviä (normaalista 52 kortin pakasta) on olemassa, jossa esiintyy täsmälleen kaksi kuningatarta? Ratkaisu [+]

Valitsemme ensin ne kaksi paikkaa, joihin kuningattaret tulevat. Vaihtoehtoja on $\dbinom 52 = 10$ .
Sitten valitsemme kuningattaret näihin paikkoihin ja nyt vaihtoehtojen lukumäärä on $4\cdot 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\cdot 47\cdot 46=103776$
Tuloperiaatteen nojalla erilaisten rivien lukumääräksi tulee $10\cdot 12 \cdot 103\,776=12\,453\,120.$

Osajoukkojen lukumäärä: $\card{\mathcal P(A)}=2^{\card{A}}$ [+]

Jos joukossa

$A$ on

$m$ alkiota niin joukossa

$\mathcal P(A)$ on

$2^m$ alkiota, eli

$A$ :n osajoukkojen lukumäärä on

$2^{\card{A}}$ koska jokaista osajoukkoa

$B$ vastaa funktio

$f_B:A\to \{0,1\}$ siten, että

$f_B(x)=1$ jos

$x\in B$ ja muuten

$0$ .

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 $n\log_2(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(n\log(\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 $2^m$ eri vastausta.
Jos järjestysalgoritmi toimii niin $2^m\geq n!$ eli $m\geq \log_2(n!)$ . Koska kun $n\geq 3^3$ joten oleellisesti parempi tulos kuin $n\log_2(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)$ .
$\displaystyle S(n,k)=\frac 1{k!}\sum_{j=0}^k \binom kj (-1)^{k-j} j^n$ . Miksi? [+]
Voimme numeroida $k$ osajoukkoa $k!$ eri tavalla ja jako ei-tyhjiin numeroituihin osajoukkoihin määrittelee funktion $f$ alkuperäisestä joukosta joukkoon $\{1,2,\ldots,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ä $\textrm{Sur}(n,k)= k!S(n,k)$ missä $\textrm{Sur}(n,k)$ on surjektioiden lukumäärä joukosta, jossa on $n$ alkiota joukkoon, jossa on $k$ alkiota. $\textrm{Sur}$ -funktiolle johdetun kaavan avulla saamme väiteen.
$S(n,2)= 2^{n-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 $2^{n-1}$ mutta yksi ei kelpaa koska joukkojen pitää olla ei-tyhjiä joten $S(n,2)= 2^{n-1}-1$ .
$\displaystyle S(n,n-1)= \frac 1{(n-1)!}\sum_{j=0}^{n-1}\binom {n-1}j(-1)^{k-j}j^n=\binom 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 $\binom n2$ :lla eri tavalla.

Viimeksi muokattu: G. Gripenberg, 2017-09-13

Lukumääriä ja kombinatoriikkaa

Joukon mahtavuus eli kardinaliteetti [-]

Esimerkki: |Z|=|N0|\card{\Z}=\card{\N_0} [+]

Esimerkki: |Q|=|Z|\card{\Q}= \card{\Z} [+]

Summaperiaate [-]

Pari epäyhtälöä [+]

Tuloperiaate [-]

Esimerkki [+]

Lokero- eli kyyhkyslakkaperiaate [+]

Esimerkki [+]

Kertoma n!n! [+]

Binomikerroin (nk)\binom nk[+]

Otokset: Järjestetty - järjestämätön, palauttamatta - palauttaen [+]

Yhteenveto [-]

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 [-]

Allokointimalli eli vaihtoehtoinen ajattelutapa [-]

Esimerkki [+]

Esimerkki [+]

Esimerkki [+]

Multinomikerroin [+]

Esimerkki [+]

Binomi- ja multinomikaavat [+]

Funktioiden lukumäärä [+]

Sekalaisia esimerkkejä [+]

Korttiesimerkki [+]

Osajoukkojen lukumäärä: |P(A)|=2|A|\card{\mathcal P(A)}=2^{\card{A}} [+]

Montako vertailua tarvitaan järjestämisalgoritmissa? [+]

Esimerkki: Monellako tavalla voidaan jakaa joukko, johon kuuluu nn alkiota, kk:hon ei-tyhjään osajoukkoon? [+]

Esimerkki: $\card{\Z}=\card{\N_0}$ [+]

Esimerkki: $\card{\Q}= \card{\Z}$ [+]

Kertoma $n!$ [+]

Binomikerroin $\binom nk$ [+]

Osajoukkojen lukumäärä: $\card{\mathcal P(A)}=2^{\card{A}}$ [+]

Esimerkki: Monellako tavalla voidaan jakaa joukko, johon kuuluu $n$ alkiota, $k$ :hon ei-tyhjään osajoukkoon? [+]