KOMBINAtoorium

Tunni eesmärgid:

• Uurige, mida kombinatoorika uurib
• Uurige, kuidas kombinatoorika tekkis
• Õppige kombinatoorika valemeid ja õppige neid ülesannete lahendamisel rakendama

Kombinatoorika kui matemaatikaharu sünd on seotud Blaise Pascali ja Pierre Fermat’ hasartmänguteooria töödega.

Blaise Pascal

Pierre Fermat

Suure panuse kombinatoorsete meetodite arendamisse andis G.V. Leibniz, J. Bernoulli ja L. Euler.

G.V. Leibniz

L. Euler.

I. Bernoulli

Lemma. Olgu hulgas A m elementi ja hulgas B n elementi. Siis on kõigi erinevate paaride arv (a,b), kus a\in A,b\in B võrdub mn-ga. Tõestus. Tõepoolest, ühe elemendiga hulgast A saame teha n nii erinevat paari ja kokku on hulgas A m elementi.

Paigutused, permutatsioonid, kombinatsioonid Oletame, et meil on komplekt kolmest elemendist a,b,c. Kuidas saame neist elementidest kaks valida? ab,ac,bc,ba,ca,cb.

Permutatsioonid Korraldame need kõikvõimalikel viisidel ümber (objektide arv jääb muutumatuks, muutub ainult nende järjekord). Saadud kombinatsioone nimetatakse permutatsioonideks ja nende arv on PN = n! =1 · 2 · 3 · ... · ( n-1) n

Sümbol n! nimetatakse faktoriaaliks ja see tähistab kõigi täisarvude korrutist vahemikus 1 kuni n. Definitsiooni järgi arvavad nad seda 0!=1 1!=1 Näide kõigist n=3 objektide (erineva kujuga) permutatsioonidest on pildil. Valemi järgi peaks olema täpselt P3=3!=1⋅2⋅3=6 , ja nii tulebki.

Objektide arvu suurenemisega kasvab permutatsioonide arv väga kiiresti ja nende visuaalne kujutamine muutub keeruliseks. Näiteks 10 üksuse permutatsioonide arv on juba 3628800 (üle 3 miljoni!).

Majutuskohad Olgu seal n erinevat objekti. Valime nende hulgast m objekti ja järjestame need kõikvõimalikel viisidel omavahel ümber (st muutub nii valitud objektide koostis kui ka nende järjekord). Saadud kombinatsioone nimetatakse n objekti paigutusteks m järgi ja nende arv on võrdne Aⁿm =n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)

Definitsioon. Asetades n erineva elemendi komplekti m elemendi kohale (m ≤ n) helistas kombinatsioonid , mis koosnevad antud n elemendist m elemendi võrra ja erinevad kas elementide endi või elementide järjestuse poolest.

Kombinatsioonid Olgu seal n erinevat objekti. Valime nende hulgast kõikvõimalikel viisidel m objekti (see tähendab, et valitud objektide koostis muutub, kuid järjekord pole oluline). Saadud kombinatsioone nimetatakse n objekti kombinatsioonideks m ja nende arv on võrdne Cmn=n!(n−m)!⋅m!

Alloleval pildil näide kõigist n=3 objekti (erineva kujuga) kombinatsioonidest m=2- järgi. Valemi järgi peab olema täpselt C23=3!(3−2)!⋅2!:3!=3. Selge on see, et kombinatsioone on alati vähem kui paigutusi (sest paigutuste puhul on järjekord oluline, aga kombinatsioonide puhul mitte) ja see on täpselt m-des! korda, see tähendab, et seose valem on õige: Amn=Cmn⋅Pm.

1. meetod. Ühes mängus osaleb 2 inimest, seega tuleb välja arvutada, mitmel viisil saad valida 2 inimest 15-st ja järjestus sellistes paarides pole oluline. Valemi abil leiame n erineva elemendi kombinatsioonide arvu (proovid, mis erinevad ainult koostise poolest) m elemendi võrra

n!= 1⋅ 2 ⋅3⋅...⋅ n, kui n=2, m=13.

2. meetod. Esimene mängija mängis 14 mängu (2., 3., 4. ja nii edasi kuni 15. kuupäevani), 2. mängija mängis 13 geimi (3., 4. jne kuni 15. kuupäevani, välistame asjaolu, et juba oli mäng esimesega), 3. mängija - 12 mängu, 4. - 11 mängu, 5 - 10 mängu, 6 - 9 mängu, 7 - 8 mängu, 8 - 7 mängu,

ja 15. juba mängis kõigiga.

Kokku: 14+13+12+11+10+9+8+7+6+5+4+3+2+1=105 mängu

VASTUS. 105 pidu.

Matemaatikaõpetaja Aksenova Svetlana Valerievna

Leningradi oblasti Vsevoložski rajooni Bugrovskaja keskkool

slaid 1

slaid 2

slaid 3

slaid 4

slaid 5

