KOMBINATORIKA

Cilji lekcije:

• Ugotovite, kaj preučuje kombinatorika
• Ugotovite, kako je nastala kombinatorika
• Spoznajte formule kombinatorike in se jih naučite uporabljati pri reševanju problemov

Rojstvo kombinatorike kot veje matematike je povezano z deli Blaisa Pascala in Pierra Fermata o teoriji iger na srečo.

Blaise Pascal

Pierre Fermat

Velik prispevek k razvoju kombinatoričnih metod je prispeval G.V. Leibniz, J. Bernoulli in L. Euler.

G.V. Leibniz

L. Euler.

I. Bernoulli

Lema. Naj bo v množici A m elementov, v množici B pa n elementov. Potem bo število vseh različnih parov (a,b), kjer je a\in A,b\in B, enako mn. Dokaz. Dejansko lahko z enim elementom iz množice A sestavimo n tako različnih parov, skupaj pa je v množici A m elementov.

Postavitve, permutacije, kombinacije Recimo, da imamo niz treh elementov a,b,c. Na kakšen način lahko izberemo dva od teh elementov? ab,ac,bc,ba,ca,cb.

Permutacije Preurejali jih bomo na vse možne načine (število predmetov ostane nespremenjeno, spremeni se le njihov vrstni red). Nastale kombinacije imenujemo permutacije, njihovo število pa je PN = n! =1 · 2 · 3 · ... · ( n-1) n

Simbol n! imenujemo faktoriel in označuje zmnožek vseh celih števil od 1 do n. Po definiciji menijo, da 0!=1 1!=1 Primer vseh permutacij n=3 objektov (različnih oblik) je na sliki. Po formuli bi moralo biti točno P3=3!=1⋅2⋅3=6 , in tako se tudi izkaže.

S povečanjem števila predmetov število permutacij zelo hitro raste in jih je težko vizualno prikazati. Na primer, število permutacij 10 elementov je že 3628800 (več kot 3 milijone!).

Prenočišča Naj bo n različnih predmetov. Izmed njih bomo izbrali m objektov in jih na vse možne načine preurejali med seboj (torej spreminjala se bo tako sestava izbranih objektov kot njihov vrstni red). Nastale kombinacije se imenujejo postavitve n predmetov z m, njihovo število pa je enako Aⁿm =n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)

Opredelitev. S postavitvijo niza n različnih elementov nad m elementov (m ≤ n) klical kombinacije , ki so sestavljeni iz danih n elementov z m elementi in se razlikujejo bodisi v samih elementih bodisi v vrstnem redu elementov.

Kombinacije Naj bo n različnih predmetov. Izmed njih bomo na vse možne načine izbrali m objektov (torej sestava izbranih objektov se spreminja, vrstni red pa ni pomemben). Nastale kombinacije imenujemo kombinacije n predmetov z m, njihovo število pa je enako Cmn=n!(n−m)!⋅m!

Primer vseh kombinacij n=3 objektov (različnih oblik) z m=2- je na spodnji sliki. Po formuli mora biti točno C23=3!(3−2)!⋅2!:3!=3. Jasno je, da je kombinacij vedno manj kot umestitev (ker je vrstni red pomemben pri umestitvah, ne pa pri kombinacijah), in ravno v m! krat, kar pomeni, da je relacijska formula pravilna: Amn=Cmn⋅Pm.

1. metoda. V eni igri sodelujeta 2 osebi, zato morate izračunati, na koliko načinov lahko izberete 2 osebi od 15, vrstni red v takih parih pa ni pomemben. S formulo poiščemo število kombinacij (vzorcev, ki se razlikujejo le po sestavi) n različnih elementov po m elementov

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

Metoda 2. Prvi igralec je odigral 14 iger (z 2., 3., 4. in tako naprej do 15.), 2. igralec je odigral 13 iger (3., 4. itd. do 15., izključujemo dejstvo, da je že obstajal igra s prvim), 3. igralec - 12 iger, 4. - 11 iger, 5 - 10 iger, 6 - 9 iger, 7 - 8 iger, 8 - 7 iger,

in 15. že igral z vsemi.

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

ODGOVOR. 105 strank.

Učiteljica matematike Aksenova Svetlana Valerievna

Srednja šola Bugrovskaya okrožja Vsevolozhsky Leningradske regije

diapozitiv 1

diapozitiv 2

diapozitiv 3

diapozitiv 4

diapozitiv 5

diapozitiv 6

Diapozitiv 7

Diapozitiv 8

Diapozitiv 9

Diapozitiv 10

diapozitiv 11

diapozitiv 12

diapozitiv 13

