Chapter 1.1 (Matem 11. kl)

Kombinatoorika

Põhi­koolis oleme õppinud, et

sündmuse A toimumise tõenäosuseks P(A) nimetatakse selle sündmuse jaoks soodsate võimaluste arvu k ja kõigi võimaluste arvu n suhet, P\left(A\right)=\frac{k}{n}.

Näide 1.

Lapsel on 5 paberi­lehte, millest igal on üks numbritest 0, 1, 2, 3, 4. Ta paneb neist juhuslikult võetud kolm kõrvuti. Kui suur on tõenäosus, et nii saadi kolme­kohaline arv?

Lahendamiseks tuleb leida kõigi võimaluste arv n ja soodsate võimaluste arv k.

Kuidas suurusi n ja k võimalikult lihtsalt leida, selgub, kui tutvuda mõningate mõistete ja lausetega matemaatika osast, mida nimetatakse kombinatoorikaks. Üldiselt uurib kombinatoorika, kuidas antud elementidest moodustada teatud tingimusi täitvaid hulki (nimetatakse ka ühenditeks) ja kuidas leida selliste hulkade (ühendite) võimalikku arvu.

Järgnevalt vaatlemegi mõningaid kombinatoorika mõisteid ja lauseid.

Kui lapsele on antud võimalus valida 3 erineva auto ja 2 erineva nuku seast üks mängu­asi, siis pole kahtlust, et erinevaid valiku­võimalusi on 3 + 2 = 5. Kombinatoorikas sõnastatakse vastav reegel nn liitmis­lausena:

kui objekti A valikuks on n erinevat võimalust ja objekti B valikuks m erinevat võimalust ning valida tuleb kas objekt A või objekt B, siis kõigi erinevate valiku­võimaluste arv on n + m.

Toodud näite korral on objektiks A auto, objektiks B nukk ning n = 3 ja m = 2.

Teatud valikute arvu leidmiseks kasutatakse nn korrutamis­lauset:

kui objekti A valikuks on n erinevat võimalust ja objekti B valikuks m erinevat võimalust ning valida tuleb nii objekt A kui ka objekt B, siis kõigi erinevate valiku­võimaluste arv on n · m.

Kui näiteks laps võib võtta 3 erineva auto seast ühe ja 2 erineva nuku seast ühe, on erinevaid võimalusi nii auto kui ka nuku võtmiseks 3 · 2 = 6.

Veendume selles üld­juhul. Objekti A iga valikuga kaasneb m võimalust objekti B valikuks. Et objekti A saab valida n erineval viisil, siis on nii A kui ka B valiku­võimaluste kogu­arv n korda suurem kui ühe objekti A korral, seega n · m.

Kombinatoorika liitmis- ja korrutamis­lauset on võimalik üldistada kolme ja enama objekti juhule, lugedes eelnevalt näiteks kaks objekti juba valituks.

Näide 1​. (järg)

Lahendame näites 1 esitatud ülesande.

Lahendus. Leiame kolme­kohalise arvu tekkeks soodsate võimaluste arvu k. Kolme­kohalise arvu esimese numbri valikuks on 4 võimalust, sest arv ei saa alata nulliga. Kui esimene number on valitud, on teise numbri valikuks 4 võimalust. Kui kaks esimest numbrit on valitud, jääb kolmanda numbri valikuks 3 võimalust. Et valik toimub põhi­mõttel nii esimene kui ka teine kui ka kolmas number, siis korrutamis­lause põhjal k = 4 · 4 · 3 = 48.

Kõiki erinevaid võimalusi viiest numbrist kolme kõrvuti asetamiseks on aga analoogilise mõtte­käigu põhjal n = 5 · 4 · 3 = 60. Järelikult vastav tõenäosus p = k : n = 48 : 60 = 0,8.

Liitmis- ja korrutamis­lauset aitab eristada valiku­viisi iseloomustav väljend. Liitmis­lause korral on see kas A või B (lühemalt A või B), korrutamis­lause korral nii A kui ka B (lühemalt A ja B).

Näide 2.

Leiame, mitu autot oleks saanud Eestis registreerida, kui numbri­märgis võinuks olla kas neli numbrit või neli suur­tähte, kaasa arvatud võõr­tähed, aga välja arvatud Õ, Ä, Ö, Ü, Š, Ž.

Lahendus. Korrutamis­lause järgi oleks saanud numbritega eristada 10 ⋅ 10 ⋅ 10 ⋅ 10 = 104 autot. Analoogiliselt ainult suur­tähtedega 264 autot. Et kasutada võis kas ainult numbreid või ainult suur­tähti, siis liitmis­lause põhjal on vastuseks 104 + 264 = 466 976.

