Kordumistega ühendid


Kordumistega kombinatsioonid

Kombinatsioonid niisuguse põhihulga korral, mille n erinevast elemendist võib igaühte kasutada suvalises arvus eksemplarides. Kordumistega kombinatsioonide, s.t m-elemendilise osahulkade arv avaldub kujul (tavaliste kombinatsioonide arvu tähist C_{n}^{m} kasutades) kujul

C_{n+m-1}^{m}=\frac{(n+m-1)!}{m!(n-1)!}

Näiteks kui müügil on vaid punaseid, siniseid ning kollaseid pliiatseid (s.t. n=3), siis nelja pliiatsi (s.t. m=4) ostmiseks leidub C_{3+4-1}^{4}=15 erinevat võimalust, nimelt ost saab olla üks pliiatsihulkadest : {pppp}, {ppps},{pppk},{ppss},{ppsk},{ppkk},{psss},{pssk},{pskk},{pkkk},{ssss},{sssk},{sskk},{skkk},{kkkk}, kus p,s või k tähistavad vastavalt punast sinist või kollast pliiatsit.

Loe edasi 

Kordumistega permutatsioonid

Permutatsioonid niisuguse põhihulga korral, mille n elemendi seas on vaid k erinevat: hulga esimest elementi m_1 eksemplari, teist m_2 eksemplari jne., kusjuures m_1+m_2+\ldots+m_k=n

Kordumistega permutatsioonide (s.t. niisuguse n-elemendilise hulga erinevate järjestamisvõimaluste) arv P_{n}^{m_1,m_2,\ldots,m_k} avaldub faktoriaalide kaudu kujul

P_{n}^{m_1,m_2,\ldots,m_k}=\frac{n!}{m_{1}!m_{2}! \ldots m_{k}!}

Näiteks numbreid 1,1,3,3,3 ning ainult neid kasutades (s.t n=5, k=2, m_1=2, m_2=3) saab moodustada P_{5}^{2,3}=10 erinevat viiekohalist naturaalarvu:

11333, 13133, 13313, 13331, 31133, 31313, 31331, 33113, 33131, 33311.

Kordumistega variatsioonid

Variatsioonid niisuguse põhihulga korral, mille n erinevast elemendist võib igaühte kasutada suvalises arvus eksemplarides. Kordumistega variatsioonide (s.t m-elemendiliste järjestatud osahulkade) arv W_{n}^m avaldub kujul:

W_{n}^m=n^m

Näiteks leidub kokku 90 kahekohalist naturaalarvu, sest numbreid 0,1, … , 9 korduvalt kasutades saame moodustada W_{10}^2=100 kaheelemendilist kordumistega variatsiooni, W_{10}^1 nulliga algavat ( ja seega ühekohalist) tuleb neist aga kõrvale jätta.

ÜLESANDED

Millised on kõikvõimalikud silmade kombinatsioonid täringu kahel järjestikkusel viskel?

Lahendus lihtne. Esimesel võivad tulla 1…6, teisel võivad tulla 1..6 e. W_{6}^2=6^2=36 või ka 6 \cdot 6 =36

Rahakapi luku avamisel tuleb viiel kettal seisvatest numbritest 1,2,..,9,0 moodustada šifriks teatav 5-kohaline arv. Kui kaua kulub šifri unustamise korral maksimaalselt aega luku avamiseks, kui ühe šifri järeleproovimiseks kulub 10 sekundit.

Esmalt arvutame kõikvõimalikud variandid selleks koodiks. Kuna igale kohale võivad tulla arvud 0…9-ni, siis on neid arve 10. Järelikult on kokku W_{10}^5=10^5 võimalust. Kui iga proovimiseks kulub 10 sekundit, kulub aega kokku 10^6 e. miljon sekundit, mis on ~16667 tundi.

Mitu viietähelist “sõna” saab moodustada tähtedest “a” ja “b”

Jällegi tegu kordumistega variatsioonidega. Viis tühja auku ja igasse auku võib minna kas a või b ehk  W_{5}^2=2^5=32

Moodustage kõikvõimalikud 4-tähelised “sõnad” tähtedest “t”, “a”, “l”,”v” (iga tähte vaid kord kasutades).