Diapozitiv 14

diapozitiv 15

diapozitiv 16

Diapozitiv 17

Diapozitiv 18

Diapozitiv 19

Diapozitiv 20

diapozitiv 21

diapozitiv 22

diapozitiv 23

diapozitiv 24

Predstavitev na temo "Diskretna analiza. Kombinatorika. Permutacije" lahko popolnoma brezplačno prenesete na naši spletni strani. Predmet projekta: Informatika. Pisani diapozitivi in ​​ilustracije vam bodo pomagali vzbuditi zanimanje vaših sošolcev ali občinstva. Za ogled vsebine uporabite predvajalnik, če pa želite poročilo prenesti, kliknite na ustrezno besedilo pod predvajalnikom. Predstavitev vsebuje 24 diapozitivov.

Predstavitveni diapozitivi

diapozitiv 1

Diskretna analiza

3. predavanje Kombinatorika. Permutacije

diapozitiv 2

Permutacije

Naj bo podana množica n elementov. Vrstni red teh elementov imenujemo permutacija. Včasih je dodan "od n elementov". Običajno ločimo eno, osnovno ali naravno, vrstni red, ki ga imenujemo trivialna permutacija. Elementi množice A nas ne zanimajo. Pogosto se kot elementi vzamejo cela števila od 1 do n ali od 0 do n-1. Množico permutacij n elementov označimo s Pn in njeno kardinalnost s Pn. Zastavimo si ista tri vprašanja: čemu je enako Pn, kako našteti elemente Pn, kako jih preštevilčiti.

diapozitiv 3

Izrek o številu permutacij

Število permutacij n elementov je n! - produkt števil od 1 do n. (n! se bere n-faktoriel) Dokaz. Z indukcijo. Za n=1 je formula očitno pravilna. Naj velja za n-1, dokazali bomo, da velja tudi za n. Prvi element vrstnega reda lahko izberemo na n načinov, ostale pa priredimo izbranemu prvemu elementu na načine. Zato je formula Pn= Pn-1n pravilna. Če je Pn-1=(n-1)!, potem je Pn=n!

diapozitiv 4

Permutacijsko oštevilčenje

