KOMBINATORIKA

Ciele lekcie:

• Zistite, čo študuje kombinatorika
• Zistite, ako kombinatorika vznikla
• Naučte sa vzorce kombinatoriky a naučte sa ich aplikovať pri riešení problémov

Zrod kombinatoriky ako odvetvia matematiky je spojený s prácami Blaise Pascala a Pierra Fermata o teórii hazardných hier.

Blaise Pascal

Pierre Fermat

Veľký prínos k rozvoju kombinatorických metód priniesol G.V. Leibniz, J. Bernoulli a L. Euler.

G.V. Leibniz

L. Euler.

I. Bernoulli

Lemma. Nech je v množine A m prvkov a v množine B n prvkov. Potom počet všetkých odlišných párov (a,b), kde a\in A,b\v B sa bude rovnať mn. Dôkaz. S jedným prvkom z množiny A dokážeme vytvoriť n takýchto rôznych párov a celkovo je v množine A m prvkov.

Umiestnenia, permutácie, kombinácie Povedzme, že máme množinu troch prvkov a,b,c. Akými spôsobmi môžeme vybrať dva z týchto prvkov? ab, ac, bc, ba, ca, cb.

Permutácie Preusporiadame ich všetkými možnými spôsobmi (počet objektov zostáva nezmenený, mení sa len ich poradie). Výsledné kombinácie sa nazývajú permutácie a ich počet je PN = n! =1 · 2 · 3 · ... · ( n-1) n

Symbol n! sa nazýva faktoriál a označuje súčin všetkých celých čísel od 1 do n. Podľa definície to považujú 0!=1 1!=1 Príklad všetkých permutácií n=3 objektov (rôzne tvary) je na obrázku. Podľa vzorca by malo byť presne P3=3!=1⋅2⋅3=6 , a tak to aj dopadne.

S nárastom počtu objektov počet permutácií rastie veľmi rýchlo a je ťažké ich vizuálne zobraziť. Napríklad počet permutácií 10 položiek je už 3628800 (viac ako 3 milióny!).

Ubytovanie Nech je n rôznych predmetov. Vyberieme z nich m objektov a preusporiadame ich medzi sebou všetkými možnými spôsobmi (teda zmení sa ako kompozícia vybraných objektov, tak aj ich poradie). Výsledné kombinácie sa nazývajú umiestnenia n objektov po m a ich počet sa rovná Aⁿm =n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)

Definícia. Umiestnením množiny n rôznych prvkov na m prvkov (m ≤ n) volal kombinácie , ktoré sú zložené z daných n prvkov po m prvkoch a líšia sa buď samotnými prvkami, alebo poradím prvkov.

Kombinácie Nech je n rôznych predmetov. Všetkými možnými spôsobmi z nich vyberieme m objektov (teda zloženie vybraných objektov sa mení, ale poradie nie je dôležité). Výsledné kombinácie sa nazývajú kombinácie n objektov podľa m a ich počet sa rovná Cmn=n!(n−m)!⋅m!

Príklad všetkých kombinácií n=3 predmetov (rôznych tvarov) podľa m=2- na obrázku nižšie. Podľa vzorca musí byť presne C23=3!(3−2)!⋅2!:3!=3. Je jasné, že kombinácií je vždy menej ako umiestnení (pretože poradie je dôležité pre umiestnenie, ale nie pre kombinácie) a je presne v m! krát, to znamená, že vzorec vzťahu je správny: Amn=Cmn⋅Pm.

Metóda 1. V jednej hre sa zúčastňujú 2 ľudia, preto si musíte spočítať, koľkými spôsobmi môžete vybrať 2 ľudí z 15, pričom poradie v takýchto pároch nie je dôležité. Vzorec používame na zistenie počtu kombinácií (vzorky, ktoré sa líšia iba zložením) n rôznych prvkov na m prvkov

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

Metóda 2. Prvý hráč odohral 14 hier (s 2., 3., 4. atď. do 15.), 2. hráč odohral 13 hier (3., 4. atď. do 15., vylučujeme, že už tam bol hra s prvým), 3. hráč - 12 hier, 4. - 11 hier, 5 - 10 hier, 6 - 9 hier, 7 - 8 hier, 8 - 7 hier,

a 15. už hrali s každým.

Celkom: 14+13+12+11+10+9+8+7+6+5+4+3+2+1=105 hier

ODPOVEĎ. 105 strán.

Učiteľka matematiky Aksenová Svetlana Valerievna

Bugrovskaja stredná škola okresu Vsevolozhsky v Leningradskej oblasti

snímka 1

snímka 2

snímka 3

snímka 4

snímka 5

snímka 6

Snímka 7

Snímka 8

Snímka 9

Snímka 10

snímka 11

snímka 12

snímka 13