slaid 6

Slaid 7

Slaid 8

Slaid 9

Slaid 10

slaid 11

slaid 12

slaid 13

Slaid 14

slaid 15

slaid 16

Slaid 17

Slaid 18

Slaid 19

Slaid 20

slaid 21

slaid 22

slaid 23

slaid 24

Ettekande teemal "Diskreetne analüüs. Kombinatoorika. Permutatsioonid" saab meie veebisaidilt alla laadida täiesti tasuta. Projekti teema: Informaatika. Värvilised slaidid ja illustratsioonid aitavad teil klassikaaslaste või publiku huvi hoida. Sisu vaatamiseks kasutage pleierit või kui soovite aruande alla laadida, klõpsake pleieri all sobivat teksti. Esitlus sisaldab 24 slaidi.

Esitluse slaidid

slaid 1

Diskreetne analüüs

3. loeng Kombinatoorika. Permutatsioonid

slaid 2

Permutatsioonid

Olgu antud hulk n elementi. Nende elementide järjestust nimetatakse permutatsiooniks. Mõnikord lisatakse "n-st elemendist". Tavaliselt eristatakse üht, põhilist või loomulikku järjestust, mida nimetatakse triviaalseks permutatsiooniks. Hulga A elemendid ei paku meile huvi. Sageli võetakse elementidena täisarve 1 kuni n või 0 kuni n-1. Tähistame n elemendi permutatsioonide hulka Pn-ga ja selle kardinaalsust Pn-ga. Esitame samad kolm küsimust: millega Pn võrdub, kuidas itereerida Pn elemente, kuidas neid ümber nummerdada.

slaid 3

Teoreem permutatsioonide arvu kohta

N elemendi permutatsioonide arv on n! - arvude 1 kuni n korrutis. (n! loeb n-faktorilist) Tõestus. Induktsiooni teel. Kui n=1 on valem ilmselt õige. Olgu see n-1 puhul tõene, tõestame, et see kehtib ka n puhul. Järjestuse esimest elementi saab valida n viisil ja ülejäänud saab valitud esimesele elemendile määrata viisil. Seetõttu on õige valem Pn= Pn-1n. Kui Pn-1=(n-1)!, siis Pn=n!

slaid 4

Permutatsiooni nummerdamine