Za oštevilčenje permutacij preslikamo množico Pn ena proti ena na drugo množico Tn, na kateri bo veliko lažje ošteti, nato pa za katerikoli element pPn vzamemo številko njegove slike v Tn kot njegovo številko. . Množica Tn je neposredni produkt več numeričnih segmentov Tn =(0:(n-1))(0:(n-2) ... (0). To pomeni, da je vsak element Tn množica nenegativnih števil i1, i2, …, in-1, in in ikn-k.

diapozitiv 5

Zaslon

Vzemite permutacijo in zraven zapišite trivialno permutacijo. Kot prvi indeks zavzamemo mesto prvega elementa (šteto od nič) v trivialni permutaciji. Namesto trivialne permutacije napišimo niz preostalih znakov. Kot drugi indeks zavzemite mesto drugega elementa permutacije v tej vrstici. Postopek ponovimo do konca. Očitno bo k-ti indeks manjši od dolžine k-te vrstice, zadnji indeks pa bo enak nič. Oglejmo si ta postopek na primeru.

diapozitiv 6

Primer prikaza

0 1 2 3 4 5 6 Kazalo c a d f g b e a b c d e f g 2 2 a d f g b e a b d e f g 0 2 0 d f g b e b d e f g 1 2 0 1 f g b e b e f g 2 2 0 1 2 g b e b e g 2 2 0 1 2 2 b e b e 0 2 0 1 2 2 0 e e 0 2 0 1 2 2 0 0 Očitno je, da je ta proces reverzibilen in da bo inverzno preslikavo zgradilo začetno permutacijo iz niza indeksov.

Diapozitiv 7

Oštevilčenje množice Tn

Vsak neposredni produkt urejenih množic lahko gledamo kot številski sistem s spremenljivo osnovo. Spomnite se primera sekund iz prvega predavanja ali razmislite o kakšni stari lestvici velikosti: 1 jard = 3 čevlje, 1 čevelj = 12 palcev, 1 palec = 12 črt, 1 črta = 6 točk. (2, 0, 4, 2, 3) = 2 jarda 0 čevljev 4 palca 2 črti 3 točke, koliko točk je to? Prešteti morate (to se imenuje Hornerjeva shema) (((2  3+0)  12+4)  12+2)  6+3

Diapozitiv 8

Oštevilčenje niza Tn - 2

Formulo #, ki poišče število za množico indeksov i1, i2, ..., in-1, in, raje zapišemo v obliki rekurzivnih izrazov #(i1, i2, ..., in) = a (i1, i2, ..., v-1, n-1); a(i1, i2, …, ik,k) = a(i1, i2, …, ik-1,k-1)(n-k+1)+ ik; a(prazno,0) = 0; V skladu s to formulo #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). Imamo 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;

Diapozitiv 9

Ponavljanje nizov indeksov

Na podlagi zgoraj navedenega je razvrščanje permutacij preprosto: našteti morate vse nize indeksov iz in za vsak niz zgraditi ustrezno permutacijo. Za naštevanje nizov indeksov upoštevamo, da je pravzaprav vsak niz zapis števila v posebnem številskem sistemu s spremenljivo osnovo (sistem imenujemo faktorial). Pravila za dodajanje 1 v tem sistemu so skoraj tako preprosta kot v dvojiškem sistemu: premikanje od zadnje števke, poskusite trenutni števki dodati 1. Če je mogoče, se dodajanje 1 ustavi. Če ni mogoče, zapišite bit nič in pojdite na naslednji bit.

Diapozitiv 10

Ponavljanje nizov indeksov - 2

Razmislite o tem primeru: 7 6 5 4 3 2 1 To so spremenljive osnove 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Upoštevajte, da se v 3 4 4 2 2 1 0 vsaka vrstica začne s 3 4 4 3 0 0 0 enako kot v prejšnjem, 3 4 4 3 0 1 0 nato sledi element, strogo 3 4 4 3 1 0 0 večji, . . . , in 3 4 4 3 1 1 0 kar sledi ni bistveno. 3 4 4 3 2 0 0 Torej je vsaka vrstica 3 4 4 3 2 1 0 leksikografsko večja od 3 5 0 0 0 0 0 prejšnje. 3 5 0 0 0 1 0

diapozitiv 11

Izrek o leksikografskem naštevanju permutacij

Opisani algoritem našteje permutacije v leksikografskem naraščajočem vrstnem redu. Dokaz. Zadostuje pokazati, da če imamo dva niza indeksov I1 in I2 in je I1 leksikografsko pred I2, potem je permutacija (I1) leksikografsko pred (I2). Te permutacije se tvorijo zaporedno in dokler se I1 in I2 ujemata, se ujemata tudi njuni permutaciji. Večja vrednost indeksa ustreza večjemu elementu.

diapozitiv 12

Neposredni algoritem za leksikografsko naštevanje permutacij

Vzamemo neko permutacijo p in neposredno poiščemo leksikografsko naslednjo. Vzemimo začetek – prvih k elementov. Med njegovimi razširitvami poznamo minimum, v katerem so vsi elementi razvrščeni v naraščajočem vrstnem redu, in maksimum, v katerem so razvrščeni v padajočem vrstnem redu. Na primer, v permutaciji p = (4, 2, 1, 7, 3, 6, 5) vse razširitve za (4, 2, 1) ležijo med (3, 5, 6, 7) in (7, 6, 5, 3). Obstoječe nadaljevanje je manjše od maksimuma, 3. element pa lahko še vedno ostane nespremenjen. In 4. tudi. In 5. je treba spremeniti. Če želite to narediti, morate od preostalih elementov vzeti naslednjega po vrstnem redu, ga postaviti na 5. in dodeliti najmanjše nadaljevanje. Izkazalo se je (4, 2, 1, 7, 5, 3, 6).

diapozitiv 13

Neposredni algoritem za leksikografsko naštevanje permutacij - 2

Zapišimo naslednje permutacije. (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)

Diapozitiv 14

Formalni opis algoritma

Delovno stanje: permutacija p in logični znak sta aktivna. Začetno stanje: Zapisana je trivialna permutacija in isActive = True. Standardni korak: Če je aktiven, vrni permutacijo kot rezultat. Če se premikate od konca, poiščite največjo monotono padajočo pripono v permutaciji. Naj bo k položaj pred pripono. Postavite isActive:= (k > 0). Če je aktiven, poiščite najmanjši element v priponi, ki presega pk, ga zamenjajte s pk in nato »obrnite« pripono.

diapozitiv 15

Še en permutacijski algoritem

Poskusimo sedaj našteti permutacije tako, da se dve zaporedni permutaciji malo razlikujeta druga od druge. Kako malo? Z eno osnovno transpozicijo, pri kateri se dva sosednja elementa zamenjata. Ali je možno? Prikazali bomo shematski diagram takšnega algoritma, ki nas bo zanimal. Predstavljajte si n-1 elementarnih "mehanizmov", od katerih vsak premika svoj element znotraj niza. Pri vsakem koraku se mehanizem premakne v levo ali desno. Smer se spremeni, ko element doseže rob. Za spremembo smeri je potreben en korak, med katerim korak naredi naslednji mehanizem, ki pa lahko prav tako spremeni smer.

diapozitiv 16

Drug algoritem za oštevilčenje permutacije -2

Poglejmo primer. 1 2 3 4 5 Čigava poteza 1 2 3 4 5 Čigava poteza 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 da 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 c d a e b a c b d a e a 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 a d c e b a a c b d e b d a c e b a a c d b a d c a e b a c a d b a d c e a b a

Diapozitiv 17

Seznam permutacij. 1

funkcija ExistsNextPerm(var kCh: integer): Boolean; var iV,iP,iVC,iPC: celo število; beginresult:= False; za iV:= nV downto 2 do if count

Diapozitiv 18

Problem minimalne vsote parnih produktov

Naj sta podana dva niza n števil, recimo (ak|k1:n) in (bk|k1:n). Ta števila razdelimo na pare (ak,bk) in izračunamo vsoto njihovih parnih produktov k1:n akbk. Oštevilčenje (ak) in (bk) lahko spremenite. Izbrati je treba takšno številčenje, pri katerem je vsota minimalna. V tem problemu lahko popravimo nekaj oštevilčevanj (ak) in (bk) in poiščemo permutacijo , za katero je dosežen minimum vsote k1:n akb(k). Oštevilčenja bomo izbrali, ko so (ak) v naraščajočem vrstnem redu in (bk) v padajočem vrstnem redu.

Diapozitiv 19

Izrek o minimalni vsoti parnih produktov

Najmanjša vsota produktov po parih je dosežena na trivialni permutaciji. Dokaz. Recimo, da obstajata dva indeksa k in r taka, da je ak 0, tj. ar br + ak bk > ar bk + ak br . V našem oštevilčevanju (ak) so razvrščeni v naraščajočem vrstnem redu. Če (bk) niso v naraščajočem vrstnem redu, potem obstaja par k in r, kot je navedeno zgoraj. S preureditvijo bk in br za ta par bomo zmanjšali vrednost vsote. Zato so v optimalni rešitvi (bk) v naraščajočem vrstnem redu. Ta preprosti izrek bomo v nadaljevanju večkrat srečali.

Diapozitiv 20

Problem največjega naraščajočega podzaporedja

Podano je zaporedje (ak|k1:n) števil dolžine n. Najti je treba njegovo zaporedje največje dolžine, v katerem bi številke (ak) šle v naraščajočem vrstnem redu. Na primer, v zaporedju 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9 bo največje podzaporedje 2, 11, 14, 16 , 17, 25, 37, 41 Ta problem je povezan s permutacijami, ker je izvirno zaporedje lahko permutacija. Omejili se bomo na prikaz, kako se ta problem rešuje, formalizacijo in utemeljitev algoritma pa bomo prepustili občinstvu.

diapozitiv 21

Iskanje največjega naraščajočega podzaporedja

Našo bomo čim bolj ekonomično razdelili na padajoča zaporedja (primer spremenjen) na najvišji vrstici, kjer ne krši vrstnega reda. Vzemimo številko iz spodnje vrstice, 21. Zakaj je v 8. vrstici? 19 posega vanj. In 17 posega 19. In 16 posega vanj. In tako naprej. Zaporedje 9, 11, 14, 16, 17, 19, 21 narašča in ima dolžino 7. Vsako daljše zaporedje vsebuje dve števili iz ene vrstice Dirichletovo načelo) in ne more naraščati.