Snímka 14

snímka 15

snímka 16

Snímka 17

Snímka 18

Snímka 19

Snímka 20

snímka 21

snímka 22

snímka 23

snímka 24

Prezentáciu na tému "Diskrétna analýza. Kombinatorika. Permutácie" si môžete stiahnuť úplne zadarmo na našej webovej stránke. Predmet projektu: Informatika. Farebné diapozitívy a ilustrácie vám pomôžu udržať záujem vašich spolužiakov alebo publika. Na zobrazenie obsahu použite prehrávač, alebo ak si chcete stiahnuť prehľad, kliknite na príslušný text pod prehrávačom. Prezentácia obsahuje 24 snímok.

Prezentačné snímky

snímka 1

Diskrétna analýza

3. prednáška Kombinatorika. Permutácie

snímka 2

Permutácie

Nech je daná množina n prvkov. Usporiadanie týchto prvkov sa nazýva permutácia. Niekedy sa pridáva „z n prvkov“. Zvyčajne sa rozlišuje jedno, základné alebo prirodzené usporiadanie, ktoré sa nazýva triviálna permutácia. Prvky množiny A nás nezaujímajú. Často sa ako prvky berú celé čísla od 1 do n alebo od 0 do n-1. Množinu permutácií n prvkov označíme Pn a jej mohutnosť označíme Pn. Položme si rovnaké tri otázky: čomu sa rovná Pn, ako iterovať prvky Pn, ako ich prečíslovať.

snímka 3

Veta o počte permutácií

Počet permutácií n prvkov je n! - súčin čísel od 1 do n. (n! číta n-faktoriál) Dôkaz. Indukciou. Pre n=1 je vzorec zjavne správny. Nech to platí pre n-1, dokážeme, že to platí aj pre n. Prvý prvok zoradenia možno vybrať n spôsobmi a zvyšok možno priradiť k vybranému prvému prvku rôznymi spôsobmi. Preto je vzorec Pn= Pn-1n správny. Ak Pn-1=(n-1)!, potom Pn=n!

snímka 4

Permutačné číslovanie