Permutatsioonide loetlemiseks kaardistame hulga Pn üks-ühele teise hulgaga Tn, mille loendamine on palju lihtsam, ja siis iga elemendi pPn jaoks võtame arvuks selle kujutise arvu Tn-s. . Hulk Tn on mitme arvulise segmendi Tn =(0:(n-1))(0:(n-2) ... (0) otsekorrutis. See tähendab, et iga Tn element on hulk mittenegatiivsetest arvudest i1, i2, …, in-1, in ja iknk.

slaid 5

Ekraan

Võtke permutatsioon ja kirjutage selle kõrvale triviaalne permutatsioon. Esimese indeksina võtame triviaalses permutatsioonis esimese elemendi koha (nullist lugedes). Triviaalse permutatsiooni asemel kirjutagem järelejäänud märkide string. Teise indeksina võta selles reas permutatsiooni teise elemendi koht. Kordame protsessi lõpuni. Ilmselgelt on k-indeks väiksem kui k-nda rea ​​pikkus ja viimane indeks võrdub nulliga. Vaatame seda protsessi näitega.

slaid 6

Näidisnäide

01 On ilmne, et see protsess on pöörduv ja pöördkaardistamine loob algse permutatsiooni indeksite komplektist.

Slaid 7

Komplekti numeratsioon Tn

Kõiki tellitud komplektide otsetooteid võib vaadelda muutuva alusega numbrisüsteemina. Mõelge tagasi esimese loengu sekundite näitele või mõelge mõnele vanale mõõtkavale: 1 jard = 3 jalga, 1 jalg = 12 tolli, 1 toll = 12 rida, 1 rida = 6 punkti. (2, 0, 4, 2, 3) = 2 jardi 0 jalga 4 tolli 2 rida 3 punkti, mitu punkti see on? Peate loendama (seda nimetatakse Horneri skeemiks) (((2  3+0)  12+4)  12+2)  6+3

Slaid 8

Hulga Tn - 2 nummerdamine

Valem #, mis leiab arvu indeksite hulgale i1, i2, ..., in-1, in, eelistame kirjutada rekursiivsete avaldiste kujul #(i1, i2, ..., in) = a (i1, i2, ..., in-1, n-1); a(i1, i2, …, ik,k) = a(i1, i2, …, ik-1,k-1)(n-k+1)+ ik; a(tühi,0) = 0; Selle valemi järgi #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). Meil on a(2,1)=2; a(2,0,2) = 26+0=12; a(2,0,1,3)=125+1=61; a(2,0,1,2,4) =614+2=246; a(2,0,1,2,2,5) =2463+2=740; a(2,0,1,2,2,0,6) =7402+0=1480;

Slaid 9

Indeksikomplektide itereerimine

Eelneva põhjal on permutatsioone lihtne loetleda: peate loetlema kõik indeksite komplektid ja iga komplekti jaoks koostama vastava permutatsiooni. Indeksihulkade loetlemiseks märgime, et tegelikult on iga komplekt arvu kirje spetsiaalses muutuva alusega arvusüsteemis (süsteemi nimetatakse faktoriaalseks). Selles süsteemis on 1 lisamise reeglid peaaegu sama lihtsad kui binaarses: liikudes viimasest bitist, proovige praegusesse bitti lisada 1. Kui võimalik, siis lisage peatumiseks 1. Kui see pole võimalik, kirjutage bitt null ja liikuge järgmise biti juurde.

Slaid 10

Indeksikomplektide itereerimine – 2

Vaatleme järgmist näidet: 7 6 5 4 3 2 1 Need on muutujate alused 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Pange tähele, et 3 4 4 2 2 1 0-s algab iga rida 3 4 4 3 0 0 0 sama mis eelmises, 3 4 4 3 0 1 0 siis tuleb element, rangelt 3 4 4 3 1 0 0 suurem, . . . , ja 3 4 4 3 1 1 0 järgnev ei ole oluline. 3 4 4 3 2 0 0 Seetõttu on iga rida 3 4 4 3 2 1 0 leksikograafiliselt suurem kui eelmise 3 5 0 0 0 0 0 rida. 3 5 0 0 0 1 0

slaid 11

Permutatsioonide teoreemi leksikograafiline loend

Kirjeldatud algoritm loetleb permutatsioonid leksikograafilises kasvavas järjekorras. Tõestus. Piisab, kui näitame, et kui meil on kaks komplekti indekseid I1 ja I2 ning I1 eelneb leksikograafiliselt I2-le, siis permutatsioon (I1) eelneb leksikograafiliselt (I2). Need permutatsioonid moodustatakse järjestikku ja seni, kuni I1 ja I2 ühtivad, sobivad ka nende permutatsioonid. Suurem indeksi väärtus vastab suuremale elemendile.

slaid 12

Otsene algoritm permutatsioonide leksikograafiliseks loendamiseks

Võtame mõne permutatsiooni p ja leksime otse leksikograafiliselt järgmise. Võtame alguse – esimesed k elementi. Selle laiendite hulgas on teada miinimum, milles kõik elemendid on järjestatud kasvavas järjekorras, ja maksimum, milles need on paigutatud kahanevas järjekorras. Näiteks permutatsioonis p =(4, 2, 1, 7, 3, 6, 5) on kõik (4, 2, 1) laiendid vahemikus (3, 5, 6, 7) ja (7, 6, 5, 3). Olemasolev jätk on maksimumist väiksem ja 3. elemendi võib siiski muutmata jätta. Ja ka 4. Ja viiendat tuleb muuta. Selleks tuleb ülejäänud elementide hulgast võtta järjekorras järgmine, panna see 5. kohale ja määrata minimaalne jätk. Selgub (4, 2, 1, 7, 5, 3, 6).

slaid 13

Otsene algoritm permutatsioonide leksikograafiliseks loendamiseks - 2

Kirjutame üles järgmised permutatsioonid. (4, 2, 1, 7, 5, 3, 6) (4, 2, 1, 7, 5, 6, 3) (4, 2, 1, 7, 6, 5, 3) (4, 2, 3, 1, 5, 6, 7) (4, 2, 3, 1, 5, 7, 6) (4, 2, 3, 1, 6, 5, 7) (4, 2, 3, 1, 6) , 7, 5) (4, 2, 3, 1, 7, 5, 6) (4, 2, 3, 1, 7, 6, 5) (4, 2, 3, 5, 1, 6, 7)

Slaid 14

Algoritmi formaalne kirjeldus

Tööolek: permutatsioon p ja tõeväärtusmärk on aktiivne. Algolek: triviaalne permutatsioon kirjutatakse ja isActive = tõene. Standardsamm: kui on Active, tagastage tulemuseks permutatsioon. Otsust liikudes leidke permutatsioonist suurim monotoonselt kahanev sufiks. Olgu k asend enne järelliidet. Pane isActive:= (k > 0). Kui on Active, siis otsi sufiksist väikseim element, mis ületab pk-d, vaheta see pk-ga ja seejärel “keera” sufiks.

slaid 15

Teine permutatsiooni algoritm

Proovime nüüd permutatsioonid loetleda nii, et kaks järjestikust permutatsiooni erineksid üksteisest vähe. Kui vähe? Ühe elementaarse transpositsiooniga, mille käigus vahetatakse kaks külgnevat elementi. Kas see on võimalik? Näitame sellise algoritmi skemaatilist diagrammi, see pakub meile huvi. Kujutage ette n-1 elementaarset "mehhanismi", millest igaüks liigutab oma elementi hulga sees. Igal sammul nihutab mehhanism vasakule või paremale. Suund muutub, kui element jõuab servani. Suuna muutmiseks kulub üks samm, mille käigus astub sammu järgmine mehhanism, mis aga võib ka suunda muuta.

