Kombinatoorika Matemaatika kiirreferents

Kombinatoorika

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

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 $k$ objekti $n$ objektist ja järjekord loeb:

$$V_n^k=\frac{n!}{(n-k)!}.$$

Kombinatsioonide arv:

$$\binom nk=\frac{n!}{k!(n-k)!}.$$

Näide

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:

Vastus: võimalusi on vastavalt 10, 20, 24, 12 ja 120.

Tüüpviga

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:

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

Lihtne kontroll

  1. Mitu kolmekohalist koodi saab moodustada numbritest 1, 2, 3, kui kordused on lubatud?
  2. Mitu viisi on 4 inimest järjekorda panna?
  3. Mitu viisi saab valida 6 õpilase seast 3?
  4. Mitu viisi saab valida 6 õpilase seast esimehe ja aseesimehe?

Rakendus

  1. Kohvikus on 5 võileiba ja 3 jooki. Mitu viisi on valida üks võileib ja üks jook?
  2. Mitu kolmekohalist koodi saab moodustada numbritest 1, 2, 3, kui kordused ei ole lubatud?
  3. Klassis on 8 õpilast. Mitu viisi saab valida 2-liikmelise tööpaari?

Mõtlemisülesanne

  1. Samast 8 õpilasest valitakse esineja ja ajamõõtja. Mitu võimalust on?
  2. Mitu viisi saab 5 raamatut riiulisse järjekorda panna?
  3. Otsusta, kas järjekord loeb: valitakse 3 õpilast ekskursiooni korraldustiimi. Põhjenda.
  4. Numbrid 1, 2, 3 pannakse juhuslikku järjekorda. Kui suur on tõenäosus, et esimene number on 1?

Vastused

  1. $3\cdot3\cdot3=27$.
  2. $4!=24$.
  3. $\binom63=20$, sest 3-liikmelises rühmas järjekord ei loe.
  4. $6\cdot5=30$, sest esimese koha jaoks on 6 ja teise jaoks 5 valikut.
  5. $5\cdot3=15$.
  6. $3\cdot2\cdot1=6$.
  7. $\binom82=28$, sest tööpaaris rollid ei erine.
  8. $8\cdot7=56$, sest esineja ja ajamõõtja on eri rollid.
  9. $5!=120$.
  10. Ei loe, kui kõigil kolmel on sama roll korraldustiimis; siis kasutatakse kombinatsiooni.
  11. 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 liigub fookus loendamiselt hajuvusele, jaotustele ning Bernoulli mudelile.