Na vyčíslenie permutácií namapujeme množinu Pn jedna k jednej na inú množinu Tn, na ktorej bude oveľa jednoduchšie enumerovať, a potom pre ľubovoľný prvok pPn vezmeme číslo jeho obrazu v Tn ako jeho číslo. . Množina Tn je priamym súčinom niekoľkých číselných segmentov Tn =(0:(n-1))(0:(n-2) ... (0). To znamená, že každý prvok Tn je množina nezáporných čísel i1, i2, …, in-1, in a iknk.

snímka 5

Displej

Vezmite permutáciu a zapíšte si triviálnu permutáciu vedľa nej. Ako prvý index zaujmeme miesto prvého prvku (počítajúc od nuly) v triviálnej permutácii. Namiesto triviálnej permutácie napíšme reťazec zvyšných znakov. Ako druhý index nahraďte druhý prvok permutácie v tomto riadku. Postup zopakujeme až do konca. Je zrejmé, že k-tý index bude menší ako dĺžka k-tého riadku a posledný index sa bude rovnať nule. Pozrime sa na tento proces na príklade.

snímka 6

Zobraziť príklad

0 1 2 3 4 5 6 Index cadfgbeabcdefg 2 2 adfgbeabdefg 0 2 0 dfgbebdefg 1 2 0 1 fgbebefg 2 2 0 1 2 gbebeg 2 2 0 1 2 2 be 1 e 2 0 2 0 2 0 2 Je zrejmé, že tento proces je reverzibilný a inverzné mapovanie vytvorí počiatočnú permutáciu z množiny indexov.

Snímka 7

Číslovanie súpravy Tn

Na akýkoľvek priamy súčin objednaných súprav možno nazerať ako na číselnú sústavu s variabilným základom. Zamyslite sa nad sekundovým príkladom z prvej prednášky alebo zvážte starú škálu veľkostí: 1 yard = 3 stopy, 1 stopa = 12 palcov, 1 palec = 12 riadkov, 1 riadok = 6 bodov. (2, 0, 4, 2, 3) = 2 yardy 0 stôp 4 palce 2 čiary 3 body, koľko je to bodov? Musíte počítať (toto sa nazýva Hornerova schéma) (((2  3+0)  12+4)  12+2)  6+3

Snímka 8

Číslovanie súpravy Tn - 2

Vzorec #, ktorý nájde číslo pre množinu indexov i1, i2, ..., in-1, in, radšej píšeme v tvare rekurzívnych výrazov #(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(prázdne,0) = 0; Podľa tohto vzorca #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). Máme 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;

Snímka 9

Iterácia cez množiny indexov

Na základe vyššie uvedeného je ľahké vymenovať permutácie: musíte spočítať všetky sady indexov a pre každú sadu zostaviť zodpovedajúcu permutáciu. Na vymenovanie množín indexov si všimneme, že v skutočnosti je každá množina záznamom čísla v špeciálnej číselnej sústave s premenlivým základom (systém sa nazýva faktoriál). Pravidlá pre sčítanie 1 v tomto systéme sú takmer také jednoduché ako v binárnom: pohybom od posledného bitu sa pokúste pridať do aktuálneho bitu 1. Ak je to možné, pridajte 1 na zastavenie. Ak to nie je možné, napíšte bit nula a prejdite na ďalší bit.

Snímka 10

Iterácia cez sady indexov - 2

Uvažujme o nasledujúcom príklade: 7 6 5 4 3 2 1 Toto sú premenné základy 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Všimnite si, že v 3 4 4 2 2 1 0 každý riadok začína 3 4 4 3 0 0 0 rovnako ako v predchádzajúcom, 3 4 4 3 0 1 0 potom príde prvok, presne 3 4 4 3 1 0 0 väčší, . . . a 3 4 4 3 1 1 0 to, čo nasleduje, nie je podstatné. 3 4 4 3 2 0 0 Každý riadok 3 4 4 3 2 1 0 je teda lexikograficky väčší ako 3 5 0 0 0 0 0 predchádzajúceho. 3 5 0 0 0 1 0

snímka 11

Lexikografický teorém o enumerácii permutácií

Opísaný algoritmus vymenúva permutácie v lexikografickom vzostupnom poradí. Dôkaz. Stačí nám ukázať, že ak máme dve sady indexov I1 a I2 a I1 lexikograficky predchádza I2, potom permutácia (I1) lexikograficky predchádza (I2). Tieto permutácie sa vytvárajú postupne a pokiaľ sa I1 a I2 zhodujú, zhodujú sa aj ich permutácie. Väčšia hodnota indexu zodpovedá väčšiemu prvku.

snímka 12

Priamy algoritmus pre lexikografický výpočet permutácií

Zoberieme nejakú permutáciu p a priamo nájdeme lexikograficky ďalšiu. Zoberme si začiatok – prvých k prvkov. Medzi jeho rozšíreniami je známe minimum, v ktorom sú všetky prvky usporiadané vzostupne, a maximum, v ktorom sú usporiadané zostupne. Napríklad v permutácii p = (4, 2, 1, 7, 3, 6, 5) všetky rozšírenia pre (4, 2, 1) ležia medzi (3, 5, 6, 7) a (7, 6, 5, 3). Existujúce pokračovanie je menšie ako maximum a 3. prvok môže zostať nezmenený. A tiež 4. A ten 5. treba zmeniť. Aby ste to dosiahli, zo zostávajúcich prvkov musíte zobrať ďalší v poradí, položiť ho na 5. a priradiť minimálne pokračovanie. Ukazuje sa (4, 2, 1, 7, 5, 3, 6).

snímka 13

Priamy algoritmus na lexikografický výpočet permutácií - 2

Zapíšme si nasledujúce permutácie. (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)

Snímka 14

Formálny popis algoritmu

Pracovný stav: Permutácia p a booleovský znak je aktívny. Počiatočný stav: Zapíše sa triviálna permutácia a isActive = True. Štandardný krok: Ak je aktívny, vráťte permutáciu ako výsledok. Postupujúc od konca nájdite najväčšiu monotónne klesajúcu príponu v permutácii. Nech k je pozícia pred príponou. Dajte isActive:= (k > 0). Ak je aktívny, nájdite najmenší prvok v prípone, ktorý presahuje pk, vymeňte ho za pk a potom príponu „otočte“.

snímka 15

Ďalší permutačný algoritmus

Skúsme teraz vymenovať permutácie tak, aby sa dve po sebe nasledujúce permutácie od seba len málo líšili. ako málo? Jednou elementárnou transpozíciou, pri ktorej sú zamenené dva susedné prvky. Je to možné? Ukážeme schematický diagram takéhoto algoritmu, bude nás to zaujímať. Predstavte si n-1 elementárnych „mechanizmov“, z ktorých každý posúva svoj prvok v rámci množiny. Pri každom kroku sa mechanizmus posunie doľava alebo doprava. Smer sa zmení, keď prvok dosiahne okraj. Na zmenu smeru stačí jeden krok, počas ktorého urobí krok ďalší mechanizmus, ktorý však môže zmeniť aj smer.

snímka 16

Ďalší permutačný enumeračný algoritmus -2

Pozrime sa na príklad. 1 2 3 4 mája, ktorých vôľa 1 2 3 4 5, ktorého koleso a b c d e a c d a b e a b a c d e a c d b a e a b c a d e a c d b e a b b c d a e a c d e b a a b c d e a b c d e a b a c b d e a a c d a e b a c b d a e s c a d e b a c b a d e a a c d e b c c a b d e a a d c e b a c b d e b d a a c e b a a c d b e a d c a e b a c a d b e a d c e A B A

Snímka 17

Zoznam permutácií. jeden

function ExistsNextPerm(var kCh: integer): Boolean; var iV,iP,iVC,iPC: celé číslo; beginresult:= False; pre iV:= nV po 2 urobte, ak počítajte

Snímka 18

Problém minimálneho súčtu párových produktov

Nech sú dané dve množiny n čísel, povedzme, (ak|k1:n) a (bk|k1:n) . Tieto čísla sa rozdelia do párov (ak,bk) a vypočíta sa súčet ich párových súčinov k1:n akbk. Môžete zmeniť číslovanie (ak) a (bk). Je potrebné zvoliť také číslovanie, pri ktorom je súčet minimálny. V tomto probléme je možné opraviť niektoré číslovanie (ak) a (bk) a hľadať permutáciu , pre ktorú sa dosiahne minimum súčtu k1:n akb(k). Číslovanie vyberieme vtedy, keď sú (ak) vo vzostupnom poradí a (bk) sú v zostupnom poradí.

Snímka 19

Veta o minimálnom súčte párových produktov

Minimum súčtu párových produktov sa dosiahne na triviálnej permutácii. Dôkaz. Predpokladajme, že existujú dva indexy k a r také, že ak 0, t.j. ar br + ak bk > ar bk + ak br . V našom číslovaní (ak) sú usporiadané vzostupne. Ak (bk) nie sú vo vzostupnom poradí, potom existuje dvojica k a r, ako je uvedené vyššie. Preskupením bk a br pre tento pár znížime hodnotu súčtu. Preto sú v optimálnom riešení (bk) vo vzostupnom poradí. S touto jednoduchou vetou sa v nasledujúcom texte stretneme niekoľkokrát.

Snímka 20

Problém maximálnej rastúcej subsekvencie

Je daná postupnosť (ak|k1:n) čísel dĺžky n. Je potrebné nájsť jeho postupnosť najväčšej dĺžky, v ktorej by čísla (ak) išli vzostupne. Napríklad v sekvencii 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9 bude maximálna podsekvencia 2, 11, 14, 16 , 17, 25, 37, 41 Tento problém súvisí s permutáciami, pretože pôvodná sekvencia môže byť permutáciou. Obmedzíme sa na ukážku, ako je tento problém vyriešený, a formalizáciu a zdôvodnenie algoritmu necháme na publikum.

snímka 21

Nájdenie maximálnej rastúcej subsekvencie

Tie naše rozdelíme čo najhospodárnejšie do klesajúcich sekvencií (príklad upravený) najvyššie z riadkov, kde to neporušuje poradie. Zoberme si číslo zo spodného riadku, 21. Prečo je v 8. riadku? 19 zasahuje do nej. Ale 17 interferuje s 19. A z jedného riadku Dirichletov princíp) a nemôže sa zvyšovať.