slaid 16

Teine permutatsiooni loendusalgoritm -2

Vaatame näidet. 1 2 3 4 mai mille lõtku 1 2 3 4 5 kelle kord a b c d e c päeva a b e a b c d e c d ba e a b c funktsiooni d e c d b e a b b c da e c d e b a a b c d e a b c d e a b c b d e a a c D a e b c b da e c funktsiooni d e t a m b a d e a a c d e b c c a b D E a a d c e b a a c b d e b d c e b a a c d b Ea d Ca e t a m funktsiooni d b Ea d c e a b

Slaid 17

Permutatsioonide loend. üks

funktsioon ExistsNextPerm(var kCh: täisarv): Boolean; var iV,iP,iVC,iPC: täisarv; beginresult:= Vale; iV jaoks:= nV kuni 2 do if loendage

Slaid 18

Paaripõhiste toodete miinimumsumma probleem

Olgu antud kaks n arvu hulka, näiteks (ak|k1:n) ja (bk|k1:n) . Need arvud jagatakse paarideks (ak,bk) ja arvutatakse nende paariskorrutiste summa k1:n akbk. Saate muuta numeratsiooni (ak) ja (bk). Tuleb valida selline nummerdamine, mille puhul summa on minimaalne. Selles ülesandes saab fikseerida mõned numeratsioonid (ak) ja (bk) ning otsida permutatsiooni , mille puhul on saavutatud summa k1:n akb(k) miinimum. Valime nummerdamise, kui (ak) on kasvavas järjekorras ja (bk) on kahanevas järjekorras.

Slaid 19

Teoreem paariskorrutiste miinimumsumma kohta

Paarikorrutise summa miinimum saavutatakse triviaalse permutatsiooniga. Tõestus. Oletame, et on kaks indeksit k ja r, nii et ak 0, s.o. ar br + ak bk > ar bk + ak br . Meie numeratsioonis (ak) on järjestatud kasvavas järjekorras. Kui (bk) ei ole kasvavas järjekorras, siis on olemas k ja r paar, nagu eespool mainitud. Korraldades selle paari jaoks ümber bk ja br, vähendame summa väärtust. Seega on optimaalses lahenduses (bk) kasvavas järjekorras. Seda lihtsat teoreemi kohtab edaspidi mitu korda.

Slaid 20

Maksimaalselt kasvava alamjada probleem

Antakse n pikkuste arvude jada (ak|k1:n). Tuleb leida selle suurima pikkusega jada, milles arvud (ak) läheksid kasvavas järjekorras. Näiteks jada 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9 korral on maksimaalne alamjada 2, 11, 14, 16 , 17, 25, 37, 41 See probleem on seotud permutatsioonidega, kuna algne jada võib olla permutatsioon. Piirdume selle probleemi lahendamise näitamisega ning algoritmi vormistamise ja põhjendamise jätame publiku hooleks.

slaid 21

Maksimaalse kasvava alamjada leidmine

Jagame enda omad võimalikult ökonoomselt kahanevateks jadadeks (näide muudetud) ridadest ülemises osas, kus see järjekorda ei riku. Võtame alumisest reast numbri 21. Miks see on 8. real? 19 segab seda. Aga 17 segab 19. Ja 16 segab seda. Ja nii edasi. Jada 9, 11, 14, 16, 17, 19, 21 suureneb ja selle pikkus on 7. Iga pikem jada sisaldab kahte arvu ühest reast Dirichlet' printsiibist) ja ei saa suureneda.

slaid 22

Inversioonide minimaalse arvu probleem

Antakse n pikkuste arvude jada (ak|k1:n). Inversioon on mõne selle alamstringi peegelpeegeldus, pidev alamjada, mis sooritatakse paigas.Jada elemendid tuleb järjestada kasvavas järjekorras minimaalse inversioonide arvu jaoks. Näiteks "tahke" permutatsiooni saab niimoodi teisendada (punased tähed on ümber paigutatud, suured on juba paigas)

slaid 23

Eksami küsimused

Permutatsioonid. Nende loendamine ja nummerdamine. Skalaarkorrutise miinimumi probleem. Suurima kasvava alamjada probleem.

slaid 24

1. Kahesuunaline ülemineku permutatsioon  arv 2. Leia permutatsioon, mis on etteantud sammude arvu kaugusel antud permutatsioonist. 3. Permutatsioonide loendamine elementaarsete transpositsioonide abil. 4. Käivitage skalaarkorrutise miinimumi probleemi näide.

Näpunäiteid hea esitluse või projektiaruande koostamiseks