Siin on tegu tavalise tähtede ümberpaigutamisega. Siin võib märgata, et hulk ei lähe suuremaks. meil on neli tähte ja sõnad peavad olema samuti neljatähelised. Kindel kordumisteta permutatsioonide teema e. P_4=4!=24

Moodustage kõikvõimalikud 4-tähelised “sõnad” tähtedest “t”, “a”, “t”, “a”

Põhimõtteliselt sama ülesanne ainult tähed korduvad. Kasutame kordumistega permutatsioone. P_{4}^{2,2}=\frac{4!}{2!2!}=6

Mitu erinevat kordumistega permutatsiooni  saab moodustada elementidest a,a,b,b,b?

Kasutame definitsiooni : P_{5}^{2,3}=\frac{5!}{2!3!}=10

Mitu erinevat sõna saab koostada sõna MISSISIPI tähtedest (kõik tähed tuleb ära kasutada)?

Sama teema. Jälle kordumistega permutatsioonid. M=1, I=4, S=3, P=1 P_{9}^{1,1,3,4}=\frac{9!}{1!1!3!4!}=2520

Tsehhis töötab masin, millel valmistatakse kahte eri tüüpi detaile. Kummagi tüübi valmistamiseks kulub 5 minutit. Ühe tunni jooksul tuleb valmistada 7 esimest ja 5 teist tüüpi detaili. Kui mitme erineva programmi järgi võib masin selleks töötada ( oletame, et masina ümberlülitamine aega ei nõua)

Tähistame esimese detaili tähega A ja teise B. Esimest on vaja 7 tükki ja teist 5 tükki. Sellest aja nõudest ma ei saa tegelikult aru. Võib olla mingi kitsendus juhuks, kui keggi hakkab mõtlema, et äkki jääb aega üle või midagist. Igatahes üks võimalikest programmidest on näiteks ABABAAAABABB. Ülejäänud saab kätte, kui tähti siin reas igatepidi ümber vahetada. Kuna nad korduvad, siis on tegu kordumistega permutatsioonidega e. P_{12}^{7,5}=\frac{12!}{7!5!}=792

Mitmel erineval viisil saab osta 7 õlut hulgast “Saku hele”, “Saku tume”, “Saku Ice” ja “Saku originaal”?

Kõigepealt on vaja mõelda, millega meil siin üldse tegu on. Kas siin on mingil moel järjekord oluline? Ei ole. Pole vahet, mis pudeli sa esimesena ostad või mis margist. Tähtis on seitsme pudeli koosseis. Seda ülesannet saab lahendada nii Kordumistega permutatsioonide kui kordumistega kombinatsioonide abil.

Uno varianto Teeme esiteks permutatsioonidega. Tähistame õllepudelid nullidega ja ütleme, et kui ühest margist on ära ostetud, pannakse nende vahele mingi “pulk” mille tähistame ühega. Meenutame järjekorda:

“Saku hele”, “Saku tume”, “Saku Ice” ja “Saku originaal”

Nüüd koostame ühe nullidest ja ühtedest koostatud jada:

0100100010

Sellisele jadale vastaks variant, kus ostetakse 1 Hele, 2 tumedat, 3 Ice ja 1 originaal. Neid jadasid võib ikka päris palju orgunnida. Kui palju, seda peamegi leidma. Kui üks asuks alguses või lõpus, tähendaks see seda, et heledat või originaali ei ostetud üldse. Kui kaks ühte oleks vahepeal koos, tähendaks see, et ühte vahepealset marki ei ostetud. Seega peaks kõik variandid kaetud olema. kasutades kordumistega permutatsioone. P_{10}^{7,3}=\frac{10!}{7!3!}=120

Secundo varianto Kordumistega kombinatsioonid. Mind ennast alguses häiris, et elementide hulk on väiksem kui valitav. Kordumisteta kombinatsioonidel saad teha maksimaalselt nii suure hulga, kui palju sul elemente on. Kordumisteta kombinatsioonidel on isegi nõue, et m<n ehk moodustatavad osahulgad ei saa olla suuremad kui koguhulk. Kui m>n (praegune olukord), siis on tegu juba kordumistega.  Kuid kui mõelda kombinatsioonide sisule, siis tegelikult võetakse ainult sisult erinevad variandid sisse ja järjestuselt erinevad vistakse välja. Kasutades variatsioone, loeks see ka millise margi me esimesena võtsime. Rõhutan, et siin ei ole see oluline. Loeb ainult koosseis.

