Kombinatoorika
Enne alustamist10. klass · raskus 4/5
Mõiste
Kombinatoorika aitab lugeda valikuid, järjekordi ja koode.
Eeldus: oskad korrutada naturaalarve ning lugeda tõenäosuses soodsaid ja kõiki võimalusi.
Enne arvutust sõnasta, millal kaks tulemust loetakse samaks ja millal erinevaks.
Põhireeglid
Kolme erineva raamatu A, B ja C kõik järjestused on ABC, ACB, BAC, BCA, CAB, CBA. Esimesele kohale on 3, teisele 2 ja viimasele 1 valikut: $3\cdot2\cdot1=6$. Need on permutatsioonid.
Kui üks valik on võimalik $m$ viisil ja teine $n$ viisil, siis järjestikuseid valikuid on
$$m\cdot n.$$
See on korrutamisreegel.
Enne valemi valimist küsi:
| Küsimus | Kui vastus on jah | Tüüpiline valem |
|---|---|---|
| Kas valikud tehakse järjest? | kasuta korrutamisreeglit | $m\cdot n\cdot\ldots$ |
| Kas järjestatakse kõik $n$ objekti? | permutatsioon | $n!$ |
| Kas valitakse $k$ objekti ja järjekord loeb? | variatsioon | $\frac{n!}{(n-k)!}$ |
| Kas valitakse $k$ objekti ja järjekord ei loe? | kombinatsioon | $\binom nk$ |
Kui valitud objektidel on erinevad rollid või kohad, siis järjekord loeb. Kui moodustub samaväärsete liikmetega rühm, siis järjekord ei loe.
Vastandnäited:
| Olukord | Kas järjekord loeb? | Põhjus |
|---|---|---|
| Valitakse 2-liikmeline võistkond | ei | Mari-Jüri ja Jüri-Mari on sama võistkond |
| Valitakse kapten ja abikapten | jah | rollid on erinevad |
| Moodustatakse 3-kohaline kood | jah | 123 ja 321 on eri koodid |
| Valitakse 3 raamatut suveks | ei | valik on sama, isegi kui nimetad raamatuid teises järjekorras |
Permutatsioonide arv:
$$n!=1\cdot2\cdot3\cdots n.$$
Variatsioonide arv, kui valitakse $n$ erinevast objektist $k$ objekti ilma kordusteta ja järjekord loeb ($0\le k\le n$, mõlemad täisarvud):
$$V_n^k=\frac{n!}{(n-k)!}.$$
Kombinatsioonide arv samadel tingimustel, kui järjekord ei loe:
$$\binom nk=\frac{n!}{k!(n-k)!}.$$
Näide
Viie erineva raamatu A, B, C, D ja E seast kahe valimisel on järjekorraga $5\cdot4=20$ võimalust. Järjekorrata on AB ja BA sama paar. Iga paari loeti kaks korda, seega $20/2=10$.
Kõik järjekorrata paarid: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE.
Kui valida 5 õpilase seast 2 esindajat, siis võimalusi on
$$\binom52=\frac{5!}{2!3!}=10.$$
Kui samast 5 õpilasest valitakse president ja asepresident, siis järjekord loeb:
$$V_5^2=5\cdot4=20.$$
Kui 4 inimest pannakse järjekorda, siis võimalusi on
$$4!=24.$$
Kui menüüs on 3 jooki ja 4 magustoitu, siis ühe joogi ja ühe magustoidu valikuid on
$$3\cdot4=12.$$
Sama 5 õpilase näide näitab, miks küsimus loeb:
- 2 esindajat: $\binom52=10$;
- esimees ja aseesimees: $5\cdot4=20$;
- kõik 5 õpilast järjekorras: $5!=120$.
Kaks täringut: 36 paari, 21 paaritüüpi või 11 summat?
Esimese ja teise täringu tulemused moodustavad järjestatud paari: $(1;2)$ ja $(2;1)$ on erinevad. Kui võtta esimene tulemus $x$- ja teine $y$-koordinaadiks, saame 36 erinevat punkti.
Järjekorrata on 6 võrdsete arvudega paari ning $30/2=15$ erinevate arvudega paari: kokku 21 paaritüüpi. Summasid on 11, arvud 2 kuni 12. Summa 7 tuleb kuuel viisil, summa 2 ühel.
Sõltumatute ausate täringute 36 järjestatud paari on võrdvõimalikud. Paaritüübid ja summad ei ole: $(1;2)$ või $(2;1)$ tõenäosus on kokku $2/36$, aga $(1;1)$ tõenäosus $1/36$.
Võimalikud eksimused
Kui järjekord ei loe, ära kasuta permutatsioone. Paar Mari ja Jüri on sama paar mis Jüri ja Mari.
Kui rollid on erinevad, siis järjekord loeb. Paar "president Mari, asepresident Jüri" ei ole sama mis "president Jüri, asepresident Mari".
Teine tüüpviga on korduste lubamist märkamata jätta. Koodis võivad kordused olla lubatud või keelatud:
- kui kordused on lubatud, siis 3-kohalise koodi jaoks numbritest 1, 2, 3 on $3\cdot3\cdot3=27$ võimalust;
- kui kordused ei ole lubatud, siis võimalusi on $3\cdot2\cdot1=6$.
Kolmas tüüpviga on kasutada kombinatsiooni siis, kui kohtadel on tähendus. Kui auhinnad on kuld, hõbe ja pronks, siis järjekord loeb.
Harjutused
Prindi selle teema harjutusleht
Lihtne kontroll
- Mitu kolmekohalist koodi saab moodustada numbritest 1, 2, 3, kui kordused on lubatud?
- Mitu viisi on 4 inimest järjekorda panna?
- Kui mitmel viisil saab valida 6 õpilase seast 3?
- Kui mitmel viisil saab valida 6 õpilase seast esimehe ja aseesimehe?
Rakendus
- Kohvikus on 5 võileiba ja 3 jooki. Mitu viisi on valida üks võileib ja üks jook?
- Mitu kolmekohalist koodi saab moodustada numbritest 1, 2, 3, kui kordused ei ole lubatud?
- Klassis on 8 õpilast. Kui mitmel viisil saab valida 2-liikmelise tööpaari?
Mõtlemisülesanne
- Samast 8 õpilasest valitakse esineja ja ajamõõtja. Mitu võimalust on?
- Kui mitmel viisil saab 5 raamatut riiulisse järjekorda panna?
- Otsusta, kas järjekord loeb: valitakse 3 õpilast ekskursiooni korraldustiimi. Põhjenda.
- Numbrid 1, 2, 3 pannakse juhuslikku järjekorda. Kui suur on tõenäosus, et esimene number on 1?
Vastused
- $3\cdot3\cdot3=27$.
- $4!=24$.
- $\binom63=20$, sest 3-liikmelises rühmas järjekord ei loe.
- $6\cdot5=30$, sest esimese koha jaoks on 6 ja teise jaoks 5 valikut.
- $5\cdot3=15$.
- $3\cdot2\cdot1=6$.
- $\binom82=28$, sest tööpaaris rollid ei erine.
- $8\cdot7=56$, sest esineja ja ajamõõtja on eri rollid.
- $5!=120$.
- Ei loe, kui kõigil kolmel on sama roll korraldustiimis; siis kasutatakse kombinatsiooni.
- Kõiki järjekordi on $3!=6$; soodsaid on 2: 123 ja 132. Tõenäosus on $\frac26=\frac13$.
Seosed
Kombinatoorika aitab tõenäosuses nimetajat ja lugejat leida. Järgmistes andmete peatükkides nihkub rõhk loendamiselt hajuvusele, jaotustele ning Bernoulli mudelile.