snímka 22

Problém minimálneho počtu inverzií

Je daná postupnosť (ak|k1:n) čísel dĺžky n. Inverzia je zrkadlový odraz niektorých jej podreťazcov, súvislá podsekvencia, vykonávaná na mieste. Je potrebné usporiadať prvky postupnosti vo vzostupnom poradí pre minimálny počet inverzií. Napríklad „pevná“ permutácia môže byť transformovaná takto (červené písmená sú preusporiadané, veľké sú už na svojom mieste)

snímka 23

Otázky na skúšku

Permutácie. Ich vyčíslenie a číslovanie. Problém minima skalárneho súčinu. Problém najväčšej rastúcej podsekvencie.

snímka 24

1. Permutácia obojsmerného prechodu  číslo 2. Nájdite permutáciu, ktorá je od danej permutácie vzdialená o daný počet krokov. 3. Enumerácia permutácií elementárnymi transpozíciami. 4. Spustite príklad problému minima skalárneho súčinu.

Tipy, ako urobiť dobrú prezentáciu alebo správu o projekte

1. Snažte sa vtiahnuť publikum do deja, nastavte interakciu s publikom pomocou navádzacích otázok, hernú časť, nebojte sa vtipkovať a úprimne sa usmievať (tam, kde je to vhodné).
2. Pokúste sa vysvetliť snímku vlastnými slovami, pridajte ďalšie zaujímavé fakty, nemusíte len čítať informácie zo snímok, diváci si ich môžu prečítať sami.
3. Nie je potrebné preťažovať snímky projektu textovými blokmi, viac ilustrácií a minimum textu lepšie sprostredkuje informácie a pritiahne pozornosť. Na snímke by mali byť len kľúčové informácie, ostatné je lepšie povedať publiku ústne.
4. Text musí byť dobre čitateľný, inak publikum neuvidí poskytnuté informácie, bude značne vyrušené z deja, bude sa snažiť aspoň niečo rozlúštiť alebo úplne stratí záujem. K tomu je potrebné zvoliť správne písmo s prihliadnutím na to, kde a ako sa bude prezentácia vysielať, a tiež zvoliť správnu kombináciu pozadia a textu.
5. Dôležité je nacvičiť si reportáž, premyslieť si, ako pozdravíte publikum, čo poviete ako prvé, ako ukončíte prezentáciu. Všetko prichádza so skúsenosťami.
6. Vyberte si ten správny outfit, pretože. Veľkú úlohu pri vnímaní jeho prejavu zohráva aj oblečenie rečníka.
7. Snažte sa hovoriť sebavedomo, plynulo a súvisle.
8. Skúste si užiť predstavenie, aby ste boli uvoľnenejší a menej úzkostliví.

