Kombinatsioonid

Kursus „Tõenäosus­teooria ja matemaatilise statistika elemente”

Näide 1.

Ülesandes 18 küsisime, mitmel erineval viisil saavad neli külalist istuda kuuele toolile. See tähendab: mitmel erineval viisil saavad neli külalist valida kuue tooli seast neli tooli ja mitmes erinevas järjestuses saavad nad valitud toolidele istuda. Vastuseks oli 6 · 5 · 4 · 3 = 360.

Leiame nüüd, mitmel erineval viisil saavad 4 külalist valida 6 tooli seast nelja. Kes millisel välja­valitud toolil istub (sisuliselt istumise järjestus toolidel), ei ole tähtis.

Kuna 4 külalist saavad iga valitud nelja tooli peal istuda 4! erinevas järjestuses, siis meid huvitav vastus on ülesande 18 vastusest 4! = 4 · 3 · 2 · 1 = 24 korda väiksem. Seega saavad 4 külalist valida 6 tooli seast nelja 360 : 24 = 15 erineval viisil.

Nii tekkinud 4-toolilisi ühendeid kuuest erinevast toolist nimetatakse kombinatsioonideks 6 elemendist 4-kaupa ja neid on 15. Rõhutame, et kombinatsioonide korral ei ole elementide järjestus tähtis.

Kombinatsioonid defineeritakse üld­juhul järgmiselt:

Kombinatsioonideks n elemendist k-kaupa (k ≤ n) nimetatakse n-elemendilise hulga k-elemendilisi osahulki.

Näide 2.

Antud on hulk {a; b; c; u}. Sellel hulgal on neli elementi, s.t n = 4. Moodustame neist kõik­võimalikud 3-elemendilised osa­hulgad: {a; b; c}, {a; b; u}, {a; c; u}, {b; c; u}. Et elementide järjestus ei ole tähtis, siis on need osa­hulkades tähestikulises järje­korras.

Järelikult kombinatsioone neljast elemendist 3-kaupa on 4.

Kombinatsioonide arvu n elemendist k-kaupa tähistatakse sümboliga C_n^k või sümboliga \left(_k^n\right), mida loetakse n üle k.

Seega näite 1 korral on C_6^4=15 ja näite 2 korral C_4^3=4.

Püüame selgusele jõuda, kuidas neid väärtusi lihtsamalt arvutada. Näitest 1 selgub, et C_6^4=\frac{6\cdot5\cdot4\cdot3}{4!}. Laiendame murdu arvuga 2!, et lugejasse tekiks 6!. Selle tulemusena saame C_6^4=\frac{6\cdot5\cdot4\cdot3\cdot2\cdot1}{4!\cdot2!}=\frac{6!}{4!\cdot2!}. Et ka 2! esitub algselt teada olevate arvude 6 ja 4 kaudu kujul (6 − 4)!, siis C_6^4=\frac{6!}{4!\cdot\left(6-4\right)!}=15.

Analoogiliselt saame näite 2 korral: C_4^3=\frac{4!}{3!\cdot\left(4-3\right)!}=\frac{4!}{3!\cdot1!}=4.

Seega arvutatakse kombinatsioonide arv n elemendist k-kaupa valemiga

Cnk=n!k! · (n-k)!.

Näide 3.

Spordi­kooli kahe­kümnest tütar­lapsest oli tarvis moodustada 6-liikmeline võrk­palli­võist­kond. Mitu erinevat võist­konda saanuks moodustada?

Et võist­konda kuuluvate tütarlaste järjestus ei ole tähtis, siis tegemist on kombinatsioonidega.

Järelikult C_{20}^6=\frac{20!}{6!\cdot\left(20-6\right)!} = \frac{20!}{6!\cdot14!} = \frac{20\cdot19\cdot18\cdot17\cdot16\cdot15\cdot14!}{6\cdot5\cdot4\cdot3\cdot2\cdot1\cdot14!}, mis pärast taandamist ja arvutamist annab, et 20 tütar­lapsest võib koostada 38 760 erinevat võrk­palli­võist­konda.

Kehtib ka seos

Cnk=Cnn-k.

mille õigsus ilmneb kohe, kui kirjutada välja C_n^k ja C_n^{n-k} avaldised. Näiteks C_7^5=C_7^2=21.

Ühe­elemendilise hulga (n = 1) elementidest saab moodustada ühe­elemendilisi (k = 1) osa­hulki (kombinatsioone) vaid ühe. Seega C_1^1=1. Et sama tulemuse saaksime valemist C_n^k=\frac{n!}{k!\cdot\left(n-k\right)!}, peab 1=\frac{1!}{1!\cdot\left(1-1\right)!} ehk 1=\frac{1}{0!}. See on aga võimalik vaid siis, kui defineerida

0! = 1.

Definitsioonide 1! = 1 ja 0! = 1 tõttu saab nüüd ka sümbol C_n^0 tähenduse ja arvulise väärtuse: C_n^0=\frac{n!}{0!\cdot\left(n-0\right)!}=\frac{n!}{1\cdot n!}=1. Kombinatsioonide definitsiooni kohaselt on sümbol C_n^0 n-elemendilise hulga null-elemendiliste osa­hulkade (sisuliselt tühja hulga kui osa­hulga) arv. Selliseid osa­hulki \left\{\ \right\}=\varnothing on igal hulgal vaid üks, sest arvutamisel saime ju, et C_n^0=1.

Avaldise C_n^k väärtused esinesid varjatult juba põhi­koolis õpitud valemites:​

\left(a+b\right)^1=a+b     ehk     \left(a+b\right)^1=C_1^0a+C_1^1b

