Kombinatorika
Kombinatorika je področje matematike, ki se ukvarja s tem, na koliko načinov je možno razporediti neko množico elementov ali na koliko načinov je možno izbrati elemente iz neke množice.
Zgled: V omari imamo 2 para čevljev (rjave in črne), 3 puloverje (rdeč, rumen in bel) in 2 hlače (zelene in modre). Koliko dni lahko hodimo različno oblečeni?
| 
|
Spoznali bomo pravila, ki nam omogočajo, da razporeditve oziroma izbore preštejemo sistematično.
Premešamo kup igralnih kart. Koliko je različnih razporeditev kart v kupu po mešanju?
Takemu vprašanju rečemo tudi iskanje permutacij.
Na tekmi sodeluje 15 tekmovalcev. Koliko je možnih razporeditev tekmovalcev na prvih treh mestih, če ni delitve mest?
Takemu vprašanju rečemo tudi iskanje variacij.
Pri igri loto žrebamo 7 številk iz množice števil od 1 do 39. Koliko je vseh možnih izborov, ki jih lahko izžrebamo?
Takemu vprašanju rečemo tudi iskanje kombinacij.
Kombinatorično drevo
S kombinatoričnim drevesom grafično prikažemo proces izbiranja. Drevo vseh možnosti narišemo tako, da vsako vozlišče razvejimo na toliko vozlišč, kolikor izbir imamo na voljo v danem koraku.
|
Število vseh možnih kombinacij dobimo tako, da preštejemo število listov v drevesu (to je število vozlišč na zadnjem nivoju). Ker pa drevo lahko postane preveliko, kombinatorika pozna še druga pravila za štetje in računanje možnosti.
PREMISLITE
Ali lahko katerikoli kombinatorični problem rešimo s pomočjo kombinatoričnega drevesa?
Da, vendar reševanje nekaterih problemov na tak način ni praktično.
Zgled:
Svetovno znana manekenka ima doma 14 parov čevljev. V naslednjih 14 dneh bi rada obula vsak dan drug par. Koliko možnih 14-dnevnih razporeditev čevljev ima? Poskusite narisati del kombinatoričnega drevesa za to nalogo. Hitro lahko ugotovite, da je drevo preveliko, da bi narisali celega.
Osnovni izrek kombinatorike
Zgled:
Pripravljamo darilo za rojstni dan. Najprej izberemo eno od daril (čokolada, igrača, darilni bon), potem darilo zavijemo v eno od možnosti (škatla, darilna vrečka, darilni papir) in na koncu dodamo pentljo ene izmed barv (rdeča, modra, rumena). Koliko različnih daril imamo na voljo?
Pravilo:
Če najprej izbiramo med možnostmi, potem neodvisno od prvega izbora med možnostmi, potem neodvisno od prejšnjega izbora med možnostmi ... in nazadnje neodvisno od prejšnjih izborov med možnostmi, potem imamo za sestavljeni izbor
možnosti.
Temu pravilu rečemo tudi pravilo produkta.
Neodvisnost pomeni, da imamo ne glede na to, katero možnost izberemo v eni fazi, v naslednji fazi odločanja na voljo enake možnosti.
Poglejmo to na primeru:
V slaščičarni se lahko odločimo med 3 okusi sladoleda (čokoladna, vanilija, jagoda) in naknadno še med 2 prelivoma (čokolada, jagoda). Neodvisnost pomeni, da ne glede na to, kateri okus sladoleda izberemo, lahko potem izberemo kateregakoli izmed 2 prelivov. Odvisnost pa bi pomenila na primer, če bi izbrali čokoladni sladoled, da bi potem lahko izbrali le čokoladni preliv, ne pa tudi jagodnega.
Neodvisnost je zelo pomembna pri osnovnem izreku kombinatorike. Če izbori niso neodvisni, tega pravila ne moremo uporabiti.
Kadar so izbori med seboj neodvisni, je kombinatorično drevo simetrično.
Zgled:
V slaščičarni najprej izberemo tip korneta (sladki, navaden), potem vrsto sladoleda (čokolada, jagoda, vanilija), nato preliv (čokolada, jagoda) in nazadnje še posip (čokolada, kokos).
|
Vsak ponedeljek pa v slaščičarni veljajo posebna pravila. Če izberemo sladki kornet, potem lahko dobimo le jagodni sladoled in posip je lahko le kokos. Če izberemo čokoladni sladoled, potem lahko dobimo le čokoladni preliv in čokoladni posip. Če izberemo vanilijev sladoled, potem ne dobimo ne preliva ne posipa.
|
Pravilo vsote
Zgled: Na kosilo gremo lahko v picerijo, ki ponuja 5 vrst pic ali v mehiško restavracijo, ki ponuja 3 vrste tortilj, ali v italijansko restavracijo, ki ponuja 4 vrste testenin. Koliko različnih kosil imamo na voljo? | 
|
Pravilo:
Če se pri izbiranju odločimo ali za eno od možnosti iz prve množice ali za eno od možnosti iz druge množice ... ali za eno od možnosti, imamo na voljo
možnosti.
Pri pravilu produkta izbiramo elemente iz prve IN druge množice, pri pravilu vsote pa izbiramo iz prve ALI druge množice:
Pri pravilu vsote je pomembno, da so množice, iz katerih izbiramo element, med seboj disjunktne. Če niso, tega pravila ne moremo uporabiti. Dve množici sta disjunktni, kadar nimata skupnih elementov.
Če bi v zgledu na primer italijanska restavracija ponujala namesto 4 vrst testenin 3 vrste testenin in 1 vrsto pice, ki bi bila enaka kot ena od pic iz picerije, ne bi imeli več disjunktnih množic in pravila vsote ne bi mogli uporabiti.
n!
Produktu vseh naravnih števil od 1 do damo posebno ime . To preberemo kot n fakulteta.
Pogosto pri računanju uporabljamo tudi število , zato še za to število definiramo fakulteto.
Fakultete naravnih števil naraščajo zelo hitro. Poglejmo fakultete prvih nekaj naravnih števil:
|
Kaj to pomeni pri računanju števila razporeditev, bomo spoznali v nadaljevanju.
Kaj narašča hitreje, ali
Znamenita zgodba o izumu šaha govori o indijskem vladarju, ki je bil tako navdušen nad igro, da je izumitelju obljubil, karkoli si želi. Izumitelj si je zaželel toliko riža, kot ga je potrebno, če postavimo na prvo šahovsko polje eno zrno, na naslednje dve zrni, na tretje štiri, in tako do zadnjega, 64. polja, na katerega postavimo zrn riža. Vladarju se je zdelo to zelo malo riža, vendar je kmalu ugotovil, da se je zelo uštel. Toliko riža namreč ni premoglo niti celo kraljestvo.
Kaj pa, če bi si izumitelj zaželel toliko riža, kot ga potrebujemo, če postavimo na prvo polje zrn, na drugo , in tako naprej do zadnjega polja, kamor postavimo zrn?
Kaj narašča hitreje, ali
Ker smo se naučili, da eksponentne funkcije naraščajo zelo hitro, se zdi na prvi pogled fakulteta ugodnejša rešitev za vladarja. Vendar ni tako. Zapišimo prvih nekaj vrednosti v tabelo.
|
Izkaže se, da je približno enako že .
Fakulteta narašča hitreje zato, ker zmnožek množimo z vedno večjimi številkami, pri eksponentni funkciji pa zmnožek množimo vedno z istim številom.
Permutacije
Permutacije so razporedbe vseh elementov dane množice v vrsto.
Zgled:
Imamo 7 različnih knjig. Na koliko načinov jih lahko zložimo na knjižno polico?
Pravilo:
Na prvo mesto lahko postavimo kateregakoli izmed elementov. Neodvisno od tega, kateri element smo postavili na prvo mesto, lahko na drugo mesto postavimo kateregakoli izmed preostalih elementov. Tako nadaljujemo do zadnjega mesta, za katerega ostane samo en element. Število vseh možnih razporeditev je torej
Kadar uporabimo to formulo, je pomembno, da so vsi elementi različni. Bolj natančno lahko rečemo, da je to pravilo za permutacije brez ponavljanja. Poznamo pa tudi permutacije s ponavljanjem.
7 različnih knjig lahko razporedimo v vrsto na načinov. Kombinatorično drevo bo torej zelo veliko, rišemo pa ga na način, predstavljen na sliki. V vsak naslednji nivo narišemo en element manj kot je v predhodnem nivoju. Izpustimo tisti element, iz katerega smo naredili razvejišče. To naredimo za vsak element. Drevo je simetrično.
|
Permutacije s ponavljanjem
O permutacijah s ponavljanjem govorimo, kadar imamo v množici nekaj elementov, ki imajo značilnost, po kateri jih razvrščamo, enako.
Zgled:
Prodajalec ima v trgovini 4 rdeče, 2 bela in 1 moder avtomobil. Na koliko načinov jih lahko uredi v vrsto? Avtomobile med seboj loči samo po barvah.
Pravilo:
Vseh možnih razporeditev elementov je , vendar pri tem večkrat štejemo razporeditve elementov, ki so med seboj enaki. Možnih razporeditev elementov med seboj je , zato moramo deliti z . Enako naredimo za ostalih elementov, ki so med seboj enaki.
Razporeditev elementov na mest, pri čemer se element k ponovi -krat, je torej
Formulo za permutacije s ponavljanjem lahko uporabljamo tudi za permutacije brez ponavljanja. V tem primeru se vsak element ponovi samo 1-krat ( za vsak k). Tako iz formule za permutacije s ponavljanjem izpeljemo formulo za permutacije brez ponavljanja.
4 rdeče, 2 bela in 1 moder avtomobil razporedimo v vrsto na načinov. Kot vidimo, je to precej manj kot .
Ko rišemo drevo, pri vsaki razvejitvi narišemo vsako možno barvo samo enkrat, hkrati pa moramo tudi šteti, kolikokrat smo v posamezni veji določeno barvo že uporabili, in ko dosežemo število barv iz naloge, te barve v tisti veji ne smemo več uporabiti. V primerjavi z drevesom pri permutacijah brez ponavljanja je to drevo ožje in ni simetrično.
|
Variacije
Pri variacijah izmed elementov izberemo elementov pri čemer je pomemben vrstni red izbranih elementov.
Zgled:
Na voljo imamo črke A, B, D, V, Y. Koliko besed dolžine tri lahko sestavimo iz njih?
Pravilo:
Na prvo mesto lahko postavimo kateregakoli izmed elementov. Neodvisno od tega, kateri element smo postavili na prvo mesto, lahko na drugo mesto postavimo kateregakoli izmed preostalih elementov. Tako nadaljujemo do -tega mesta, na katerega lahko postavimo enega izmed preostalih elementov. Število vseh možnih razporeditev je torej
Tako kot imamo permutacije brez ponavljanja in s ponavljanjem, tako imamo tudi variacije obojih vrst. Ta formula se uporablja za variacije brez ponavljanja.
Produkt
je del izraza za . Manjka še del
Če produkt pomnožimo in delimo z njim, se vrednost produkta ne bo spremenila. Dobimo
Števec in imenovalec zdaj zapišimo s fakulteto
Kombinatorično drevo za variacije brez ponavljanja gradimo podobno kot drevo za permutacije brez ponavljanja. Edina razlika je, da je drevo krajše. Število nivojev je enako številu mest, na katera razporejamo, to pa je manjše od števila elementov.
|
Permutacij elementov je , variacij elementov na mestih pa . Kadar je različen od , je ulomek manjši od kadar je pa je ulomek enak . Permutacij je torej več kot variacij, razen kadar je , takrat je permutacij toliko kot variacij.
Kako pa to vidimo intuitivno? Vzemimo množico števk od 1 do 9. Permutacije so 9-mestna števila brez ponavljanja. Vzemimo za variacije in , to so variacije 9 števil na 6 mestih, kar pomeni vsa 6-mestna števila brez ponavljanja. 6-mestnih števil je zagotovo manj kot 9-mestnih. Če pa vzamemo variacije 9 števil na 9 mestih pa je to enako kot permutacije 9 števil.
Variacije s ponavljanjem
Kadar od različnih elementov pri čemer se vsak lahko ponovi poljubno mnogo krat, izberemo elementov za katere je pomemben vrstni red izbora, govorimo o variacijah s ponavljanjem.
Zgled:
Koliko trimestnih števil lahko sestavimo s ciframi 1, 2, 3, 4, in 5, če se cifre lahko ponavljajo?
Pravilo:
Določeno imamo število različnih elementov in število mest, , na katera razporejamo elemente. Na vsako od mest lahko postavimo kateregakoli od elementov, ker imamo na voljo poljubno število ponovitev, zato je formula za izračun vseh kombinacij enaka
Pri permutacijah s ponavljanjem imamo število ponovitev posameznega elementa točno določeno in število vseh elementov skupaj s številom ponovitev je enako številu mest. Pri variacijah s ponavljanjem pa število ponovitev ni omejeno, imamo pa določeno število mest, na katera elemente razporejamo. Različnih elementov je lahko več ali manj kot mest, medtem ko pri variacijah brez ponavljanja število elementov mora biti večje (ali enako) od števila mest.
Če vzamemo variacije n elementov na r mest, potem je tistih s ponavljanjem več kot brez ponavljanja. To pa zato, ker pri variacijah s ponavljanjem pridejo v poštev vse variacije brez ponavljanja in dodatno še tiste s ponavljanjem.
Zgled:
Opremljamo spalnico. Izbrati moramo barvo zaves, barvo sten in barvo posteljnine. Na voljo imamo 4 različne barve, rumeno, modro, belo in zeleno. Če imamo pogoj, da moramo uporabiti različne barve, potem so to variacije brez ponavljanja. Če lahko barve izbiramo poljubno, so to variacije s ponavljanjem. Kadar imamo variacije brez ponavljanja, lahko izberemo kombinacijo barv rumena, bela, zelena, ne moremo pa izbrati kombinacije bela, bela, modra. Kadar imamo permutacije s ponavljanjem, pa lahko izberemo tako prvo kot drugo kombinacijo barv. Izberemo lahko tako tiste kombinacije, kjer se barve ne ponavljajo, kot tiste, kjer se barve ponavljajo. Zato je variacij s ponavljanjem več kot variacij brez ponavljanja.
S ciframi 1, 2, 3, 4, in 5, če se cifre lahko ponavljajo, sestavimo trimestnih števil. Kombinatorično drevo rišemo tako, da imamo v vsaki fazi in pri vsakem elementu na voljo vse elemente. Rišemo ga do globine, ki je enaka številu mest, na katera razporejamo elemente. Drevo je simetrično in od vseh dreves najširše.
|
Kombinacije
O kombinacijah govorimo takrat, ko iz različnih elementov izberemo elementov za katere ni pomembno v kakšnem vrstnem redu jih izbiramo. Še drugače, kombinacije so podmnožice dane množice.
Zgled:
Imamo 7 vrst sadja. Koliko različnih sadnih solat s 4 vrstami sadja lahko naredimo?
Pravilo:
Določeno imamo število različnih elementov, , in število mest, , na katera razporejamo elemente, vendar vrstni red elementov ni pomemben. Razporejanje elementov na mest so variacije. Pri tem prevečkrat štejemo razporeditve z istimi elementi na različnih mestih. Razporeditev elementov na mestih je . S tem številom delimo število variacij, da dobimo število kombinacij. Formula je:
Tej vrsti izbora rečemo tudi kombinacije brez ponavljanja.
Pri variacijah je vrstni red pomemben, pri kombinacijah pa ne.
Zgled:
Primerjajmo igri LOTO in LOTKO. Pri igri Loto izžrebajo 7 kroglic s številkami. Ne glede nato, v kakšnem vrstnem redu so izžrebali številke, je dobitnik glavne nagrade tisti, ki ima na svojem listku vse številke. Pri igri Lotko pa po vrsti izžrebajo 6 številk in dobitnik glavne nagrade je tisti, ki ima na svojem listku številke v točno takem vrstnem redu, kot so bile po vrsti izžrebane.
Pri igri Loto zaporedje 1, 27, 14, 2, 5, 36, 20 predstavlja enako kombinacijo kot zaporedje 1, 2, 5, 14, 20, 27, 36. Pri igri Lotko pa zaporedji 135788 in 815783 predstavljata različni možni razporeditvi.
Binomski simbol
Izraz, s katerim računamo kombinacije,
zapišemo še drugače
Temu simbolu rečemo binomski simbol. Preberemo ga "n nad r". Pove nam, koliko podmnožic moči ima množica z močjo .
Vrednosti binomskih simbolov enostavno brez računanja preberemo iz Pascalovega trikotnika.
| 1 | |||||||||||||||
| 1 | 1 | ||||||||||||||
| 1 | 2 | 1 | |||||||||||||
| 1 | 3 | 3 | 1 | ||||||||||||
| 1 | 4 | 6 | 4 | 1 | |||||||||||
| 1 | 5 | 10 | 10 | 5 | 1 | ||||||||||
| 1 | 6 | 15 | 20 | 15 | 6 | 1 | |||||||||
| 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 |
V zapisu predstavlja vrstico v Pascalovem trikotniku, pa element v -ti vrstici. Vrstice in elemente štejemo od 0 naprej.
Zapis pomeni, koliko praznih množic je v množici z elementi. Taka množica je ena sama, zato je
Zapis pomeni, koliko množic z enim elementom je v množici z elementi. Takih množic je toliko, kolikor je elementov, torej .
Zapis pomeni, koliko je množic z vsemi elementi. Taka množica je ena sama, to je kar ista množica.
Binomski izrek
Poglejmo, kje nam lahko binomski simbol in Pascalov trikotnik olajšata računanje.
Za kvadrat in kub dvočlenika poznamo formule,
potence višjih redov pa smo do zdaj računali z množenjem
Pri tem opazimo, da je pri vsakem členu vsota eksponentov enaka . Členi so oblike , kjer teče od 0 do . Koeficient pri vsakem členu pa je enak številki, ki ustreza vrednosti binomskega simbola .
Binomski izrek se torej glasi
Koeficienti po vrsti točno ustrezajo vrstici v Pascalovem trikotniku za izbran .
Najprej pogledamo potenco, ta je 6. To pomeni, da pogledamo v Pascalov trikotnik v vrstico in pišemo po vrsti k številkam ustrezne potence a in b, tako da štejemo od 0 do in velja .
Oznake v kombinatoriki
|
|