Prezentácia "Permutácie" predstavuje vzdelávací materiál pre školskú hodinu na túto tému. Prezentácia obsahuje definíciu permutácií, názorné príklady na pochopenie významu tejto operácie, popis matematického aparátu na riešenie úloh s permutáciami, príklady riešenia úloh. Úlohou prezentácie je sprostredkovať vzdelávací materiál žiakom pohodlnou, zrozumiteľnou formou, prispieť k jeho lepšiemu pochopeniu a zapamätaniu.

Prezentácia využíva špeciálne techniky, ktoré pomáhajú učiteľovi vysvetliť novú tému. Učebné materiály sú vopred štruktúrované. Pomocou animačných efektov prezentujú príklady a úlohy, pričom pri názornej ukážke zdôrazňujú dôležité vlastnosti príkladov a úloh. Dôležité pojmy sú farebne zvýraznené, aby boli ľahšie zapamätateľné.

Po predstavení témy lekcie sa študentom ukáže definícia permutácií ako najjednoduchších kombinácií, ktoré je možné vytvoriť z určitého súboru prvkov. Text je zvýraznený výkričníkom ako dôležitý na zapamätanie.

Nasleduje príklad permutácií na farebných ceruzkách, ktoré možno umiestniť v inom poradí. Na tento účel sú ceruzky podpísané prvým písmenom ich farebného názvu: S, K, Zh. Pomocou animovanej prezentácie sú jasne znázornené možnosti usporiadania týchto ceruziek. Na jednej snímke sú najskôr umiestnené modré ceruzky a vedľa nich sú dve možnosti umiestnenia - červená a žltá, žltá a červená. Na ďalšej snímke sú zobrazené možnosti umiestnenia ceruziek po červenej – modrej a žltej, žltej a modrej. Posledné možné možnosti sú po žltej červenej a modrej, modrej a červenej. Po názornej ukážke sú vykonané operácie podpísané ako permutácie troch prvkov. Presnejšia definícia permutácie troch prvkov je uvedená na samostatnej snímke 7. V pamäťovom poli je zvýraznený text, že každé usporiadanie týchto prvkov v určitom poradí sa bude nazývať permutácia troch prvkov.

Snímka 8 ukazuje zápis permutácií n prvkov - P n . Je naznačené, že permutácie troch prvkov boli podrobne uvažované na príklade ceruziek, pričom je zrejmé, že takýchto permutácií bude 6. Matematický záznam počtu permutácií je vyznačený na snímke: P 3 =6 . Ďalej na obrazovke je uvedené, že existuje pravidlo kombinatorického násobenia na nájdenie počtu permutácií troch prvkov.

Na ďalšej snímke je postup permutácií rozložený na kroky, aby sa získalo pravidlo na zistenie počtu permutácií. Uvádza sa, že pre výpočet je potrebné umiestniť ktorýkoľvek z troch prvkov na prvé miesto. Na výber druhého prvku má dve možnosti. Zostáva len výber tretieho prvku. To znamená, že počet permutácií 3 prvkov sa zistí vynásobením 3.2.1=6. Dostaneme celkový počet možných permutácií. Podobne ako pri procese hľadania permutačných variantov sa uvažuje o variabilite pre n prvkov.

Nech existuje nejaká množina n prvkov. Pri ňom je jeden z n-1 prvkov umiestnený na druhom mieste, jeden z n-2 prvkov je umiestnený na treťom mieste a tak ďalej. Môžeme teda odvodiť všeobecné pravidlo na zistenie počtu permutácií n prvkov: P n =n(n-1)(n-2).….3.2.1.

