Kombinatoorika tööleht (2)

KOMBINATOORIKA
2
Kombinatoorika tegeleb üldiste meetodite ja valemite loomisega
niisuguste ülesannete lahendamiseks, kus tuleb leida erinevate
võimaluste arv mingis mõttes eristatavate hulkade moodustamiseks.
Näiteks kui meil on vaja numbritest 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
moodustada neljakohalisi naturaalarve, siis saame neid arve eristada
selles esinevate kohtade arvu järgi, aga lisaks sellele veel selle järgi,
kas selles neljakohalises arvus on korduvaid numbreid , kas selles võib
esikohal olla number 0, kas numbrite erinev järjestus annab erineva arvu
jne. Seega on ennekõike vaja ülesande teksti põhjal määrata ühendite
arvu määramise eeskirjad.
Ühendeiks nimetatakse mingeist esemeist ehk elementidest
moodustatud rühmi, mis erinevad üksteisest kas elementide endi,
nende järjestuse või arvu poolest. Niisugust üldist definitsiooni saab
väga mitmel viisil täpsustada. Järgnevalt vaatleme kuut kõige
olulisemat võimalust selleks ja esitame vastavate ühendite arvude
leidmiseks vajalikud valemid.
Variatsioonideks n elemendist m kaupa nimetatakse selliseid
ühendeid, milledest igaüks sisaldab m elementi, mis on võetud
antud n erineva elemendi hulgast ja mis erinevad üksteisest kas
elementide endi või nende järjestuse poolest (loomulikult ei saa m
olla suurem kui n).
Kõigi erinevate variatsioonide arvu n elemendist m kaupa
tähistatakse sümboliga m
Vn (vahel ka m
An ). Arvu m
Vn leidmiseks
arutleme näiteks järgmiselt.
Variatsiooni esimese elemendi valimiseks on n võimalust (nii
palju on üldse erinevaid elemente). Kui see element on juba välja
valitud, siis teise elemendi valimiseks jääb n - 1 võimalust, sest nii
palju on nüüd veel vabu elemente. Seega variatsiooni kahe esimese
elemendi valimiseks on kokku n(n - 1) erinevat võimalust. Edasi näeme,
et variatsiooni kolmanda elemendi valimiseks on n - 2 võimalust,
neljanda elemendi valimiseks n - 3 võimalust jne kuni lõpuks
variatsiooni viimase (m -nda) elemendi valimiseks jääb võimalusi n - (m
- 1) = n - m + 1. Kokkuvõttes on erinevate valikute (variatsioonide) arv
lihtsalt nende üksikvalikute arvude korrutis:
V m n(n 1) ... (n m 1).
n
3
Näiteks kui antud elementideks on tähed a, b, c, d ja e (n = 5), siis
kolmetäheliste (m = 3) sõnade moodustamiseks neist leidub
3 5 4 3 60
V5 võimalust.
Nendeks sõnadeks on:
abc adb bac bda cab cda dab dca eab eca
abd adc bad bdc cad cdb dac dcb eac ecb
abe ade bae bde cae cde dae dce ead ecd
acb aeb bca bea cba cea dba dea eba eda
acd aec bcd bec cbd ceb dbc deb ebc edb
ace aed bce bed cbe ced dbe dec ebd edc
Permutatsioonideks n erinevast elemendist nimetatakse
selliseid, antud n elemendist koosnevaid ühendeid, mis erinevad
üksteisest elementide järjestuse poolest.
Kõigi võimalike erinevate permutatsioonide arvu n elemendist
tähistatakse sümboliga Pn. Selle arvu leidmiseks paneme tähele, et
permutatsioonid n elemendist on samad, mis variatsioonid n elemendist
n kaupa. Seega
Pn = n
Vn = n(n - 1) ... (n - n + 1) = n!
Näiteks elementidest a, b, c ja d (n = 4) saab moodustada Pn = 4! = 24
permutatsiooni:
abcd adbc bcad cabd cdab dbac
abdc adcb bcda cadb cdba dbca
acbd bacd bdac cbad dabc dcab
acdb badc bdca cbda dacb dcba.
Eelpool näites olnud elementidest a, b, c, d ja e (n = 5) saaks siis
moodustada P5 = 5! = 120 sõna, mis erinevad üksteisest vaid
elementide järjestuse poolest, kuid koosnevad ühtedest ja samadest
elementidest.
Kombinatsioonideks n elemendist m kaupa nimetatakse
selliseid ühendeid, millest igaüks sisaldab m elementi, mis on
võetud n erineva elemendi hulgast ja mis erinevad üksteisest
vähemalt ühe elemendi poolest.
Kõigi võimalike erinevate kombinatsioonide arvu n elemendist m
kaupa tähistatakse sümboliga m
Cn . Arvu m
Cn leidmiseks on sobiv
kasutada seost m
m
n
m
Vn C P , sest teostades kõigis m kaupa
4
moodustatud kombinatsioonides kõik võimalikud permutatsioonid
saame ju kõik m kaupa moodustatud variatsioonid. Seega
!( )!
( 1) ... ( 1)
m n m
n
m
n n n m
P
V
C
m
m
m n
n 