1. Proovige publikut loosse kaasata, looge publikuga suhtlemine suunavate küsimuste, mänguosa abil, ärge kartke nalja teha ja siiralt naeratada (vajadusel).
2. Proovige slaidi oma sõnadega selgitada, lisage täiendavaid huvitavaid fakte, te ei pea lihtsalt slaididelt teavet lugema, publik saab seda ise lugeda.
3. Pole vaja oma projekti slaide tekstiplokkidega üle koormata, rohkem illustratsioone ja minimaalne tekstisisaldus annab paremini teavet ja tõmbab tähelepanu. Slaidil peaks olema ainult põhiteave, ülejäänu on parem publikule suuliselt öelda.
4. Tekst peab olema hästi loetav, vastasel juhul ei näe publik pakutavat teavet, on loost oluliselt häiritud, püüdes vähemalt midagi välja mõelda või kaotab täielikult huvi. Selleks tuleb valida õige font, võttes arvesse, kus ja kuidas esitlus edastatakse, ning valida ka õige tausta ja teksti kombinatsioon.
5. Oluline on ettekanne läbi harjutada, mõelda läbi, kuidas publikut tervitate, mida esimesena ütlete, kuidas ettekande lõpetate. Kõik tuleb kogemusega.
6. Vali õige riietus, sest. Kõne tajumisel mängib suurt rolli ka kõneleja riietus.
7. Proovige rääkida enesekindlalt, ladusalt ja sidusalt.
8. Proovige esinemist nautida, et saaksite olla lõdvestunud ja vähem mures.

Ettekanne "Permutatsioonid" esitab selleteemalise koolitunni õppematerjali. Esitlus sisaldab permutatsioonide definitsiooni, illustreerivaid näiteid selle tehte tähenduse mõistmiseks, permutatsioonidega ülesannete lahendamise matemaatilise aparaadi kirjeldust, ülesannete lahendamise näiteid. Ettekande ülesanne on edastada õppematerjal õpilastele mugavas, arusaadavas vormis, aidata kaasa selle paremale mõistmisele ja meeldejätmisele.

Esitluses kasutatakse spetsiaalseid võtteid, mis aitavad õpetajal uut teemat selgitada. Õppematerjalid on eelstruktureeritud. Animatsiooniefektide abil esitavad nad näiteid ja ülesandeid, rõhutades demonstratsiooni käigus näidete ja ülesannete olulisi omadusi. Olulised mõisted on värviliselt esile tõstetud, et neid oleks lihtsam meeles pidada.

Pärast tunni teema tutvustamist näidatakse õpilastele permutatsioonide määratlust kui lihtsamaid kombinatsioone, mida saab teha teatud elementide komplektist. Tekst on hüüumärgiga esile tõstetud, kuna see on oluline meeles pidada.

Järgmine on näide värvipliiatsi permutatsioonidest, mida saab paigutada erinevas järjekorras. Selleks allkirjastatakse pliiatsid nende värvinime esitähega: S, K, Zh. Animeeritud esitluse abil on selgelt näidatud nende pliiatsite järjestamise võimalused. Ühele slaidile asetatakse esimesena sinised pliiatsid ning nende kõrval on kaks paigutusvõimalust - punane ja kollane, kollane ja punane. Järgmisel slaidil kuvatakse valikud, kuidas panna pliiatsid punase järel – sinine ja kollane, kollane ja sinine. Viimased võimalikud valikud on pärast kollast punast ja sinist, sinist ja punast. Pärast visuaalset demonstratsiooni allkirjastatakse tehtud toimingud kolme elemendi permutatsioonidena. Kolmest elemendist koosneva permutatsiooni täpsem definitsioon on antud eraldi slaidil 7. Mälukastis on esile tõstetud tekst, et nende elementide iga paigutust kindlas järjekorras nimetatakse kolme elemendi permutatsiooniks.

Slaid 8 näitab n elemendi permutatsioonide tähistust - P n . On märgitud, et kolme elemendi permutatsioone käsitleti üksikasjalikult pliiatsite näitel, samas on ilmne, et selliseid permutatsioone tuleb 6. Slaidile on märgitud permutatsioonide arvu matemaatiline kirje: P 3 =6 . Edasi on ekraanil märgitud, et kolme elemendi permutatsioonide arvu leidmiseks on olemas kombinatoorne korrutusreegel.

Järgmisel slaidil jagatakse permutatsiooniprotseduur sammudeks, et saada permutatsioonide arvu leidmise reegel. Näidatakse, et arvutamiseks on vaja esikohale panna ükskõik milline kolmest elemendist. Teise elemendi valimiseks on tal kaks võimalust. Ainus võimalus on valida kolmas element. See tähendab, et 3 elemendi permutatsioonide arv leitakse korrutades 3.2.1=6. Saame võimalike permutatsioonide koguarvu. Sarnaselt permutatsioonivariantide otsimise protsessiga võetakse arvesse n elemendi varieeruvust.