\left(a+b\right)^2=a^2+2ab+b^2     ehk     \left(a+b\right)^2=C_2^0a^2+C_2^1ab+C_2^2b^2

\left(a+b\right)^3=a^3+3a^2b+3ab^2+b^3     ehk     \left(a+b\right)^3=C_3^0a^3+C_3^1a^2b+C_3^2ab^2+C_3^3b^3

Nende valemite üldistuseks on nn Newtoni binoom­valem

(a+b)n=Cn0an+Cn1an-1b+Cn2an-2b2+…+Cnn-1abn-1+Cnnbn

kus kordajaid C_n^0, C_n^1, C_n^2, … C_n^{n-1}, C_n^n nimetatakse binoom­kordajateks.

Võttes Newtoni binoom­valemis a = b = 1, saame, et binoom­kordajate summa

Cn0+Cn1+Cn2+…+Cnn=2n.

Järelikult n-elemendilisel hulgal (vt kombinatsioonide definitsiooni) on osa­hulki (kaasa arvatud tühi hulk) 2^n.

Näide 4.

Anetal on 5 sõbrannat. Ta otsustas, et igal püha­päeval läheb ta oma sõbrannadest erineva selts­konnaga kinno, aga üksinda kinno ei lähe. Mitmel püha­päeval pidi Aneta kinos käima?

Ühe sõbrannaga läks Aneta kinno C_5^1 korral, kahe sõbrannaga C_5^2 korral jne ning lõpuks viie sõbrannaga vaid C_5^5 korral. Seega tuli kokku kinos käia C_5^1+C_5^2+C_5^3+C_5^4+C_5^5=2^5-C_5^0 ehk 32 – 1 = 31 korda.

Paigutades binoom­kordajad all­järgneval viisil, saame nn Pascali kolm­nurga

Arvutatult on Pascali kolm­nurk järgmine:

Viimast Pascali kolm­nurka on lihtne välja kirjutada ja ka jätkata. Kolm­nurga külgedel on ühed. Üle­jäänud arvud on kahe nende kohal oleva arvu summa. Kuuenda rea moodustavad seega 1; 1 + 5 = 6; 5 + 10 = 15; 10 + 10 = 20; 10 + 5 = 15; 5 + 1 = 6 ja 1.

Näide 5.

Kirjutame välja binoom­valemi (a + b)5.

Et n = 5, saame binoom­kordajad Pascali kolm­nurga viiendast reast ja

(a + b)5 = a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5.

Seotud sisu
Muud tegevused

Ülesanded

Vastus. Auhinnad võivad jaotuda võist­kondade vahel  erineval viisil.

Vastus. See nime­kiri võis tekkida  erinevas järjestuses.

Meil on tunni­plaanis  õppe­ainet.

Mitmel erineval viisil saab nendest ainetest koostada ühe päeva tunni­plaani, kui päevas on 5 erinevat tundi ja

  1. matemaatika­tund ei tohi olla esimene?
    Vastus. 
  2. kehalise kasvatuse tund võib olla vaid viimane?
    Vastus. 

Vastus. Koos­oleku juhataja ja protokollija valimiseks on  erinevat viisi.

  • Kui palju on võimalusi siis, kui ei ole oluline, kumb juhatab koos­olekut, kumb protokollib?

Vastus. Kui ei ole oluline, kumb juhatab koos­olekut, kumb protokollib, siis on võimalusi .

Vastus. Saadi  kordumatut ülesannet.

C_{509}^{507} = 

C_8^5\ :\ C_8^3 = 

C_{10}^5\left(C_7^2-C_9^2\right) = 

18\cdot17\cdot16\ :\ C_{18}^6 = 

Vastus. Seda saab teha  erineval viisil.

  1. 8 punkti

    Vastus. 8 punktiga on määratud  erinevat sirget.
  2. 20 punkti

    Vastus. 20 punktiga on määratud  erinevat sirget.
  3. n punkti

    Vastus. n punktiga on määratud  erinevat sirget.
  • Mitu erinevat sirget on nende punktidega määratud?
    Vastus. Nende punktidega on määratud  erinevat sirget.
  • Tehke vastav joonis ja kirjutage need sirged välja.
  • Mitu kolm­nurka on nende punktidega määratud? Kirjutage need.
    Vastus. Nende punktidega on määratud  kolm­nurka: .

Vastus. Selleks on  võimalust.

Vastus. Võist­kondi saab moodustada  erineval viisil.

Vastus. Nad saavad laudade juurde istuda  erineval viisil.

C_9^3=C_9^k?

Vastus. Võrdus kehtib kui k =  ja kui k = .

Vastus. Koostada oli võimalik  erinevat menüüd.

Vastus. See laud­kond saab oma võist­konda valida  erineval viisil.

  1. 8 roosaks ja 8 roheliseks?

    Vastus. Nii saab värvida  erineval viisil.
  2. 2 punaseks ja üle­jäänud mustaks?

    Vastus. Nii saab värvida  erineval viisil.
  3. 2 punaseks, 4 siniseks ja 10 pruuniks?

    Vastus. Nii saab värvida  erineval viisil.

Vastus. Ruumi saab nende lampidega valgustada  erineval viisil.

  • Kui palju on võimalusi, kui süüdata tohib kõige rohkem 5 lampi?

Vastus. Siis on  erinevat võimalust ruumi valgustamiseks.

Vastus. Selleks kulus  nädala­vahetust.

Joon 1.2

Vastus. D1 juurde  viisil, D2 juurde  viisil, D3 juurde  viisil, D4 juurde  viisil ja D5 juurde  viisil.

Võrdle teede pikkust.

Seotud sisu
Muud tegevused