Näide 3.

Lapse käes on neli kaarti tähtedega AEKR. Leiame, mitmel viisil saab ta neid järjestada (mitu nelja­tähelist „sõna” saab ta neist moodustada) ja millised need järjestused on.

Esimest tähte saab ta valida 4 erineval viisil, teist kolmel, kolmandat kahel ja neljandat ühel viisil. Korrutamis­lause põhjal on erinevate „sõnade” arv 4 · 3 · 2 · 1 = 24. Need on:

A E K R

A E R K

A K E R

A K R E

A R E K

A R K E

E A K R

E A R K

E K A R

E K R A

E R A K

E R K A

K A E R

K A R E

K E R A

K E A R

K R A E

K R E A

R A E K

R A K E

R E K A

R E A K

R K E A

R K A E

Kombinatoorika seisukohalt oleme näites 3 saanud teatud liiki hulgad (ühendid), mida nimetatakse permutatsioonideks neljast elemendist. Üldiselt:

permutatsioonideks n erinevast elemendist nimetatakse nende elementide kõik­võimalikke erinevaid järjestusi.

Permutatsioonide arv n elemendist, mida tähistatakse sümboliga Pn, on korrutamis­lause põhjal n · (n – 1) · (n – 2) · … · 3 · 2 · 1.

Et kõigi naturaal­arvude korrutist arvust 1 kuni arvuni n nimetatakse arvu n faktoriaaliks ja tähistatakse sümboliga n!, siis

Pnn · (n – 1) · (n – 2) · … · 3· 2 · 1 = n!

Näiteks 4! = 4 · 3 · 2 · 1 = 24.

Kui soovime, et valem Pn = n! annaks ka permutatsioonide arvu ühest elemendist, mis on loomulikult 1, siis peame defineerima, et

1! = 1.

Nüüd P1 = 1! = 1.

Tasku­arvutitel saab reeglina leida arvu faktoriaali. Selleks on klahv !, x! või n!.

Näide 4.

Leiame tasku­arvutil \frac{50!\cdot40!\cdot5!}{28!\cdot60!\cdot8!}.

  Tasku­arvutil reeglina ei saa leida antud avaldise väärtust nii, et esmalt leitakse lugeja väärtus. Juba korrutise 50! · 40! arvutamisel annab arvuti vea­teate, sest tulemus ei mahu mällu. Seda on võimalik vältida, kui teha tehteid selles järje­korras, et vahe­tulemusi saab talletada. Nii sobib näiteks arvutus­skeem 

50 !: 60 !· 40 !: 28 !· 5 !: 8 !=

ja tulemuseks on 0,0291115274.

Näide 5.

Leiame, mitu nelja­tähelist „sõna“ saab moodustada tähtedest A, A, L, S. Mõnel neist on tähendus.

ite 3 ees­kujul vastust leida ei saa, sest korduvate tähtede oma­vahelisel vahetamisel ei muutu „sõna“ pildis midagi.

On aga võimalus kirjutada kõik need „sõnad“ välja ja siis loendada need. Et see­juures vältida võimalikke eksimusi, on ots­tarbekas teha seda nn diagrammi „puu“ abil, mis on joonisel 1.1.

Joon. 1.1

Ülesanded A

Ülesanne 1. Puu­viljade võtmine
  1. kas üks õun või üks ploom või üks pirn?

    Vastus. Sel juhul on võimalik puu­vilju võtta  erineval viisil.
  2. nii üks õun kui ka üks ploom kui ka üks pirn?

    Vastus. Sel juhul on võimalik puu­vilju võtta  erineval viisil.
Ülesanne 2. Kahe­täheliste sõnade moodustamine
  1. korduvaid tähti sõnas ei kasutata?
    Vastus. Siis saaks moodustada  erinevat sõna.
  2. võib kasutada sõnas ka korduvaid tähti?
    Vastus. Siis saaks moodustada  erinevat sõna.
  3. sõnas on üks täis­häälik ja üks kaas­häälik?
    Vastus. Siis saaks moodustada  erinevat sõna.

Ülesanne 3. Üks­teise kõrval istumine

Vastus. 5 inimest saavad teatris kõrvuti istuda  erineval viisil.

Ülesanne 4. Kolme­käiguline lõuna

Vastus. Valida on võimalik  erinevat kolme­käigulist lõunat.

Ülesanne 5. Tee­kond linnast A külla D

Vastus. Linnast A külla D sõiduks on  erinevat teed.

Ülesanne 6. Rahvus­vaheline esindus

Vastus. Seda saab teha  erineval viisil.

Ülesanne 7. Auto numbri­märk