.
Näiteks elementidest a, b, c, d ja e (n = 5) saab kolme elemendilisi
(m = 3) valikuid teostada 10
6 2
120
3!2!
3 5!
5 
C  erineval viisil:
abc abe ace bcd bde
abd acd ade bce cde.
Seega erinevus variatsioonidest seisneb selles, et kombinatsioonide
puhul ei loeta näiteks sõnu abc, bca ja cab erinevateks.
Senivaadatud ühendites me eeldasime iga kord, et kõik antud
n elementi on erinevad ja et ühes ühendis võib iga element esineda
ülimalt ühe korra. Praktika probleemid nõuavad aga vahel ühendite
üldistamist ka nendele juhtudele , mil kas antud elementide hulgas
esineb ühesuguseid või antud elementidest igaüks võib ühes ja samas
ühendis esineda mitu korda.
Esinegu antud n elemendi hulgas korda element a, korda
element b jne, korda element l, kusjuures + + ... + = n. Neist n
elemendist moodustatud permutatsioone nimetatakse kordumistega
permutatsioonideks.
Kõigi võimalike erinevate kordumistega permutatsioonide arvu n
elemendist (mis ei pruugi olla erinevad) tähistatakse sümboliga
Pn(,,...,).
Kui = = ...= = 1 (iga element esineb ainult üks kord), siis
muidugi Pn(1,1,...,1) = Pn = n! .
Arvu Pn(,,..,) leidmiseks üldjuhul arutleme järgmiselt. Varustame
elemendid a (neid on tükki) indeksitega 1,2,...,, ele- mendid b
indeksitega 1,2,...,jne, elemendid l indeksitega 1,2, ...,. Sel teel
saame kunstlikult n elementi, mis kõik erinevad üksteisest kas elemendi
enda või vähemalt indeksi poolest:
a1, a2,..., a, b1, b2, ..., b, ..., l1,l2, ..., l.
Moodustame nendest n erinevast elemendist kõik tavalised Pn = n!
permutatsiooni ja vaatleme neist üht konkreetset. Selles permutatsioonis
elemendid a1,a2, ..., aesinevad kindlal kohal, elemendid b1,b2,...,b
eelmistest erineval kindlal kohal jne, lõpuks elemendid l1, l2,...,l
kõigist eelpool nimetatud elementidest erineval kindlal kohal.
5
Teostame meie valitud permutatsioonis elementidega a1,a2,...,akõik
P=! võimalikku omavahelist permutatsiooni. Sel teel saame P
permutatsiooni, mis omavahel erinevad elementide a1,a2,...,aindeksite
järjekorra poolest. Teostame nüüd igas saadud Ppermutatsioonis
elementidega b1,b2,...,bkõik P= ! võimalikku omavahelist
permutatsiooni. Siis saame igaühest Ppermutatsiooni, mis omavahel
erinevad nüüd juba elementide b1,b2,...,bpaigutuse järjekorra (mitte
kohtade) poolest. Kokku oleme nüüd juba saanud P
Ppermutatsiooni. Nii edasi toimides teostame lõpuks kõikides sel
teel saadu permutatsioonides elementidega l1,l2,...,lkõik P= !
võimalikku omavahelist permutatsiooni, saades igaühest Puut, mis
omavahel erinevad jällegi vaid elementide l1,l2,...,lindeksite järjekorra
poolest. Selliselt toimides saame meie poolt valitud konkreetsetest
permutatsioonidest moodustada PP...Ppermutatsiooni, milledes
kõikides elemendid a1,a2,...,aasuvad ikka samadel kindlal kohal,
elemendid b1,b2,...,bsamadel kindlal kohal jne, elemendid l1,l2,...,l
samadel kindlal kohal, kuid mis kõik üksteisest erinevad elementide
indeksite järjekorra poolest, kuuludes seega esialgu moodustatud Pn
permutatsiooni hulka.
Nüüd jätame kõigis saadud PP... Ppermutatsioonis
elementide juures indeksid ära. Siis kujutavad nad endast kõik üht ja
sama kordumistega permutatsiooni.
Toimides samuti mõne teise permutatsiooniga, milles elemendid
a1, a2, ..., lasuvad mingitel teistel, vaadeldust erinevatel kohtadel,
saame jällegi PP... Pühesugust kordumistega permutatsiooni. Seega
moodustatud Pn permutatsiooni hulgas iga erinev kordumistega
permutatsioon esineb PP... Pkorda. Erinevate kordumistega
permutatsioonide arvu me aga tähistasime sümboliga Pn(,,...,).
Järelikult Pn = P×P...PPn(,,..,) , millest
Pn(,,...,) =
! ! ... !
a b ... l a b l