Olgu mingi hulk n elementi. Selle jaoks asetatakse üks n-1 elemendist teisele kohale, üks n-2 elemendist vastavalt kolmandale kohale ja nii edasi. Seega saame tuletada üldreegli n elemendi permutatsioonide arvu leidmiseks: P n =n(n-1)(n-2).….3.2.1.

Slaidil 11 kuvatakse valem P n kujul P n =1.2.3.….(n-2)(n-1)n. Seega võetakse kasutusele faktoriaali mõiste, mille tähistus on näidatud valemi all: n!. Vaadeldakse näiteid mõne arvu faktoriaali leidmiseks: 3!=1.2.3=6, ja ka 6!=1.2.3.4.5.6=720. Samuti on kirjas, et 1!=1. Permutatsioonide arvu leidmise üldreegli tekst n faktoriaalina asub slaidi allosas.

Järgmisena tehakse ettepanek kaaluda mitmeid probleeme permutatsioonide arvu leidmisel. Slaidil 12 tehakse ettepanek lahendada seitse palli seitsmeks lahtriks lagundamise viiside arvu leidmise ülesanne. Näidatakse, et lahenduseks on arvutada 7 elemendi permutatsioonide arv: P 7 =7!=5040.

Slaid 13 käsitleb ülesande lahendust leida neljakohaliste arvude arv, mis koosnevad numbritest 0,1,2,3, samas kui ühes numbris olevaid numbreid ei korrata. Lahendus on esitatud kahes etapis - kõigepealt leitakse 4 elemendi kõigi permutatsioonide arv ja seejärel lahutatakse nendest permutatsioonide arv, milles arvud, mille ees on 0, nii et nullist algavad arvud ei ole neli- numbriline. Seega taandub lahendus P 4 -P 3 =4!-3!=18 arvutamisele. See tähendab, et selliste numbrite moodustamiseks on 18 võimalust.

Viimasel slaidil käsitletakse ülesande lahendust, mis teeb ettepaneku leida viise, kuidas saab paigutada 9 plaati, millest 4 on punased, nii et punased on kõrvuti. Peamine raskus selle probleemi lahendamisel on mõista, et punaseid plaate nendes permutatsioonides tuleb võtta ühena. Seega taandatakse lahendus korrutise P 6 .P 4 =6!.4!=17280 leidmisele.

Ettekanne "Permutatsioonid" on mõeldud visuaalselt saatma õpetaja selgitust teemal "Permutatsioonid". Õppematerjali üksikasjalik, arusaadav esitlus võib kasuks tulla ka kaugõppes ning antud juhul läbimõeldud ülesanded aitavad õpilasel ise lahendusega hakkama saada.

Kombinatoorika alused.

Paigutused, permutatsioonid,

kombinatsioonid.

ulakas ahv

eesel,

kits,

Jah, lampjalgsus Mishka

Hakkas mängima kvartetti

Lõpetage, vennad, lõpetage! -

Ahv karjub, - oota!

Kuidas muusika läheb?

Sa ei istu nii...

Ja nii, ja nii siirdatud - jälle muusika ei lähe hästi.

Siin läks nende analüüs rohkem kui kunagi varem

Ja vaidlusi

Kes ja kuidas istuda...

tean:

• Kombinatoorika kolme kõige olulisema mõiste määratlused:
• n elemendi paigutus m järgi;
• n elemendi kombinatsioonid m võrra;
• n elemendi permutatsioonid;
• põhilised kombinatoorsed valemid

suutma:

• eristada ülesandeid üksteisest "permutatsioonideks", "kombinatsioonideks", "paigutusteks";
• rakendada põhilisi kombinatoorseid valemeid kõige lihtsamate kombinatoorsete ülesannete lahendamisel.

trobikond

Komplekti iseloomustab mõnede homogeensete objektide ühinemine ühtseks tervikuks.

Objekte, mis moodustavad hulga, nimetatakse hulga elementideks.

Kirjutame komplekti, asetades selle elemendid lokkis sulgudesse ( a, b, c, … , e, f}.

Komplektis ei oma elementide järjekord tähtsust, seega ( a, b} = {b, a}.

Kutsutakse hulka, mis ei sisalda ühtegi elementi tühi komplekt ja seda tähistatakse sümboliga ø.

trobikond

Kui komplekti iga element A on hulga B element, siis ütleme, et hulk A on komplekti alamhulk V.

Trobikond ( a, b) on hulga ( a, b, c, … , e, f}.

Tähistatakse

Loetlege komplekti alamhulga võimalikud valikud ( 3 , 4 , 5 , 7, 9 }.

Kombinatoorika on matemaatika haru, mis uurib küsimusi selle kohta, kui palju erinevaid kombinatsioone teatud tingimustel saab teha antud hulka kuuluvatest elementidest.

Kombinatoorika on oluline matemaatika haru, mis uurib fikseeritud hulga elementide paigutuse, järjestamise, valiku ja jaotamise mustreid.