diapozitiv 22

Problem minimalnega števila inverzij

Podano je zaporedje (ak|k1:n) števil dolžine n. Inverzija je zrcalni odsev nekaterih njegovih podnizov, neprekinjeno podzaporedje, ki se izvaja na mestu.Za najmanjše število inverzij je potrebno razporediti elemente zaporedja v naraščajočem vrstnem redu. Na primer, "trdno" permutacijo je mogoče preoblikovati tako (rdeče črke so prerazporejene, velike so že na mestu)

diapozitiv 23

Izpitna vprašanja

Permutacije. Njihovo naštevanje in oštevilčenje. Problem minimuma skalarnega produkta. Problem največjega naraščajočega podzaporedja.

diapozitiv 24

1. Dvosmerna prehodna permutacija  številka 2. Poiščite permutacijo, ki je za dano število korakov oddaljena od dane. 3. Naštevanje permutacij z elementarnimi transpozicijami. 4. Izvedite primer za problem minimuma skalarnega produkta.

Nasveti, kako narediti dobro predstavitev ali projektno poročilo

1. Poskusite vključiti občinstvo v zgodbo, vzpostavite interakcijo z občinstvom z vodilnimi vprašanji, igralnim delom, ne bojte se šaliti in se iskreno nasmehniti (kjer je to primerno).
2. Poskusite prosojnico razložiti s svojimi besedami, dodajte dodatna zanimiva dejstva, ni vam treba samo brati informacij s prosojnic, občinstvo jih lahko prebere samo.
3. Diapozitivov projekta vam ni treba preobremeniti z besedilnimi bloki, več ilustracij in najmanj besedila bo bolje posredovalo informacije in pritegnilo pozornost. Na prosojnici naj bodo samo ključne informacije, ostalo je bolje povedati občinstvu ustno.
4. Besedilo mora biti dobro berljivo, sicer občinstvo ne bo moglo videti posredovanih informacij, bo močno odvrnjeno od zgodbe, poskušalo vsaj nekaj razbrati ali popolnoma izgubilo zanimanje. Če želite to narediti, morate izbrati pravo pisavo, pri čemer morate upoštevati, kje in kako bo predstavitev predvajana, ter izbrati pravo kombinacijo ozadja in besedila.
5. Pomembno je, da vadite svoje poročilo, razmislite, kako boste pozdravili občinstvo, kaj boste najprej rekli, kako boste zaključili predstavitev. Vse pride z izkušnjami.
6. Izberite pravo obleko, saj. Veliko vlogo pri zaznavanju njegovega govora ima tudi govorčeva obleka.
7. Poskusite govoriti samozavestno, tekoče in povezano.
8. Poskusite uživati ​​v nastopu, da boste lahko bolj sproščeni in manj zaskrbljeni.