Seega : C_{4+7-1}^{7}=\frac{(4+7-1)!}{7!(4-1)!}=\frac{10!}{7!3!}=120

Leida kõikvõimalikud täringusilmade kombinatsioonid, kui kaht täringut korraga visata.

Koht, kus peab tunnetama, mida tahetakse. Sarnane sõnastus esimesega aga nüüd mõeldakse ka tegelikult kombinatsioone. Nüüd visatakse kahte täringut korraga ja ei saa teha vahet, kumb on esimene kumb teine. Esimesel juhul tehti vise ära ja siis visati täringut teist korda, eh saime järjestada visked.

Seega: m=2 (täringuid) , n=6 (erinavid silmi) C_{6+2-1}^{2}=\frac{(6+2-1)!}{2!(6-1)!}=\frac{7!}{2!5!}=21

Mitu võimalust on poiste ja tüdrukute arvu jaoks viielapselises peres?

Käib nagu see õllepudeli ülesanne Olgu lapsed kodeeritud arvuga null ja poiste ning tüdrukute vahe arvuga 1. Siis variandile 010000 vastaks variant 1 poisist ja 4 tüdrukust. Kui üks oleks alguses, poleks ühtegi poissi ja kui üks oleks lõpus, poleks tüdrukuid. Seega P_{6}^{1,5}=\frac{6!}{1!5!}=6

Või võib ka kasutada kordumistega kombinatsioone, kus n=2 ja m=5,

C_{2+5-1}^{5}=\frac{(2+5-1)!}{5!(2-1)!}=\frac{6!}{5!}=6

Mitu erinevat 3 saiaksesest koosnevat einet saab kohvikust tellida, kui müügil on 11 erinevat sorti saiakest?

Järjestus pole oluline. Koosluses võivad saiad korduda. Seega kordumistega kombinatsioonid e. n=11 (saiakese liigid) m=3 ( ostetud kogus).

C_{11+3-1}^{3}=\frac{(11+3-1)!}{3!(11-1)!}=\frac{13!}{3!10!}=286

Mitmel erineval viisil on võimalik panna 6 erinevat münti 3 taskusse?

Mina kitsendasin lolli peaga seda kunagi nii, et igas taskus võib olla ainult üks münt. siit õpetussõnad. Olge mõtlemisel vaba ja ärge seadke ise mingeid kitsendusi, mis ei tule loogilise aruteluga välja.

Kujutage ette, et te olete münt, siis on teil valida kolme tasku vahel. sama valik on ka teisel mündil ja kolmandal ja neljandal … ja isegi viiendal (mis sest, et taskus võib keegi ees olla), keegi ei keela teil teise mündiga taskut jagada. Seega on võimalusi

3 \cdot 3\cdot 3\cdot 3 \cdot 3 \cdot 3 =3^6=W_{3}^6=729

Naum Vilenkin
Kombinatoorika

Vene keelest tõlkinud Jaak Hion

347-leheküljeline tavaformaadis ja kõvas köites raamat

Valgus 1975

Põhimõtteliselt on igal pool koolides ringlevad ülesanded siit pärit. Kui keegi on huvitatud, võib hankida endale. Kui oma kõvakettale ligi saan, panen ka selle raamatu põhjal koostatud lühikonspekti üles.

Kasutatud materjal:

Abel, E., Abel, M., Kaasik, Ü. (2006) Koolimatemaatika entsüklopeedia. 3. täiendatud trükk. Tartu: Ilmamaa

—————————————————-

Meta: kombinatoorika, kordumistega kombinatsioonid, kordumistega variatsioonid, kordumistega permutatsioonid, kordumistega ühendid

Lisa kommentaar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Muuda )

Twitter picture

You are commenting using your Twitter account. Log Out / Muuda )

Facebook photo

You are commenting using your Facebook account. Log Out / Muuda )

Google+ photo

You are commenting using your Google+ account. Log Out / Muuda )

Connecting to %s