SUMMAERIMISREEGEL

Kui kaks teineteist välistavat tegevust saab sooritada vastavalt k ja m viisil, siis saab sooritada ühe neist toimingutest k+m viise.

Näide nr 1

Linnast A linna B pääseb 12 rongi, 3 lennuki, 23 bussiga. Mitu teed pidi saab linnast A linna B?

Lahendus

Näide nr 2

Karbis on n värvilist palli. Võtke juhuslikult üks pall välja. Kui mitmel viisil saab seda teha?

Lahendus. kindlasti, n viise.

Nüüd on need n palli jagatud kahte kasti: Esimeses m pallid, teises k. Võtke suvalisest karbist välja üks pall. Kui mitmel erineval viisil saab seda teha?

Lahendus.

Palli saab tõmmata esimesest kastist m mitmel viisil, alates teisest k mitmel viisil, kogu N = m + k viise.

TOOTEREEGEL

Olgu kaks üksteise järel sooritatud toimingut võimalik teostada vastavalt k ja m viise Siis saab mõlemat teha k ∙ m viise.

Näide nr 3

Turniiril osaleb 8 hokimeeskonda. Mitu võimalust on esimese, teise ja kolmanda koha jagamiseks?

Lahendus

Näide nr 4

Mitu kahekohalist arvu saab kirjutada kümnendsüsteemis?

Lahendus. Kuna arv on kahekohaline, on kümnete arv ( m) võib võtta ühe üheksast väärtusest: 1,2,3,4,5,6,7,8,9. Ühikute arv ( k) võib võtta samad väärtused ja võib lisaks olla võrdne nulliga. Sellest järeldub m= 9 ja k= 10. Kokku saame kahekohalised arvud

N= m · k= 9 10 =90.

Näide nr 5

Õpilasrühmas on 14 tüdrukut ja 6 poissi. Mitmel viisil saab valida kahte samast soost õpilast erinevate ülesannete täitmiseks?

Lahendus. Kahe tüdruku korrutusreegli järgi saab valida 14 13 = 182 viisi ja kahe poisi 6 5 = 30 viisi. Valida tuleks kaks samast soost õpilast: kaks üliõpilast või naisüliõpilast. Selliste valikute lisamise reegli kohaselt

N = 182 + 30 = 212.

Ühenduse tüübid

Elementide komplekte nimetatakse ühendid.

Ühendusi on kolme tüüpi:

• permutatsioonid alates n elemendid;
• majutus alates n elemendid poolt m;
• kombinatsioonid n elemendid poolt m (m < n).

Definitsioon: permutatsioon alates n elemendid on mis tahes järjestatud komplekt n elemendid.

Teisisõnu, see on selline komplekt, mille puhul näidatakse, milline element on esimesel kohal, milline teisel, milline kolmandal, ..., milline on n-ndal kohal.

PERMUTATSIOONID

Permutatsioonid on sellised ühendused n elemendid antud elementidest, mis erinevad üksteisest elementide järjestuse poolest.

N elemendi permutatsioonide arv on tähistatud Pn-ga.

Рn = n · ( n- üks) · ( n– 2) · … · 2 · 1 = n!

Definitsioon:

Lase n- naturaalarv. Üle n! (loe "en faktoriaal") tähistab arvu, mis võrdub kõigi naturaalarvude korrutisega 1 alates kuni n:

n! = 1 2 3 ... n.

Kui n= 0, definitsiooni järgi eeldatakse: 0! = 1.

FAKTORIAALNE

Näide nr 6

Leiame järgmiste avaldiste väärtused: 1! 2! 3!

Näide nr 7

Mis on võrdne

a) R 5 ;

b) R 3.

Näide nr 8

Lihtsustama

b) 12! 13 14

v) κ ! · ( κ + 1)

Näide nr 9

Mitmel viisil saab kaheksale jooksulindile asetada 8 finaalsõidu osalejat?

Lahendus.

R 8=8! = 8 7 6 5 4 3 2 1 = 40320

MAJUTUS

Definitsioon. Majutus alates n elementi m järgi kutsutakse iga tellitud komplekt m elemendid, mis koosnevad elementidest n elemendi komplekt.

Paigutuste arv alates m elemendid poolt n eest seisma:

arvutatakse valemiga:

Näide nr 9

11. klassi õpilased õpivad 9 ainet. Ühe päeva treeningute ajakavasse saab panna 4 erinevat ainet. Kui palju erinevaid viise on päeva planeerimiseks?

Lahendus.

Meil on 9-elemendiline komplekt, mille elementideks on õppeained. Ajakava koostamisel valime 4-elemendilise alamhulga (tundide) ja määrame selles järjestuse. Selliste viiside arv on võrdne paigutuste arvuga üheksast neljaga ( m = 9, n = 4) see on A 94:

Näide nr 10

Mitmel viisil saab 24 õpilasega klassist valida prefekti ja abiprefekti?

Lahendus.