Predstavitev "Permutacije" predstavlja izobraževalno gradivo za šolsko lekcijo na to temo. Predstavitev vsebuje definicijo permutacij, ilustrativne primere za razumevanje pomena te operacije, opis matematičnega aparata za reševanje problemov s permutacijami, primere reševanja problemov. Naloga predstavitve je učencem posredovati učno snov v priročni, razumljivi obliki, prispevati k njenemu boljšemu razumevanju in pomnjenju.

Predstavitev uporablja posebne tehnike za pomoč učitelju pri razlagi nove teme. Učna gradiva so vnaprej strukturirana. S pomočjo animacijskih učinkov predstavijo primere in naloge, pri čemer ob demonstraciji poudarijo pomembne značilnosti primerov in nalog. Pomembni koncepti so označeni z barvo, da si jih je lažje zapomniti.

Po predstavitvi teme lekcije se študentom prikaže definicija permutacij kot najenostavnejših kombinacij, ki jih je mogoče sestaviti iz določenega nabora elementov. Besedilo je označeno s klicajem kot pomembno, da si ga zapomnite.

Sledi primer permutacij na barvnih svinčnikih, ki jih je mogoče postaviti v drugačen vrstni red. Da bi to naredili, so svinčniki podpisani s prvo črko imena njihove barve: S, K, Zh. S pomočjo animirane predstavitve so jasno prikazane možnosti za postavitev teh svinčnikov v vrstnem redu. Na enem diapozitivu so najprej postavljeni modri svinčniki, poleg njih pa dve možnosti postavitve - rdeča in rumena, rumena in rdeča. Naslednji diapozitiv prikazuje možnosti za postavitev svinčnikov po rdeči - modra in rumena, rumena in modra. Zadnje možne možnosti so po rumeni rdeči in modri, modri in rdeči. Po vizualni predstavitvi so izvedene operacije označene kot permutacije treh elementov. Natančnejša definicija permutacije treh elementov je podana na ločenem diapozitivu 7. V spominskem polju je označeno besedilo, da se bo vsaka razporeditev teh elementov v določenem vrstnem redu imenovala permutacija treh elementov.

Diapozitiv 8 prikazuje zapis za permutacije n elementov - P n . Navedeno je, da so bile permutacije treh elementov podrobno obravnavane na primeru svinčnikov, medtem ko je očitno, da bo takih permutacij 6. Diapozitiv prikazuje matematični zapis števila permutacij: P 3 =6. Nadalje na zaslonu je zapisano, da obstaja pravilo kombinatornega množenja za iskanje števila permutacij treh elementov.

Na naslednjem diapozitivu je postopek permutacije razdeljen na korake, da dobimo pravilo za iskanje števila permutacij. Navedeno je, da je za izračun potrebno na prvo mesto postaviti katerega koli od treh elementov. Za izbiro drugega elementa sta dve možnosti. Edina možnost, ki ostane, je, da izberete tretji element. To pomeni, da bomo število permutacij 3 elementov našli z množenjem 3.2.1=6. Dobimo skupno število možnih permutacij. Podobno kot pri procesu iskanja variant permutacije se upošteva variabilnost za n elementov.