n
P P P
Pn .
Näiteks elementidest a, a, b, b, b saab toodud valemi kohaselt
moodustada P5(2,3) =
2! 3!
5!
= 10 erinevat kordumistega permutatsiooni ja
nimelt:
6
aabbb abbab baabb babba bbaba
ababb abbba babab bbaab bbbaa.
Kordumistega variatsioonideks n erinevast elemendist m
kaupa nimetatakse selliseid m elemendist koosnevaid variatsioone,
milledes 2, 3, ..., m elementi võivad olla ühesugused (nüüd võib m olla
ka suurem kui n).
Kõigi võimalike erinevate kordumistega variatsioonide arvu n
elemendist m kaupa tähistatakse sümboliga m
Wn . Selle arvu leidmiseks
paneme tähele, et variatsiooni esimese elemendi valimiseks on n
võimalust, teise elemendi valimiseks jälle n võimalust jne. Seega
m m
Wn n .
Näiteks kasutades trükkimisel ainult tähti a ja b saab moodustada
5
W2 = 25 = 32 erinevat viietähelist sõna:
aaaaa aabaa abaaa abbaa baaaa babaa bbaaa bbbaa
aaaab aabab abaab abbab baaab babab bbaab bbbab
aaaba aabba ababa abbba baaba babba bbaba bbbba
aaabb aabbb ababb abbbb baabb babbb bbabb bbbbb.
Kordumistega kombinatsioonideks n erinevast elemendist m
kaupa nimetatakse niisuguseid kombinatsioone m kaupa, milledes 2, 3,
..., m elementi võivad olla ühesugused (ka siin võib m olla suurem kui
n).
Kõigi võimalike erinevate kordumistega kombinatsioonide arvu n
elemendist m kaupa tähistatakse sümboliga m
n .
Selle arvu leidmisel saab kasutada seost m
n m
m
n C 1 ( mille
õigsuse võib tõestada täiliku induktsiooni meetodiga).
Näiteks elemente a ja b kasutades saab moodustada 5
6
5
2 C = 6
erinevat viieelemendilist hulka:
aaaaa aaabb abbbb
aaaab aabbb bbbbb.
Kombinatoorikaülesandeid saab sageli lahendada ka ilma
siintoodud valemeid kasutamata ja seda tuleks arvestada kontrolltöö
ülesannete lahendamisel.
Järgnevalt toome mõningad näited .
7
Näide 1. Kui mitu erinevat kolmest saiakesest koosnevat
lõunaoodet saab kohvikus tellida , kui menüü sisaldab 11 erinevat
nimetust ?
Nagu ikka kombinatoorikaülesannete lahendamisel, tuleb siin kõigepealt
selgitada, millal lugeda kaht lõunaoodet (ühendit) teineteisest
erinevateks. Antud juhul on erinevad näiteks tellimused A, B, C ja A, B,
D (erinevad elementide eneste poolest), aga samuti A, A, B ja A, B, B
(erinevad tellimuste proportsioonide poolest, kuid sisaldavad endas
korduvaid elemente). Kokkulangevateks tuleb aga lugeda näiteks
tellimused A, B, C ja B, A, C, sest tellimuse esitamise järjekord
saadavaid lõunaooteid ei erista.
Seega selleks, et leida erinevate võimalike lõunaoodete arvu,
tuleb leida kõigi võimalike kordumistega kombinatsioonide arv 11
elemendist 3 kaupa, st otsitav arv on 286
3! 10!
3 13!
13
3
11 3 1
3
11 
C C .
Vastus: Kohvikust saab tellida 286 erinevat lõunaoodet.
Näide 2. Kui mitmel erineval viisil on võimalik panna kuus
erinevat münti kolme taskusse ?
Selle ülesande lahendamisel arutleme näiteks järgmiselt. Meil on
antud kuus erinevat münti m1, m2, m3, m4, m5, m6 kolm taskut 1, 2, 3.
Asjaolu, et münt mi (i=1,2,...,6) pannakse taskusse T (T = 1,2,3), võib
tähistada tasku numbri 1, 2, 3 kirjutamisega jada m1, m2, ..., m6 i- ndale
kohale. Seega näiteks jada 3, 2, 2, 1, 3, 1 (ehk kuuekohaline arv
322131) tähistab situatsiooni, kus münt m1 on taskus 3, münt m2 on
taskus 2, münt m3 on taskus 2, münt m4 on taskus 1, münt m5 on taskus
3 ja münt m6 on taskus 1.
Kui kaks müntide paigutust erinevad, siis peavad muidugi erinema
ka vastavaid situatsioone kirjeldavad kuuekohalised arvud. Samuti on
ilmne, et kui kaks kuuekohalist arvu (mis koosnevad numbritest 1, 2 ja
3) ei ole võrdsed, siis erinevad ka vastavad müntide paigutused
taskutesse. Seega võimalused müntide paigutamiseks taskutesse
erinevad nii müntide (elementide) endi kui ka nende järjestuse poolest
(esimene münt taskus 1 ja teine münt taskus 3 on erinev sellest kui
esimene münt taskus 3 ja teine münt taskus 1). Sellisele arutelule
tuginedes võime oma esialgse ülesande ümber sõnastada kujul: kui mitu
erinevat kuuekohalist arvu saab moodustada numbritest 1, 2 ja 3? Seega
8
saadud ülesande lahendamine tähendab aga kordumistega variatsioonide
arvu leidmist kolmest elemendist kuue kaupa, st otsitav paigutuste arv
on 6 36 729
W3 .
Vastus: Seda on võimalik teha 729 erineval viisil.
Näide 3. Mingis tsehhis töötab masin, millel valmistatakse kahte
erinevat tüüpi detaile ( kummagi detailitüübi ühe eksemplari
valmistamiseks kulub 5 minutit). Ühe tunni jooksul tuleb
valmistada esimest tüüpi detaile 7 ja teist tüüpi detaile 5 tükki. Kui
mitme erineva programmi järgi võib masin sellise plaani täitmisel
töötada, kui eeldada, et masina ümberlülitamine aega ei võta?
Et masin peab iga programmi korral valmistama esimest tüüpi
detaile 7 ja teist tüüpi detaile 5 tükki, siis kaks programmi erinevad
teineteisest vaid selle poolest, millises järjekorras kästakse neid detaile
valmistada. Seega meid huvitavad kaheteistkümnest elemendist
koosnevad permutatsioonid (erinevad vaid järjestuse poolest, sees
korduvad elemendid) . Seega tuleb leida just kordumistega
permutatsioonide arv. P12(7,5) = 792
7! 5!
12! 
Vastus: Erinevate programmide arv on 792.
Näide 4. Kui palju leidub selliseid ülimalt kahekohalisi
naturaalarve, mis ei jagu kahega, kolmega ega viiega ?
Sellist ülesannet saab lahendada mitmel moel, üks võimalus seda
teha on kasutada nn juurde- ja mahaarvamise valemit, sest osa arve
jagub näiteks nii 2 kui ka 5-ga, me ei saa neid topelt maha arvata. Olgu
meil N eset, millede seast näiteks a1, a2, a3 on omadus jaguda 2, 3 ja 5-
ga ning näiteks N(a1) tähistab a1-ga jaguvate arvude arvu, N(a2) tähistab
a2-ga jaguvate arvude arvu jne ning N(a’1,a’2,a’3) tähistab esemete arvu,
millel pole ühtegi omadust a1, a2, a3 , siis juurde-ja mahaarvamise
valem on järgmine:
N(a’1,a’2,a’3) = N - N(a1) - N(a2) - N(a3) + N(a1,a2) + N(a1,a3) +
+ N(a2,a3) - N(a1,a2,a3), kusjuures N(a1) jne võetakse arvesse täisosa.
Meie näite korral siis N(2’,3’,5’) = 99 - N(2) - N(3) - N(5) + N(2,3) + +
N(2,5) +N(3,5) - N(2,3,5) = 99 - 99/2 - 99/3 - 99/5 + 99/6 + 99/10 + +
99/15 - 99/30 = 99 - 49 - 33 - 19 + 16 + 9 + 6 - 3 = 26.
Vastus: Neid mittejaguvaid arve on 26.
9
Näide 5. Kui palju mittenegatiivseid täisarvulisi lahendeid on
määramata võrrandil x + y + z + w = 7, kui näiteks lahendeid
x = 0, y = 1, z = w = 3 ja x = 1, y = z = 3, w = 0 loetakse
erinevateks?
Mittenegatiivseid erinevatest elementidest koosnevaid lahendigruppe,
mis annavad summaks 7, on 11: (0;0;0;7), (0;0;1;6), (0;0;2;5), (0;0;3;4),
(0;1;1;5), (0;1;2;4), (0;1;3;3), (0;2;2;3), (1;1;1,4), (1;1;2;3), (1;2;2;2).
Neid, kus on 3 korduvat elementi, on 3, neid, kus on 2 korduvat
elementi, on 7 ja ilma korduvate elementideta on 1. Et erinevateks
loetakse näit. ka lahendeid (0;0;0;7) ja (0;7;0;0) jne, st lahendid erinevad
üksteisest elementide järjestuse poolest ning et esinesid eelpool
mainitud kordumised, siis tuleb erinevate lahendite leidmiseks kasutada
kordumistega permutatsioone, nimelt
3 P4(3) + 7 P4(2) + P4 = ... = 120 lahendit.
Vastus: Sellel määramata võrrandil on 120 erinevat mittenegatiivset
täisarvulist lahendit.
Harjutusülesanded
1. Mitu erinevat 11-tähelist sõna on võimalik moodustada tähtede
ümberpaigutamisega sõnas matemaatika ?
2. Kui mitmel erineval viisil saab nimes TEELE tähti selliselt ümber
paigutada, et kolm tähte E ei satuks kõrvuti?
3. Mitu erinevat neljakohalist arvu saab koostada numbritest 0, 1, 3, 6,
8 ja 9, kui numbrid arvus ei tarvitse olla erinevad (arvu 0363 loeme
kolme-, mitte neljakohaliseks)?
4. Auto registreerimisnumber koosnev kolmekohalisest arvust ja
kolmetähelisest sõnast (ka arvu 031 loetakse kolmekohaliseks). Mitu
autot on võimalik registreerida, kui kasutatakse tähti A, B, C, D, E, F,
G, H, I, J, K, L ,M ,N, O, P, R, S, T, U, V, W ?
5. Inglastel on kombeks anda lapsele kuni kolm erineva kõlaga nime.
Kui palju nimevariante tuleb lapsevanematel kõrvale heita, eeldades, et
sobivaid üksiknimesid on nende arvates 100?
10
6. Milliseid arve esineb ülimalt seitsmekohaliste naturaalarvude (st
arvud 1 kuni 9 999 999) hulgas rohkem: kas neid, mille kirjutis sisaldab
numbrit 1, või neid, mille kirjutis numbrit 1 ei sisalda?
7. Naturaalarvud 1 kuni 222 222 222 on kirjutatud ühte ritta . Kui palju
sisaldab see ülipikk kirjutis nulle ?
8. Ühiselamu toas elab 3 üliõpilast. Neil on kokku 4 erinevat tassi, 5
erinevat alustassi ja 6 erinevat teelusikat . Kui mitmel erineval viisil
saavad nad katta laua hommikuseks kohvijoomiseks?
9. Kui palju leidub selliseid ülimalt kolmekohalisi naturaalarve, mis ei
jagu kolmega, viiega ega seitsmega?
10. Kui palju leidub arvust 56 700 000 väiksemaid naturaalarve, mis on
selle arvuga ühistegurita?
11. Maleturniiril on esindatud viis linna, igaüks nelja võistlejaga. Kui
mitmel erineval viisil saab moodustada turniiritabeli nii, et esimeses
voorus kõigil laudadel kohtuksid kaaslinlased?
12. Kui palju mittenegatiivseid täisarvulisi lahendeid on määramata
võrrandil x + y + z + w = 8 (arvestades, et näiteks x = 0, y = 2,
z = w = 3 ja x = 2, y = z = 3, w = 0 on erinevad lahendid)?
13. Kui mitmel erineval viisil saab 36-kaardilise paki jagada kaheks
osaks nii, et kumbki osa sisaldaks kaks ässa?
14. Mitmel viisil saab 36-st kaardist koosnevast kaardipakist valida ühe
kaardi igast mastist ( mastid on risti, ruutu , poti ja ärtu)?
15. Mitmel viisil võib 36-lisest kaardipakist valida ühe kaardi igast
mastist nii, et punaste ja mustade mastide kaardid oleksid ühenimelised
(näiteks poti ja risti üheksad ning ruutu ja ärtu sõdurid)?
16. Koosolekul peavad sõna võtma viis inimest : Jüri, Tiit, Kalle, Eno ja
Marek . Mitmel viisil võib neid paigutada sõnavõtjate nimekirja
tingimusel, et Tiit ei tohi esineda enne Jüri?
17. Mitmel viisil saab ümmarguse laua ümber paigutada 5 meest ja 5
naist nii, et tekiks kirju rida ( st samast soost isikud poleks kõrvuti)?
18. Mitu erinevat neljakohalist neljaga jaguvat arvu saab moodustada
numbritest 1, 2, 3, 4 ja 5, kui arvu üleskirjutamisel võib üht numbrit
kasutada mitu korda?
19. Mitu erinevat võimalust on täringumängus saada 3 viskega 9 silma?
20. Lasti välja loterii , mille 4x5 ruutudes on arvud 1 - 20 ja mille
täitmisel tuleb ristiga märgistada 5 võidunumbrit . Mitu võimalust on
nende viie numbri märgistamiseks?
11
21. Perekond pidi talule nime panema . Mõeldi välja talule
iseloomulikud sõnad : Maasikas, Mägi, Org, Mets, Mänd, Järv, Veski,
Juhan, Karla. Kõik nimed tundusid kenad, peremees arvas , et võiks
panna ühe neist, perenaine , et kahest sõnast koosneva nime (teatavasti
pannakse talule nimi omastavas käändes, st näiteks Oru talu). Nad
otsustasid kõik erinevad võimalused paberile panna. Mitu oletatavat
talunime nad kokku said?
22. Kui palju leidub erinevaid võimalusi selleks, et jaotada 30 töölist
kolmeks 10-liikmeliseks brigaadiks? Kui palju võimalusi on nende
tööliste jaotamiseks kümneks 3-liikmeliseks brigaadiks?
Kontrolltööks M - ......... tuleb Teil lahendada järgmised
ülesanded ....................................................................
Tähtaeg .................................................