Na snímke 11 je vzorec P n zobrazený v tvare P n =1.2.3....(n-2)(n-1)n. Zavádza sa teda pojem faktoriál, ktorého označenie je uvedené pod vzorcom: n!. Uvažujeme príklady nájdenia faktoriálu nejakého čísla: 3!=1.2.3=6 a tiež 6!=1.2.3.4.5.6=720. Tiež uvádza, že 1!=1. Text všeobecného pravidla na zistenie počtu permutácií ako n faktoriál sa nachádza v spodnej časti snímky.

Ďalej sa navrhuje zvážiť niekoľko problémov na nájdenie počtu permutácií. Na snímke 12 sa navrhuje vyriešiť problém nájdenia počtu spôsobov, ako rozložiť sedem loptičiek na sedem buniek. Uvádza sa, že riešením je vypočítať počet permutácií 7 prvkov: P 7 =7!=5040.

Snímka 13 rozoberá riešenie úlohy nájsť počet štvorciferných čísel, ktoré sú tvorené 0,1,2,3, pričom čísla v jednom čísle sa neopakujú. Riešenie sa poskytuje v dvoch fázach - najprv sa zistí počet všetkých permutácií 4 prvkov a potom sa od nich odpočíta počet permutácií, v ktorých čísla s 0 na začiatku, takže čísla začínajúce od nuly nebudú štyri- číslica. Riešením je teda výpočet P4-P3=4!-3!=18. To znamená, že existuje 18 možností na vytvorenie takýchto čísel.

Posledná snímka pojednáva o riešení úlohy, ktorá navrhuje nájsť počet spôsobov, ako možno usporiadať 9 platní, z toho 4 červené, aby červené boli vedľa seba. Hlavným problémom pri riešení tohto problému je pochopiť, že červené dosky v týchto permutáciách treba brať ako jednu. Riešenie sa teda redukuje na nájdenie produktu P6.P4=6!.4!=17280.

Prezentácia „Permutácie“ má za cieľ vizuálne sprevádzať výklad učiteľa na tému „Permutácie“. Podrobná, zrozumiteľná prezentácia vzdelávacieho materiálu môže byť užitočná aj pri dištančnom vzdelávaní a úlohy zvažované v tomto prípade pomôžu študentovi samostatne sa vysporiadať s riešením.

Základy kombinatoriky.

Umiestnenia, permutácie,

kombinácie.

nezbedná opica

somár,

Koza,

Áno, PEC Mishka

Začal hrať kvarteto

Prestaňte, bratia, prestaňte! -

Opica kričí, - počkaj!

Ako ide hudba?

Nesedíš tak...

A tak, a tak transplantované - opäť hudba nejde dobre.

Tu, viac ako kedykoľvek predtým, išla ich analýza

A spory

Kto a ako má sedieť...

vedieť:

• definície troch najdôležitejších pojmov kombinatoriky:
• umiestnenie n prvkov podľa m;
• kombinácie n prvkov podľa m;
• permutácie n prvkov;
• základné kombinatorické vzorce

byť schopný:

• rozlišovať medzi sebou úlohy na „permutácie“, „kombinácie“, „umiestnenia“;
• aplikovať základné kombinatorické vzorce pri riešení najjednoduchších kombinatorických úloh.

kopa

Súbor je charakterizovaný spojením niektorých homogénnych predmetov do jedného celku.

Objekty, ktoré tvoria množinu, sa nazývajú prvky množiny.

Množinu napíšeme umiestnením jej prvkov do zložených zátvoriek ( a, b, c, … , e, f}.

V množine nezáleží na poradí prvkov, takže ( a, b} = {b, a}.

Volá sa množina, ktorá neobsahuje žiadny prvok prázdna sada a označuje sa symbolom ø.

kopa

Ak každý prvok množiny A je prvkom množiny B, potom hovoríme, že množina A je podmnožinou množiny V.

Kopa ( a, b) je podmnožinou množiny ( a, b, c, … , e, f}.

Označené

Uveďte možné možnosti pre podmnožinu množiny ( 3 , 4 , 5 , 7, 9 }.

Kombinatorika je oblasť matematiky, ktorá študuje otázky o tom, koľko rôznych kombinácií za určitých podmienok možno vytvoriť z prvkov patriacich do danej množiny.

Kombinatorika je dôležitým odvetvím matematiky, ktoré študuje vzorce usporiadania, usporiadania, výberu a distribúcie prvkov z pevnej množiny.

PRAVIDLO SÚČTU

Ak je možné vykonať dve vzájomne sa vylučujúce akcie podľa k a m spôsobmi, potom je možné vykonať jednu z týchto akcií k+m spôsoby.

Príklad č. 1

Z mesta A do mesta B sa dá dostať 12 vlakmi, 3 lietadlami, 23 autobusmi. Koľkými spôsobmi sa môžete dostať z mesta A do mesta B?

Riešenie