Naj obstaja neka množica n elementov. Zanj je eden od n-1 elementov postavljen na drugo mesto, eden od n-2 elementov je postavljen na tretje mesto in tako naprej. Tako lahko izpeljemo splošno pravilo za iskanje števila permutacij n elementov: P n =n(n-1)(n-2).….3.2.1.

Na diapozitivu 11 je formula P n prikazana v obliki P n =1.2.3.….(n-2)(n-1)n. Tako je uveden koncept faktoriala, katerega oznaka je prikazana pod formulo: n!. Upoštevani so primeri iskanja faktoriala nekega števila: 3!=1.2.3=6 in tudi 6!=1.2.3.4.5.6=720. Navaja tudi, da je 1!=1. Besedilo splošnega pravila za iskanje števila permutacij kot n faktoriala se nahaja na dnu diapozitiva.

Nato je predlagano, da se obravnava več problemov za iskanje števila permutacij. Na diapozitivu 12 je predlagana rešitev problema iskanja števila načinov za razgradnjo sedmih kroglic v sedem celic. Navedeno je, da je rešitev izračunati število permutacij 7 elementov: P 7 =7!=5040.

Diapozitiv 13 obravnava rešitev problema iskanja števila štirimestnih števil, ki so sestavljena iz 0,1,2,3, medtem ko se števila v enem številu ne ponavljajo. Rešitev je na voljo v dveh stopnjah - najprej se najde število vseh permutacij 4 elementov, nato pa se od njih odšteje število permutacij, pri čemer števila z 0 spredaj, tako da števila, ki se začnejo z nič, ne bodo štiri- številka. Tako se rešitev zmanjša na izračun P 4 -P 3 =4!-3!=18. To pomeni, da obstaja 18 možnosti za oblikovanje takšnih številk.

Zadnji diapozitiv obravnava rešitev problema, ki predlaga, da najdemo število načinov, na katere je mogoče razporediti 9 plošč, od katerih so 4 rdeče, tako da so rdeče nameščene ena poleg druge. Glavna težava pri reševanju tega problema je razumeti, da je treba rdeče plošče v teh permutacijah jemati kot eno. Tako se rešitev zmanjša na iskanje produkta P 6 .P 4 =6!.4!=17280.

Predstavitev »Permutacije« je namenjena vizualni spremljavi učiteljeve razlage na temo »Permutacije«. Podrobna, razumljiva predstavitev učnega gradiva je lahko koristna tudi pri učenju na daljavo, obravnavane naloge v tem primeru pa bodo študentu pomagale pri samostojnem reševanju rešitve.

Osnove kombinatorike.

Umestitve, permutacije,

kombinacije.

poredna opica

osel,

koza,

Ja, klobuka Miška

Začel igrati kvartet

Stojte, bratje, stopite! -

Opica kriči, - počakaj!

Kako gre glasba?

Ne sediš tako ...

In tako in tako presajeno - spet glasba ne gre dobro.

Tu je bolj kot kdajkoli prej šla njihova analiza

In spori

Kdo in kako sedi ...

vedeti:

• definicije treh najpomembnejših konceptov kombinatorike:
• postavitev n elementov po m;
• kombinacije n elementov po m;
• permutacije n elementov;
• osnovne kombinatorične formule

biti sposoben:

• razlikovati med nalogami v "permutacije", "kombinacije", "umestitve";
• uporabljajo osnovne kombinatorične formule pri reševanju najenostavnejših kombinatoričnih problemov.

kup

Za sklop je značilna združitev nekaterih homogenih predmetov v eno celoto.

Predmeti, ki tvorijo množico, se imenujejo elementi množice.

Množico bomo zapisali tako, da bomo njene elemente postavili v zavite oklepaje ( a, b, c, … , e, f}.

V nizu vrstni red elementov ni pomemben, torej ( a, b} = {b, a}.

Pokličemo množico, ki ne vsebuje nobenega elementa prazen niz in je označen s simbolom ø.

kup

Če vsak element množice A je element množice B, potem pravimo, da je množica A je podmnožica množice IN.

Kup ( a, b) je podmnožica množice ( a, b, c, … , e, f}.

Označeno

Navedite možne možnosti za podnabor nabora ( 3 , 4 , 5 , 7, 9 }.

Kombinatorika je veja matematike, ki preučuje vprašanja o tem, koliko različnih kombinacij je mogoče sestaviti iz elementov, ki pripadajo dani množici, pod določenimi pogoji.

