Matemaatika lisaülesanne Mitu lk (A4) paberit on vaja, et trükkida välja 40-elemendilise hulga permutatsioonide kõik variandid? 40! = 8.15915283247897734345611269596115894272 × 10^47 ehk 815915283247897734345611269596115894272000000000 Selleks, et saada teada, mitu lehekülge on vaja, tuleb välja arvutada, mitu tähemärki mahub ühele A4 paberile Ääristuseks kasutan Microsoft Wordi poolt pakutud „kitsast“ raamistust – igast äärest jääb vabaks 1,27cm Reavahe on 1.0
VIETE'I TEOREEM ARITMEETILINE JADA kui a = 1, siis an = a1 + (n-1)d x1 + x2 = - b x1 * x2 = c TULETISED (u±v)'=u' ± v' GEOMEETRILINE n1 JADA (uv)' u'v + uv' an = a1q Hääbuv geomeetriline jada [u(v[x])]'=u'(v[x])v'[x] NEWTONI BINOOMVALEM VEKTORID KOMBINATOORIKA Kui A(x1;y1) ja B(x2;y2), siis Permutatsioonide arv Vektor =(x2-x1;y2-y1) Vektori pikkus: Kombinatsioonide arv . Skalaarkorrutis: . Kui kaks vektorid on risti, siis on Variatsioonide arv nende skalaarkorrutis 0. MATEMAATIKA PÕHIKOOLILE valemid PROTSENT JA PROMILL TEHTED ASTMETEGA
Mitu erinevat komplekti ta saab moodustada? Kasutades korrutamisreeglit, saame erinevaid võimalusi 12. 4. Esimese n positiivse täisarvu korrutise ülesmärkimiseks kasutatakse sümbolit n! (n faktoriaal). n! = 1*2*3* ... *(n-1)*n 1! = 1 0! = 1 5. Permutatsioonideks n elemendist nimetatakse n-elemendilise hulga n- elemendilisi ................................?........................................ osahulki ning permutatsioonide arv leitakse valemiga Pn = n! 6. Hiireküla algkooli kehalise kasvatuse õpetaja tahab teada, mitu võimalust on panna erinevasse järjekorda oma neljaliikmelise võistkonna õpilasi 4 ×100 m teatejooksuks. Leia võimaluste arv. P4=4*3*2*1=24 7. Kombinatsioonideks n elemendist k kaupa nimetatakse n-elemendilise hulga k- k elemendilisi osahulki. Kombinatsioonide arv leitakse valemiga C n = n!/[k!*(n-k)!] 8
35 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
oestus. T~oestame teoreemi matemaatilise induktsiooni abil elemen- tide arvu n j¨argi hulgas Nn . Nagu n¨agime n = 1 korral teoreem kehtib. Eespool ¨oeldu p~ohjal ka n = 2 ja n = 3 korral teoreem kehtib, olgugi et matememaatilise induktsiooni l¨abiviimiseks pole seda tarvis teada. Eel- dame, et teoreem kehtib n - 1 korral. Hulga Nn-1 abil saab moodustada (n - 1)! permutatsiooni. Tuleb t~oestada, et hulga Nn abil saab moodus- tada n! permutatsiooni. Jaotame hulga Nn k~oikide permutatsioonide hulga, (1) (2) (n) t¨ahistame Pn abil, tema alamhulkadeks Pn , Pn , . . . , Pn . Alamhulka (i) Pn , kus i Nn , kuulugu sellised permutatsioonid, mille esimene element on i Nn . Selle hulga iga permutatsioon on kujuga i2 3 . . . n , 21 kus (n - 1)-elemendiline permutatsioon 2 3 . . . n on permutatsioon hulga {1, 2, . . . , i - 1, i + 1, . . . , n} elementidest
T˜oestame teoreemi matemaatilise induktsiooni abil elemen- tide arvu n j¨argi hulgas Nn . Nagu n¨agime n = 1 korral teoreem kehtib. Eespool ¨oeldu p˜ohjal ka n = 2 ja n = 3 korral teoreem kehtib, olgugi et matememaatilise induktsiooni l¨abiviimiseks pole seda tarvis teada. Eel- dame, et teoreem kehtib n − 1 korral. Hulga Nn−1 abil saab moodustada (n − 1)! permutatsiooni. Tuleb t˜oestada, et hulga Nn abil saab moodus- tada n! permutatsiooni. Jaotame hulga Nn k˜oikide permutatsioonide hulga, (1) (2) (n) t¨ahistame Pn abil, tema alamhulkadeks Pn , Pn , . . . , Pn . Alamhulka (i) Pn , kus i ∈ Nn , kuulugu sellised permutatsioonid, mille esimene element on i ∈ Nn . Selle hulga iga permutatsioon on kujuga iα2 α3 . . . αn , 21 kus (n − 1)-elemendiline permutatsioon α2 α3 . . . αn on permutatsioon hulga {1, 2, . . . , i − 1, i + 1,
cba nelja elemendi korral võib arutleda nõnda, kui esimesele kohale paigutada element a, siis ülejäänud kolme elemendi omavaheliseks järjestamiseks on 6 võimalust; kui esimesel kohal on element b, siis ülejäänud elemente saab järjestada 6 viisil, samamoodi on see ka siis, kui esimesel kohal on element c või element d. Kokku on nelja elemendi järejestamiseks siis 24 võimalust. Permutatsioonide arvu tähistatakse sümboliga Pn. Seega leidsime, et P2 = 2 = 1 · 2 P3 = 6 = 1·2·3 P4 = 24 = 1·2·3·4 Jätkates samasuguseid arutlusi, jõuame tulemusele, et P5 = 120 = 1·2·3·4·5 P6 = 720 = 1·2·3·4·5·6 Üldkujuline valem: Pn = 1·2·3·...·n Korrutist 1·2·3·...·n tähistatakse matemaatikas sümboliga n! ning nimetatakse faktoriaaliks. Erijuhtumid: 1! = 1 0! = 1 Permutatsioonide arvutamise valemi üldkuju on seega Pn = n! Näiteks 1
siis öeldakse, et on määratud ühine kujutis hulgast V hulka W. L V = M(n × n) LW= f: M(n × n) f: Ad A M(n × n) d 1 2 n |a1 a1 ... a1 | |a21 a22 ... a2n| d = |.....................| = (-1) a11 a22 a33 ... ann permutatsioonid |an1 an2 ... ann| Selgitus: determinandi väärtust arvutav summa on võetud üle kõigi permutatsioonide, millised saab moodustada numbritest 1, 2, 3 ... n ( seega on liidetavaid n! tükki), sümbol summa avaldises tähistab inversioonide koguarvu permutatsioonis 1; 2;....; n. Permutatsioon on teatava hulga kõikidest elementidest moodustatud ning konkreetne järjestus. Pn = n! Öeldakse, et kui väiksem indeks asetseb suurema ees, siis nad moodustavad loomuliku järjestuse, vastasel juhul kui suurem väiksema ees, siis räägitakse, et nad moodustavad inversiooni.
Näide. Kui suur on tõenäosus, et täringut veeretades tuleb paaritu arv silmi? Täringu veeretamisel võib tulla silmade arvuks 1, 2, 3, 4, 5 või 6 silma. Seega on kõikide võimaluste arv 6. Neist paaritud arvud on 1, 3 ja 5. Seega on soodsate võimaluste arv 3. Lahendus. Vastus. Tõenäosus, et täringu veeretamisel tuleb paaritu arv silmi, on 50%. Permutatsioonid on n elemendilise hulga elementidest moodustatud n-elemendilised järjestatud osahulgad. Permutatsioonide arv leitakse valemiga Pn = n! Kirjutist n! loetakse - "n faktoriaalis" ja arvutatakse järgmise reegli järgi: n! = 1 · 2 · 3 ... (n - 1) · n. Jätke meelde, et 0! = 1 ja 1! = 1. Näited: 1) 1! = 1, 3! = 1 · 2 · 3 = 6 ja 5! = 1 · 2 · 3 · 4 · 5 = 120. 2) Neljast tähest (k, a, r, u) on võimalik moodustada tähtede ümberpaigutamise teel 4! = 24 erinevat sõna. 3) 13 õpilasega klassis on võimalik teha 13! = 6227020800 erineva järjestusega õpilaste nimekirja.
Kasutame teoreemis tõestatud valemit, P( ) = 1 P(A1 A2 A3 A4) = 1 0,647 = 0,353. 2 KOMBINATOORIKA 2.1.1.1 Valemid ja näited katsetulemuste arvu loendamiseks Permutatsioonid Katses osaleb k elementi, katse tulemuseks on nende elementide teatav järjestus. Niisuguse katse võimalike tulemuste arvuks on n elemendi kõikvõimalike erinevate järjestuste arv. Erinevaid järjestusi etteantud elementidest nimetatakse permutatsioonideks. Kõikvõimalike permutatsioonide arv k elemendist Pk määratakse valemiga Pk = k! =1 × 2 × 3 × 4 × (k1) × k Näide 1. Maja ette pargitakse igal õhtul 5 autot, kõik autod on erinevat värvi. Leida, mitmel erineval viisil saab autosid järjestada. Lahendus. Tuleb leida erinevate 5elemendiliste permutatsioonide arv. P5= 5! = 1 × 2 × 3 × 4 × 5 = 120 Vastus. Autosid saab järjestada 120 erineval viisil. (Kui iga päev moodustada ainult üks
Mat(n, n) korral XEn = X; EmX = X: 3. Mistahes kolme maatriksi X,Y Mat(p, q) ja Z Mat(q,r ) korral (X±Y )Z = XZ ±YZ: 4. Mistahes kolme maatriksi X Mat(p, q) ja Y , Z Mat(q, r ) korral X(Y±Z) = XY ±XZ: Maatriksite transponeerimise omadused. 1. Mistahes maatriksite X, Y Mat(m, n) korral (X ± Y )T = XT ± Y T : 2. Mistahes a R ja mistahes X Mat korral (aX)T = aXT : 3. Mistahes X Mat(p, q) ja Y Mat(q,r ) korral (XY )T = YTXT : PERMUTATSIOON: Kõigi permutatsioonide hulga tähiseks on P(x1, x2, x3...xn). Hulga n kõigi permutatsioonide hulga tähiseks on Pn või P(1, 2, . . . , n). Permutatsioon Hulga H = {x1, x2, x3...xn}(Näiteks H = n) elementide ümberjärjestust, milles hulga H iga element esineb täpselt 1 kord, nim hulga H permutatsiooniks Loomulik permutatsioon permutatsioon 1,2,3,...,n hulgas Nn Inversioon Öeldakse, et elemendipaar (ai, aj) moodustab inversiooni, kui selles paaris esimene arv ai on suurem kui aj
Permutatsioonid, Õpilane: Tekstülesande Tõenäosus, statistika. kombinatsioonid ja 1) eristab juhuslikku, kindlat ja d. variatsioonid. võimatut sündmust ning selgitab Uurimisülesan Sündmus. sündmuse tõenäosuse mõistet, ne. Sündmuste liigid. liike ja omadusi; Klassikaline 2) selgitab permutatsioonide, tõenäosus. kombinatsioonide ja Suhteline sagedus, variatsioonide tähendust ning statistiline leiab nende arvu; tõenäosus. 3) selgitab sõltuvate ja Geomeetriline sõltumatute sündmuste korrutise tõenäosus. ning välistavate ja Sündmuste liigid: mittevälistavate sündmuste
erinevatest ridadest ja erinevatest veergudest. Tähistades maatriksi A determinandi | A |, võib eelöeldu kirja panna järgmiselt: A |A| = (-1) a1 i a2 j . . . an k , (i, j,...,k) kus (i, j,...,k) on n-elemendiline permutatsioon arvudest 1, 2, . . . ,n ja on inversioonide arv selles permutatsioonis. Permutatsioonid erinevad üksteisest ainult elementide järjekorra poolest ja n-elemendiliste permutatsioonide arv on n-faktoriaal, st neid on n! = 1 2 . . . n tükki. Öeldakse, et kaks arvu k ja l moodustavad permutatsioonis inversiooni, kui suurem arv asetseb väiksema ees. St kui ( . . . k . . . l . . .) ja k > l, siis nad moodustavad inversiooni, vastasel korral aga mitte. NÄITEID 1) TEIST JÄRKU DETERMINANT (n = 2). Teist järku ruutmaatriksi determinant sisaldab 2! = 12 liidetavat, mis on maatriksi kahe elemendi korrutised. Täpsemalt, teist järku determinant on
erinevatest ridadest ja erinevatest veergudest. Tähistades maatriksi A determinandi | A |, võib eelöeldu kirja panna järgmiselt: A |A| = (-1) a1 i a2 j . . . an k , (i, j,...,k) kus (i, j,...,k) on n-elemendiline permutatsioon arvudest 1, 2, . . . ,n ja on inversioonide arv selles permutatsioonis. Permutatsioonid erinevad üksteisest ainult elementide järjekorra poolest ja n-elemendiliste permutatsioonide arv on n-faktoriaal, st neid on n! = 1 2 . . . n tükki. Öeldakse, et kaks arvu k ja l moodustavad permutatsioonis inversiooni, kui suurem arv asetseb väiksema ees. St kui ( . . . k . . . l . . .) ja k > l, siis nad moodustavad inversiooni, vastasel korral aga mitte. NÄITEID 1) TEIST JÄRKU DETERMINANT (n = 2). Teist järku ruutmaatriksi determinant sisaldab 2! = 12 liidetavat, mis on maatriksi kahe elemendi korrutised. Täpsemalt, teist järku determinant on
väljasõiduvõimalus Ämarisse või Laekverre imetoredate radarite juurde) . Aga samas on see ka muidu selline asi, mida on alati tore ka niisama teada. Keegi mäletab veel Alice´it Bob´i ja Trudy´t Paluoja tunnist ? DES algoritm Algoritmi põhistruktuur on toodud ära alumisel joonisel. F plokid tähistavad seal Feisteli funktsioone, punane ring ristiga tavalist XOR tehet. IP on algpermutatsioonide koostamine, FP lõpp- permutatsioonide oma. Antud näites jagatakse alginfo 64 bitistesse blokkidesse. Võtmena kasutatakse 64 bitist jada, millest kasutusse läheb 56 ( 8 bitti on paarsusbitid). Fikseeritud permutasioonid muudavad algsete infobittide asukohti. Peale permutasiooni jagatakse 64 bitine kood kaheks 32 bitiseks osaks. Üks osa läbib Feisteli funktsiooniga plokki ja liidetakse XORiga teisele otsa, ning kogu asi läheb vastupidi käima (vt. joonist). Nõnda käib see 16 korda, kuni tehakse
Permutatsioonid on variatsioonid n elemendist n elemendi kaupa ja esitavad kõikvõimalikke erinevaid järjestusi n elemendist. Nende järjestuste arvu tähistatakse Pn ja arvutatakse Pn = 1 2 3 ... ( n - 1) n = n ! . Kui n ümberjärjestatava elemendi hulgas on erinevaid elemente k, kusjuures nad esinevad vastavalt n1 , n2 , ... , nk korda (kus n1 + n2 + ... + nk = n ), siis erinevate kordumistega permutatsioonide arv on n! Pnn1 , n2 , ... , nk = . n1 ! n2 ! ... nk ! Kombinatsioonid n erinevast elemendist m elemendi kaupa on ühendid, mis erinevad üksteisest vähemalt ühe elemendi poolest (s.t. ainult järjestuse muutus uut kombinatsiooni ei m n
seisu permutatsioon. Samuti on permutatsioon nelja tinasõduri ülesrivistus akna- laual ning kõikvõimalikud laused, mida võib moodustada kolme sõnaga – mulle, meeldib, matemaatika. Põhiliselt huvitab meid siin peatükis permutatsioonide arv, mida objekti korral tähistatakse . Muidugi ei ole siin objektide enda täpne olemus oluline – meil on sama palju reastusi -st tinasõdurist kui -st tõsisest kaitseväelasest. 380 Permutatsioonide arv permutatsioonid ja faktoriaal
Permutatsioonid on variatsioonid n elemendist n elemendi kaupa ja esitavad kõikvõimalikke erinevaid järjestusi n elemendist. Nende järjestuste arvu tähistatakse Pn ja arvutatakse Pn 1 2 3 ... n 1 n n ! . Kui n ümberjärjestatava elemendi hulgas on erinevaid elemente k, kusjuures nad esinevad vastavalt n1 , n2 , ... , nk korda (kus n1 n2 ... nk n ), siis erinevate kordumistega permutatsioonide arv on n! Pnn1 , n2 , ... , nk . n1 ! n2 ! ... nk ! Kombinatsioonid n erinevast elemendist m elemendi kaupa on ühendid, mis erinevad üksteisest vähemalt ühe elemendi poolest (s.t. ainult järjestuse muutus uut kombinatsiooni ei
31 31 + märgiga liikmed märgiga liikmed Tahame üldistada determinandi mõistet igat järku ruutmaatriksitele. Selleks toome esmalt sisse mõningad mõisted. 5. Permutatsioonid. Inversioonid. Kõrgemat järku determinandid. Definitsioon. Arvude 1,2, , n ümberjärjestus, milles iga arv esineb täpselt üks kord, nimetatakse permutatsiooniks. Antud n korral kõigi permutatsioonide hulka tähistame Pn. Näide. Kui n=1, siis on võimalik ainult 1=1! premutatsioon: 1 Arvu n=2 korral on 2=2! permutatsiooni: (1,2) ja (2,1) Arvu n=3 korral on 6=3! permutatsiooni: (1,2,3); (2,3,1); (3,1,2); (2,1,3); (3,2,1); (1,3,2). Teoreem. Permutastoonide arv n elemendist on Pn=n! Tõestus. Permutatsiooni esimese elemendi valimiseks on n võimalust. Teise elemendi valikuks jääb n 1 võimalust. Seega esimese kahe elemendi valikuks on n(n 1) võimalust.
annaabi.ee 