Príklad č. 2

V krabici je n farebných loptičiek. Náhodne vytiahnite jednu loptičku. Koľkými spôsobmi sa to dá urobiť?

Riešenie. určite, n spôsoby.

Teraz je týchto n loptičiek rozdelených do dvoch boxov: V prvom m gule, v druhom k. Náhodne vyberte jednu loptičku z ľubovoľnej krabice. Koľkými rôznymi spôsobmi sa to dá urobiť?

Riešenie.

Loptičku je možné ťahať z prvého políčka m rôznymi spôsobmi, od druhého k rôznymi spôsobmi, celkový N = m + k spôsoby.

PRAVIDLO PRODUKTU

V súlade s tým môžu byť vykonané dve akcie vykonané jedna po druhej k a m spôsoby Potom je možné vykonať oboje k ∙ m spôsoby.

Príklad č. 3

Turnaja sa zúčastňuje 8 hokejových tímov. Koľko spôsobov je možné rozdeliť na prvé, druhé a tretie miesta?

Riešenie

Príklad č. 4

Koľko dvojciferných čísel možno zapísať v desiatkovej sústave?

Riešenie. Keďže číslo je dvojciferné, počet desiatok ( m) môže mať jednu z deviatich hodnôt: 1,2,3,4,5,6,7,8,9. Počet jednotiek ( k) môže nadobúdať rovnaké hodnoty a môže sa navyše rovnať nule. Z toho teda vyplýva m= 9 a k= 10. Celkovo dostaneme dvojciferné čísla

N= m · k= 910 = 90.

Príklad č. 5

V žiackej skupine je 14 dievčat a 6 chlapcov. Koľkými spôsobmi možno vybrať dvoch študentov rovnakého pohlavia na splnenie rôznych úloh?

Riešenie. Podľa pravidla násobenia dvoch dievčat si môžete vybrať 14 13 = 182 spôsobov a dvaja chlapci 6 5 = 30 spôsobov. Mali by byť vybratí dvaja študenti rovnakého pohlavia: dvaja študenti alebo študentky. Podľa pravidla sčítania takýchto volieb,

N = 182 + 30 = 212.

Typy pripojenia

Množiny prvkov sa nazývajú zlúčeniny.

Existujú tri typy spojení:

• permutácie z n prvky;
• ubytovanie od n prvky podľa m;
• kombinácie z n prvky podľa m (m < n).

Definícia: permutácia z n prvkov je ľubovoľná usporiadaná množina n prvkov.

Inými slovami, ide o takú množinu, pri ktorej sa uvádza, ktorý prvok je na prvom mieste, ktorý na druhom, ktorý na treťom, ..., ktorý na n-tom mieste.

PERMUTÁCIE

Permutácie sú také spojenia n prvky z daných prvkov, ktoré sa navzájom líšia v poradí prvkov.

Počet permutácií n prvkov označujeme Pn.

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

Definícia:

Nechaj n- prirodzené číslo. Naprieč n! (čítaj "en faktoriál") označuje číslo, ktoré sa rovná súčinu všetkých prirodzených čísel 1 od do n:

n! = 1 2 3 ... n.

Ak n= 0, podľa definície sa predpokladá: 0! = 1.

FAKTORIÁLNY

Príklad č. 6

Nájdite hodnoty nasledujúcich výrazov: 1! 2! 3!

Príklad č. 7

Čo sa rovná

a) R 5 ;

b) R 3.

Príklad č. 8

Zjednodušiť

b) 12! 13 14

v) κ ! · ( κ + 1)

Príklad #9

Koľkými spôsobmi možno umiestniť 8 účastníkov finálového závodu na osem bežeckých pásov?

Riešenie.

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

UBYTOVANIE

Definícia. Ubytovanie od n prvkov podľa m volá sa ľubovoľná objednaná množina m prvky, pozostávajúce z prvkov n sada prvkov.

Počet umiestnení z m prvky podľa n znamená:

vypočítané podľa vzorca:

Príklad #9

Žiaci 11. ročníka študujú 9 predmetov. Do rozvrhu tréningov na jeden deň si môžete dať 4 rôzne predmety. Koľko rôznych spôsobov je možné naplánovať si deň?

Riešenie.

Máme 9-prvkovú zostavu, ktorej prvkami sú výchovné predmety. Pri rozvrhu si vyberieme 4-prvkovú podmnožinu (lekcií) a nastavíme v nej poradie. Počet takýchto spôsobov sa rovná počtu umiestnení z deviatich krát štyri ( m=9, n=4) to jest A 94:

Príklad #10

Koľkými spôsobmi možno vybrať prefekta a asistenta prefekta z triedy 24 žiakov?

Riešenie.