Kombinatorika je pomembna veja matematike, ki preučuje vzorce razporeditve, vrstnega reda, izbire in distribucije elementov iz fiksne množice.

PRAVILO SEŠTEVANJA

Če je mogoče izvesti dve medsebojno izključujoči dejanji glede na k in m načine, potem je mogoče izvesti eno od teh dejanj k+m načine.

Primer #1

Od mesta A do mesta B se lahko pripelje z 12 vlaki, 3 letali, 23 avtobusi. Na koliko načinov lahko pridete iz mesta A v mesto B?

rešitev

Primer #2

V škatli je n barvnih kroglic. Naključno vzemite eno žogo. Na koliko načinov je to mogoče storiti?

rešitev. seveda, n načine.

Zdaj je teh n kroglic razdeljenih v dve škatli: V prvo mžoge, v drugem k. Iz poljubne škatle naključno vzemite eno kroglico. Na koliko različnih načinov je to mogoče storiti?

rešitev.

Žogica se lahko izvleče iz prvega polja m različne načine, od drugega k na različne načine, skupno N = m + k načine.

PRAVILO IZDELKA

Naj se dve dejanji, izvedeni eno za drugim, izvedeta v skladu k in m potem je oboje mogoče storiti k ∙ m načine.

Primer #3

Na turnirju sodeluje 8 hokejskih ekip. Koliko načinov je za razdelitev prvih, drugih in tretjih mest?

rešitev

Primer #4

Koliko dvomestnih števil lahko zapišemo v decimalnem zapisu?

rešitev. Ker je število dvomestno, je število desetic ( m) ima lahko eno od devetih vrednosti: 1,2,3,4,5,6,7,8,9. Število enot ( k) ima lahko enake vrednosti in je lahko poleg tega enak nič. Iz tega sledi, da m= 9 in k= 10. Skupaj dobimo dvomestna števila

N= m · k= 9 10 =90.

Primer #5

V dijaški skupini je 14 učenk in 6 fantov. Na koliko načinov lahko izberemo dva učenca istega spola, da opravita različni nalogi?

rešitev. Po pravilu množenja dveh deklet lahko izberete 14 13 = 182 načinov, dveh fantov pa 6 5 = 30 načinov. Izbereta se dva študenta istega spola: dva študenta ali študentka. V skladu s pravilom dodajanja takih izbir,

N = 182 + 30 = 212.

Vrste povezav

Množice elementov imenujemo povezave.

Obstajajo tri vrste povezav:

• permutacije iz n elementi;
• namestitev od n elementi po m;
• kombinacije n elementi po m (m < n).

Opredelitev: permutacija iz n elementov je katera koli urejena množica n elementi.

Z drugimi besedami, to je množica, za katero je označeno, kateri element je na prvem mestu, kateri element na drugem, kateri na tretjem, ..., kateri na n-tem mestu.

PERMUTACIJE

Permutacije so takšne povezave n elemente iz danih elementov, ki se med seboj razlikujejo po vrstnem redu elementov.

Število permutacij n elementov je označeno s Pn.

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

Opredelitev:

Pustiti n- naravno število. Skozi n! (beri "en factorial") označuje število, ki je enako produktu vseh naravnih števil 1 od do n:

n! = 1 2 3 ... n.

če n= 0, po definiciji se predpostavlja: 0! = 1.

FAKTORIAL

Primer #6

Poiščimo vrednosti naslednjih izrazov: 1! 2! 3!

Primer #7

Čemu je enako

A) R 5 ;

b) R 3.

Primer #8

Poenostavite

b) 12! 13 14

V) κ ! · ( κ + 1)

Primer #9

Na koliko načinov je mogoče 8 udeležencev finalne tekme postaviti na osem tekalnih stez?

rešitev.

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

NAMESTITEV

Opredelitev. Namestitev od n elementov z m pokličemo katero koli urejeno množico m elementi, sestavljeni iz elementov n nabor elementov.

Število umestitev od m elementi po n stoji za:

izračunano po formuli:

Primer #9

Učenci 11. razreda se učijo 9 predmetov. V urnik treningov za en dan lahko postavite 4 različne predmete. Koliko različnih načinov je na voljo za načrtovanje dneva?

rešitev.

Imamo 9-elementni sklop, katerega elementi so izobraževalni predmeti. Pri razporejanju bomo izbrali 4-elementni podmnožico (učnih ur) in v njej določili vrstni red. Število takih načinov je enako številu umestitev od devet krat štiri ( m=9, n=4) to je A 94:

Primer #10