Vastus. Sellise süsteemi korral saab registreerida  autot.

Ülesanne 8. Ühe-, kolme-, viie- ja seitsme­kohalised arvud

Vastus. Kokku saab moodustada  sellist arvu.

Ülesanne 9. Permutatsioonid tähtedest A, O, S

Vastus. Tähendus on neist .

Ülesanne 10. Ühe oktaavi noodid

Vastus. Ühe oktaavi 12 nooti saab läbi mängida  erineval viisil.

Ülesanne 11. Permutatsioonid elementidest A, E, K, S

Vastus. Tähendus on neist .

Ülesanne 12. Kolme­sõnalised laused sõnadest keegi, on, siin

Ülesanne 13. Bussi sisenemine

Vastus. Kümme turisti saavad bussi siseneda  erinevas järje­korras. Kõik­võimalike variantide „läbi mängimiseks” kuluks  päeva.

Ülesanne 14. Kutsete saatmine

Vastus. Nii saaks tekkida  erinevat varianti.

Ülesanne 15. Klassi õpilaste järjestamine

Ülesanne 16. Külalised ja toolid

Vastus. Neli külalist saavad istuda kuuele toolile  erineval viisil.

Ülesanne 17. 5-kohaline arvkood
  1. koodis ei tohi olla korduvaid numbreid?

    Vastus. Siis saab moodustada  erinevat koodi.
  2. koodis võib olla korduvaid numbreid?

    Vastus. Siis saab moodustada  erinevat koodi.
Ülesanne 18. Arvu faktoriaal

3!\ +\ 4! =  = 

4!\ -\ 3! =  = 

\frac{18!}{16!} =  = 

3!\ \cdot\ 4! =  = 

5!\ \cdot\ 6 =  = 

\frac{1!\cdot19!}{20!} =  = 

4!\ :\ 3! =  = 

8!\ :\ 56 =  = 

\frac{6!\cdot9!}{3!\cdot5!} =  = 

Ülesanne 19. Naturaal­arvud 1, 2, 3, 4, 5 faktoriaalide abil

1 = 

2 = 

3 = 

4 = 

5 = 

Ülesanne 20. Lihtsustamine

\left(n+1\right)\cdot n\cdot\left(n-1\right)! = 

\left(n-1\right)\cdot n!+n\cdot\left(n-1\right)! = 

\frac{n!}{\left(n-1\right)!}-\frac{\left(n+1\right)!}{n!} = 

\frac{\left(n+3\right)\left(n+2\right)\left(n+1\right)n!}{\left(n+4\right)!} = 

Ülesanded B

Ülesanne 21. Lihtsustamine

\frac{n!}{\left(n-1\right)!}+\frac{n!}{2!\left(n-2\right)!} = 

\frac{\left(n-1\right)!\cdot n\cdot\left(n+1\right)}{n!}+\frac{\left(n+1\right)!}{\left(n-1\right)!} = 

Ülesanne 22. Erinevate permutatsioonide arv

Kui n elemendi seas üks element kordub s korda ja teine element kordub t korda, siis erinevate permutatsioonide arv on \frac{n!}{s!t!}. Põhjendage seda.

Ülesanne 23. Viie­kohalised arvud

Vastus. Nendest numbritest saab moodustada  erinevat viie­kohalist arvu.

Ülesanne 24. Sõna ANANASS

Vastus. Neid tähti saab järjestada  erineval viisil.

Ülesanne 25. Kaksikud

Vastus. Kokku­tulnuid saab järjestada  erineval viisil.

Ülesanne 26. Õpikud

Vastus. Selleks on  erinevat võimalust.

Ülesanne 27. Arvu miljard tegurid

Vastus. Arvul 1 000 000 000 on  erinevat tegurit.

Ülesanne 28. Viie­kohalised arvud

Vastus. Korduvate numbritega on  5-kohalist arvu, mis moodustab % kõigist 5-kohalistest arvudest. 4-kohaliste arvude korral on see protsent .

Ülesanne 29. Vana­vanemate vana­vanemad

Vastus. Igal inimesel on  vana­vanemate vana­vanemat ja vana­vanemate vana­vanematel on  vana­vanemate vana­vanemat.

Ülesanne 30. Anagrammid

Leidke:

  1. sõna „sai” anagrammid.
    Vastus. Need on  ja .
  2. oma eesnime anagrammid
    Vastus. Need on .
  3. Mitu erinevat permutatsiooni saate moodustada oma pere­konna­nimest?
    Vastus. Minu pere­konna­nimest saab moodustada  permutatsiooni.
Ülesanne 31. Võrrandi lahendamine

P_x=56P_{x-2}

x

Please wait