Máme 24-prvkovú zostavu, ktorej prvkami sú žiaci triedy. Pri voľbe prednostu a zástupcu prednostu si vyberieme 2-prvkovú podmnožinu (žiaka) a ustanovíme v nej poriadok. Počet takýchto spôsobov sa rovná počtu umiestnení z deviatich krát štyri( m=24, n=2), tj A 242:

KOMBINÁCIE

Definícia. Kombinácia bez opakovaní z n prvky podľa m- nazývaný ľubovoľný m elementárna podmnožina n- súprava prvkov

Označuje sa počet kombinácií n prvkov podľa m

a vypočíta sa podľa vzorca:

Príklad č. 11

Koľkými spôsobmi možno vybrať dvoch účastníkov z triedy 24 žiakov?

Riešenie.

n =24, m=2

KOMBINÁCIE

UBYTOVANIE

PERMUTÁCIE

Рn = n!

Určite, do akého typu pripojení úloha patrí.

1. Koľkými spôsobmi si môžete rozvrhnúť jeden školský deň z 5 rôznych vyučovacích hodín?

2. V triede 9B je 12 žiakov. Koľkými spôsobmi možno zostaviť tím 4 ľudí, ktorí sa zúčastnia matematickej olympiády?

Zohľadňuje sa poradie prvkov v spojení?

Sú v spojení zahrnuté všetky prvky?

Záver: permutácia

Zohľadňuje sa poradie prvkov v spojení?

Sú v spojení zahrnuté všetky prvky?

(táto otázka nepotrebuje odpoveď)

Záver: kombinácie

3. Koľko je rôznych dvojciferných čísel, v ktorých možno použiť čísla 1, 2, 3, 4, 5, 6, ak sa čísla v čísle musia líšiť?

Zohľadňuje sa poradie prvkov v spojení?

Sú v spojení zahrnuté všetky prvky?

Záver: umiestnenie

nezbedná opica

Áno, PEC Mishka

Začal hrať kvarteto

Prestaňte, bratia, prestaňte! -

Opica kričí, - počkaj!

Ako ide hudba?

Nesedíš tak...

A tak, a tak transplantované - opäť hudba nejde dobre.

Tu, viac ako kedykoľvek predtým, išla ich analýza

Kto a ako má sedieť...

Koľko rôznych aranžmánov hudobníkov je možných?

Riešenie.

Zohľadňuje sa poradie prvkov v spojení?

Sú v spojení zahrnuté všetky prvky?

Záver: permutácia

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

P4 = 4! = 4 3 2 1 = 24

„Každá správna matematická myšlienka skôr či neskôr nájde uplatnenie v tom či onom biznise“?

permutácií

ubytovanie

kombinácia

Výsledky riešenia problémov

DOMÁCA ÚLOHA

Naučte sa abstrakt a vzorce.

S. 321 č. 1062

Permutácie sú kombinácie tvorené rovnakými prvkami, ktoré sa líšia v poradí. Počet všetkých možných permutácií prvkov označujeme P n a možno ho vypočítať podľa vzorca: Permutačný vzorec: P n =n! Počas permutácie zostáva počet objektov nezmenený, mení sa len ich poradie.S pribúdajúcim počtom objektov počet permutácií veľmi rýchlo rastie a je ťažké ich vizuálne zobraziť.

Úloha 1. Turnaja sa zúčastňuje sedem tímov. Koľko možností na rozdelenie miest medzi nimi je možných? Р 7 =7!=1*2*3*4*5*6*7=5040 Odpoveď: 5040 Úloha 2. Koľkými spôsobmi môže 10 ľudí sedieť za okrúhlym stolom? P 10 = 10! = = 1*2*3*4*5*6*7*8*9*10 = odpoveď:

Nech je n rôznych predmetov. Vyberieme z nich m objektov a preusporiadame ich medzi sebou všetkými možnými spôsobmi. Výsledné kombinácie sa nazývajú umiestnenia n objektov po m a ich počet sa rovná: Pri umiestňovaní sa mení zloženie vybraných objektov aj ich poradie. Vzorec umiestnenia:

Úloha: Koľkými spôsobmi možno rozdeliť tri poukážky do jedného sanatória medzi päť ľudí? Keďže poukážky sú poskytované na jedno sanatórium, možnosti distribúcie sa od seba líšia minimálne pre jednu osobu. Preto počet spôsobov distribúcie Odpoveď: 10 spôsobov.

Úloha: V dielni pracuje 12 ľudí: 5 žien a 7 mužov. Koľkými spôsobmi sa dá zostaviť tím 7 ľudí tak, aby v ňom boli 3 ženy? Z piatich žien treba vybrať tri, teda počet metód výberu. Keďže je potrebné vybrať štyroch mužov zo siedmich, potom počet spôsobov výberu mužov Odpoveď: 350