Na koliko načinov je mogoče izbrati prefekta in pomočnika prefekta iz razreda 24 dijakov?

rešitev.

Imamo 24-elementni niz, katerega elementi so učenci razreda. Pri volitvah predstojnika in pomočnika predstojnika bomo izbrali 2-elementno podmnožico (učenec) in v njej vzpostavili red. Število takih načinov je enako številu umestitev od devet krat štiri ( m=24, n=2), to je A 242:

KOMBINACIJE

Opredelitev. Kombinacija brez ponovitev iz n elementi po m- poklicali katero koli m elementarna podmnožica n- komplet elementov

Število kombinacij n elementov je označeno z m

in se izračuna po formuli:

Primer #11

Na koliko načinov je mogoče izbrati dva spremljevalca iz razreda 24 učencev?

rešitev.

n =24, m=2

KOMBINACIJE

NAMESTITEV

PERMUTACIJE

Рn = n!

Ugotovite, kateri vrsti povezav pripada naloga.

1. Na koliko načinov lahko razporedite en šolski dan iz 5 različnih ur?

2. V 9.B razredu je 12 učencev. Na koliko načinov je mogoče sestaviti ekipo 4 članov za sodelovanje na matematični olimpijadi?

Ali je upoštevan vrstni red elementov v spoju?

Ali so vsi elementi vključeni v povezavo?

Zaključek: permutacija

Ali je upoštevan vrstni red elementov v spoju?

Ali so vsi elementi vključeni v povezavo?

(to vprašanje ne potrebuje odgovora)

Zaključek: kombinacije

3. Koliko je različnih dvomestnih števil, v katerih se lahko uporabijo števila 1, 2, 3, 4, 5, 6, če morajo biti števila v številu različna?

Ali je upoštevan vrstni red elementov v spoju?

Ali so vsi elementi vključeni v povezavo?

Zaključek: postavitev

poredna opica

Ja, klobuka Miška

Začel igrati kvartet

Stojte, bratje, stopite! -

Opica kriči, - počakaj!

Kako gre glasba?

Ne sediš tako ...

In tako in tako presajeno - spet glasba ne gre dobro.

Tu je bolj kot kdajkoli prej šla njihova analiza

Kdo in kako sedi ...

Koliko različnih aranžmajev glasbenikov je možnih?

rešitev.

Ali je upoštevan vrstni red elementov v spoju?

Ali so vsi elementi vključeni v povezavo?

Zaključek: permutacija

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

P4 = 4! = 4 3 2 1=24

"Vsaka pravilna matematična ideja prej ali slej najde uporabo v tem ali onem poslu"?

permutacije

namestitev

kombinacija

Rezultati reševanja problemov

DOMAČA NALOGA

Naučite se povzetkov in formul.

S. 321 št. 1062

Permutacije so kombinacije, sestavljene iz istih elementov, ki se razlikujejo po vrstnem redu. Število vseh možnih permutacij elementov označujemo s P n, izračunamo pa ga lahko po formuli: Permutacijska formula: P n =n! Pri permutaciji ostane število objektov nespremenjeno, spremeni se le njihov vrstni red, z večanjem števila objektov število permutacij zelo hitro raste in jih je težko vizualno upodobiti.

Naloga 1. Na turnirju sodeluje sedem ekip. Koliko možnosti za razdelitev sedežev med njimi je možnih? Р 7 =7!=1*2*3*4*5*6*7=5040 Odgovor: 5040 Problem 2. Na koliko načinov lahko za okroglo mizo sedi 10 ljudi? P 10 =10! = = 1*2*3*4*5*6*7*8*9*10 = Odgovor:

Naj bo n različnih predmetov. Izmed njih bomo izbrali m predmetov in jih na vse možne načine prerazporedili med seboj. Nastale kombinacije imenujemo postavitve n objektov po m, njihovo število pa je enako: Pri postavljanju se spremenita tako sestava izbranih objektov kot njihov vrstni red. Formula umestitve:

Naloga: Na koliko načinov lahko tri bone za en sanatorij razdelimo med pet ljudi? Ker se boni zagotavljajo enemu zdravilišču, se možnosti razdeljevanja med seboj razlikujejo za vsaj eno osebo. Zato je število načinov distribucije Odgovor: 10 načinov.

Naloga: V delavnici dela 12 ljudi: 5 žensk in 7 moških. Na koliko načinov je mogoče sestaviti brigado 7 ljudi, da so v njej 3 ženske? Od petih žensk je treba izbrati tri, zato je število izbirnih metod. Ker je potrebno izbrati štiri moške od sedmih, potem je število načinov za izbiro moških Odgovor: 350