Meil on 24-elemendiline komplekt, mille elementideks on klassi õpilased. Juhataja ja abijuhataja valimisel valime 2-elemendilise alamhulga (õpilase) ja kehtestame selles korra. Selliste viiside arv võrdub paigutuste arvuga üheksast neljaga ( m = 24, n = 2), see on A 242:

KOMBINATSIOONID

Definitsioon. Kombinatsioon ilma kordusteta alates n elemendid poolt m- kutsus ükskõik milliseks m elementaarne alamhulk n-elementide komplekt

Tähistatakse n elemendi kombinatsioonide arvu m-ga

ja arvutatakse järgmise valemiga:

Näide nr 11

Mitmel viisil saab 24 õpilasega klassist valida kaks saatjat?

Lahendus.

n =24, m=2

KOMBINATSIOONID

MAJUTUS

PERMUTATSIOONID

Рn = n!

Määrake, millist tüüpi ühendustele ülesanne kuulub.

1. Kui mitmel viisil on võimalik ajastada ühte koolipäeva 5 erinevast õppetunnist?

2. 9B klassis õpib 12 õpilast. Mitmel viisil saab matemaatikaolümpiaadil osalemiseks moodustada 4-liikmelise võistkonna?

Kas elementide järjekorda ühenduses arvestatakse?

Kas kõik elemendid on ühenduses?

Järeldus: permutatsioon

Kas elementide järjekorda ühenduses arvestatakse?

Kas kõik elemendid on ühenduses?

(see küsimus ei vaja vastust)

Järeldus: kombinatsioonid

3. Mitu erinevat kahekohalist arvu on, milles saab kasutada arve 1, 2, 3, 4, 5, 6, kui numbrid peavad olema erinevad?

Kas elementide järjekorda ühenduses arvestatakse?

Kas kõik elemendid on ühenduses?

Järeldus: paigutus

ulakas ahv

Jah, lampjalgsus Mishka

Hakkas mängima kvartetti

Lõpetage, vennad, lõpetage! -

Ahv karjub, - oota!

Kuidas muusika läheb?

Sa ei istu nii...

Ja nii, ja nii siirdatud - jälle muusika ei lähe hästi.

Siin läks nende analüüs rohkem kui kunagi varem

Kes ja kuidas istuda...

Mitu erinevat muusikute seadet on võimalik?

Lahendus.

Kas elementide järjekorda ühenduses arvestatakse?

Kas kõik elemendid on ühenduses?

Järeldus: permutatsioon

Рn = n! =n · ( n- üks) · ( n– 2) · … · 2 · 1

P4 = 4! = 4 3 2 1 = 24

“Varem või hiljem leiab iga õige matemaatiline idee selles või teises äris rakendust”?

permutatsioonid

majutus

kombinatsioon

Probleemide lahendamise tulemused

KODUTÖÖ

Õppige abstrakti ja valemeid.

S. 321 nr 1062

Permutatsioonid on kombinatsioonid, mis koosnevad samadest elementidest ja erinevad oma järjestuse poolest. Elementide kõigi võimalike permutatsioonide arv on tähistatud P n-ga ja seda saab arvutada valemiga: Permutatsioonivalem: P n =n! Permutatsiooni käigus jääb objektide arv muutumatuks, muutub ainult nende järjekord.Objektide arvu kasvades kasvab permutatsioonide arv väga kiiresti ja nende visuaalne kujutamine muutub keeruliseks.

Ülesanne 1. Turniiril osaleb seitse võistkonda. Kui mitu võimalust on nende vahel kohtade jaotamiseks? Р 7 =7!=1*2*3*4*5*6*7=5040 Vastus: 5040 Ülesanne 2. Mitmel viisil saab ümarlaua taha istuda 10 inimest? P 10 = 10! = = 1*2*3*4*5*6*7*8*9*10 = Vastus:

Olgu seal n erinevat objekti. Valime nende hulgast m objekti ja paigutame need kõikvõimalikel viisidel omavahel ümber. Saadud kombinatsioone nimetatakse n objekti paigutusteks m võrra ja nende arv on võrdne: Paigutamisel muutub nii valitud objektide koosseis kui ka nende järjekord. Paigutuse valem:

Ülesanne: Mitmel viisil saab jagada viie inimese vahel kolm vautšerit ühe sanatooriumi kohta? Kuna vautšerid antakse ühele sanatooriumile, erinevad jagamisvõimalused üksteisest vähemalt ühe inimese kohta. Seetõttu levitamisviiside arv Vastus: 10 võimalust.

Ülesanne: Töökojas töötab 12 inimest: 5 naist ja 7 meest. Kui mitmel viisil saab moodustada 7-liikmelise meeskonna nii, et selles on 3 naist? Viiest naisest tuleb välja valida kolm, seega valikumeetodite arv. Kuna on vaja valida neli meest seitsmest, siis meeste valimise võimaluste arv Vastus: 350