KOMBINATORIKA

Az óra céljai:

• Tudja meg, mit tanul a kombinatorika
• Tudja meg, hogyan keletkezett a kombinatorika
• Tanulja meg a kombinatorika képleteit, és tanulja meg azokat a feladatok megoldásában alkalmazni

A kombinatorika, mint a matematika ágának megszületése Blaise Pascal és Pierre Fermat szerencsejáték-elméletről szóló munkáihoz kötődik.

Blaise Pascal

Pierre Fermat

A kombinatorikus módszerek fejlesztéséhez nagyban hozzájárult G.V. Leibniz, J. Bernoulli és L. Euler.

G.V. Leibniz

L. Euler.

I. Bernoulli

Lemma. Legyen m elem az A halmazban és n elem a B halmazban. Ekkor az összes különálló pár (a,b) száma, ahol a\in A,b\in B egyenlő mn-nel. Bizonyíték. Valóban, az A halmaz egy elemével n darab ilyen különböző párt alkothatunk, és összesen m elem van az A halmazban.

Elhelyezések, permutációk, kombinációk Tegyük fel, hogy van egy három elemből álló halmazunk: a,b,c. Milyen módon választhatunk kettőt ezek közül az elemek közül? ab,ac,bc,ba,ca,cb.

Permutációk Ezeket minden lehetséges módon átrendezzük (az objektumok száma változatlan marad, csak a sorrendjük változik). Az így kapott kombinációkat permutációknak nevezzük, számuk pedig az PN = n! =1 · 2 · 3 · ... · ( n-1) n

Szimbólum n! faktoriálisnak nevezzük, és az összes 1-től n-ig terjedő egész szám szorzatát jelöli. Értelemszerűen úgy vélik 0!=1 1!=1 A képen látható egy példa n=3 objektum (különböző alakú) összes permutációjára. A képlet szerint pontosan P3=3!=1⋅2⋅3=6 , és így alakul.

Az objektumok számának növekedésével a permutációk száma nagyon gyorsan növekszik, és nehézkessé válik vizuálisan ábrázolni őket. Például 10 elem permutációinak száma már 3628800 (több mint 3 millió!).

Szálláshelyek Legyen n különböző objektum. M objektumot választunk ki belőlük, és minden lehetséges módon átrendezzük őket egymás között (azaz a kiválasztott objektumok összetétele és sorrendje is változik). Az így kapott kombinációkat n objektum elhelyezésének nevezzük m-re, és számuk egyenlő Aⁿm =n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)

Meghatározás. Ha n különböző elemből álló halmazt helyezünk m elem fölé (m ≤ n) hívott kombinációk , amelyek adott n elemből m elemmel állnak össze, és vagy magukban az elemekben, vagy az elemek sorrendjében különböznek.

Kombinációk Legyen n különböző objektum. Minden lehetséges módon m objektumot fogunk kijelölni belőlük (vagyis a kiválasztott objektumok összetétele változik, de a sorrend nem fontos). Az így kapott kombinációkat n objektum kombinációinak nevezzük m-rel, és számuk egyenlő Cmn=n!(n−m)!⋅m!

Példa n=3 objektum (különböző alakú) összes kombinációjára m=2- értékkel az alábbi képen. A képlet szerint pontosan C23=3!(3−2)!⋅2!:3!=3 kell. Jól látható, hogy mindig kevesebb kombináció van, mint elhelyezés (mert az elhelyezéseknél a sorrend fontos, a kombinációknál nem), és pontosan m-ben van! alkalommal, vagyis a relációs képlet helyes: Amn=Cmn⋅Pm.

1. módszer. Egy játékban 2 fő vesz részt, ezért ki kell számolni, hogy a 15-ből hányféleképpen lehet kiválasztani 2 főt, és az ilyen párok sorrendje nem fontos. A képlet segítségével megkeressük n különböző elem kombinációinak számát (minták, amelyek csak összetételben különböznek) m elemenként

n!= 1⋅ 2 ⋅3⋅...⋅ n, n=2 esetén m=13.

2. módszer. Az első játékos 14 játszmát játszott (a 2., 3., 4. és így tovább 15-ig), a 2. játékos 13 meccset (3., 4. stb. 15.-ig), kizárjuk, hogy már volt egy játék az elsővel), 3. játékos - 12 meccs, 4. - 11 meccs, 5 - 10 meccs, 6 - 9 meccs, 7 - 8 meccs, 8 - 7 meccs,

a 15. pedig már mindenkivel játszott.

Összesen: 14+13+12+11+10+9+8+7+6+5+4+3+2+1=105 meccs

VÁLASZ. 105 párt.

Matematika tanár Aksenova Svetlana Valerievna

Bugrovskaya középiskola a Leningrádi régió Vsevolozhsky kerületében

dia 1

2. dia

3. dia

4. dia

5. dia

6. dia

7. dia

8. dia

9. dia

10. dia

dia 11

dia 12

dia 13

14. dia

dia 15

16. dia

17. dia

18. dia

19. dia

20. dia

dia 21

dia 22

dia 23

dia 24

A "Diszkrét elemzés. Kombinatorika. Permutációk" témájú előadás teljesen ingyenesen letölthető honlapunkról. Projekt tárgya: Informatika. A színes diák és illusztrációk segítenek fenntartani az osztálytársai vagy a közönség érdeklődését. A tartalom megtekintéséhez használja a lejátszót, vagy ha le szeretné tölteni a jelentést, kattintson a megfelelő szövegre a lejátszó alatt. Az előadás 24 diát tartalmaz.

Bemutató diák

dia 1

Diszkrét elemzés

3. előadás Kombinatorika. Permutációk

2. dia

Permutációk

Legyen adott egy n elemű halmaz. Ezen elemek sorrendjét permutációnak nevezzük. Néha hozzáadódik az „n-ből n elemből”. Általában egyetlen, alapvető vagy természetes sorrendet különböztetnek meg, amit triviális permutációnak neveznek. Az A halmaz elemei számunkra nem érdekesek. Gyakran 1-től n-ig vagy 0-tól n-1-ig terjedő egész számokat veszünk elemnek. Jelölje n elem permutációinak halmazát Pn-nel, számosságát pedig Pn-nel. Tegyük fel ugyanazt a három kérdést: mi Pn egyenlő, hogyan iterálhatjuk át Pn elemeit, hogyan kell újraszámozni őket.

3. dia

Tétel a permutációk számáról

n elem permutációinak száma n! - 1-től n-ig terjedő számok szorzata. (n! n-tényezős olvas) Bizonyítás. Indukcióval. n=1 esetén a képlet nyilvánvalóan helyes. Legyen igaz n-1-re, bebizonyítjuk, hogy n-re is igaz. A rendezés első eleme n módon választható, a többi pedig a kiválasztott első elemhez rendelhető hozzá. Ezért a Pn= Pn-1n képlet helyes. Ha Pn-1=(n-1)!, akkor Pn=n!

4. dia

Permutációs számozás

A permutációk felsorolásához a Pn halmazt egy az egyben leképezzük egy másik Tn halmazra, amelyen sokkal könnyebb lesz a felsorolás, majd bármely pPn elemhez a Tn-beli képének számát vesszük számnak. . A Tn halmaz több Tn =(0:(n-1))(0:(n-2) ... (0) numerikus szegmens közvetlen szorzata, vagyis Tn minden eleme egy halmaz. nemnegatív számok i1, i2, …, in-1, in és iknk.

5. dia

Kijelző

Vegyünk egy permutációt, és írjunk mellé egy triviális permutációt. Első indexként a triviális permutációban az első elem helyét foglaljuk el (nullától számolva). Egy triviális permutáció helyett írjunk egy sztringet a megmaradt karakterekből. Második indexként vegye át a permutáció második elemének helyét ebben a sorban. Ismételjük meg a folyamatot a végéig. Nyilvánvaló, hogy a k-adik index kisebb lesz, mint a k-adik sor hossza, az utolsó index pedig nulla lesz. Nézzük meg ezt a folyamatot egy példán keresztül.

6. dia

Kijelző példa

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 gbebeg 2 2 0 1 2 2 20 20 20 20 Nyilvánvaló, hogy ez a folyamat reverzibilis, és az inverz leképezés az indexek halmazából állítja elő a kezdeti permutációt.

7. dia

A Tn halmaz számozása

A megrendelt készletek bármely közvetlen terméke változó alapú számrendszernek tekinthető. Gondoljon vissza az első előadás második példájára, vagy vegyen egy régi méretskálát: 1 yard = 3 láb, 1 láb = 12 hüvelyk, 1 hüvelyk = 12 sor, 1 sor = 6 pont. (2, 0, 4, 2, 3) = 2 yard 0 láb 4 hüvelyk 2 vonal 3 pont, hány pont ez? Számolni kell (ezt nevezik Horner sémájának) (((2  3+0)  12+4)  12+2)  6+3

8. dia

A Tn - 2 halmaz számozása

A # képletet, amely megkeresi az i1, i2, ..., in-1, in indexek halmazának számát, szívesebben írjuk rekurzív kifejezések formájában #(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(üres,0) = 0; E képlet szerint #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). Van 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;

9. dia

Indexkészletek iterálása

A fentiek alapján a permutációkat könnyű felsorolni: minden indexkészletet fel kell sorolni, és minden halmazhoz létre kell hozni a megfelelő permutációt. Az indexhalmazok számbavételéhez megjegyezzük, hogy valójában mindegyik halmaz egy szám rekordja egy változó bázisú speciális számrendszerben (a rendszert faktoriálisnak nevezzük). Az 1-es hozzáadásának szabályai ebben a rendszerben majdnem olyan egyszerűek, mint a binárisban: az utolsó bittől kezdve próbáljunk meg hozzáadni 1-et az aktuális bithez, majd ha lehetséges, adjunk hozzá 1-et a leállításhoz. Ha ez nem lehetséges, írja be a nulla bitet, és lépjen a következő bitre.

10. dia

Indexkészletek iterálása – 2

Tekintsük a következő példát: 7 6 5 4 3 2 1 Ezek a változó alapok 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Vegye figyelembe, hogy a 3 4 4 2 2 1 0-ban minden sor 3 4 4 3 0-val kezdődik. 0 0 ugyanaz, mint az előzőben, 3 4 4 3 0 1 0 ezután jön az elem, szigorúan 3 4 4 3 1 0 0 nagyobb, . . . , és 3 4 4 3 1 1 0 az alábbiak nem lényegesek. 3 4 4 3 2 0 0 Ezért minden 3 4 4 3 2 1 0 sor lexikográfiailag nagyobb, mint az előző 3 5 0 0 0 0 0. sora. 3 5 0 0 0 1 0

dia 11

Permutációk lexikográfiai felsorolása tétel

A leírt algoritmus a permutációkat lexikográfiai növekvő sorrendben sorolja fel. Bizonyíték. Elég megmutatnunk, hogy ha két I1 és I2 indexhalmazunk van, és I1 lexikográfiailag megelőzi az I2-t, akkor a (I1) permutáció lexikográfiailag megelőzi (I2). Ezek a permutációk egymás után jönnek létre, és amíg I1 és I2 egyezik, addig permutációik is megegyeznek. A nagyobb indexérték nagyobb elemnek felel meg.

dia 12

Közvetlen algoritmus permutációk lexikográfiai felsorolására

Vegyünk néhány p permutációt, és közvetlenül megtaláljuk a lexikográfiailag következőt. Vegyük az elejét – az első k elemet. Kiterjesztései közül ismert a minimum, amelyben minden elem növekvő sorrendben, és a maximum, amelyben csökkenő sorrendben van elrendezve. Például a p =(4, 2, 1, 7, 3, 6, 5) permutációban a (4, 2, 1) összes kiterjesztése (3, 5, 6, 7) és (7, 6, 5, 3). A meglévő folytatás kisebb, mint a maximum, és a 3. elem továbbra is változatlanul hagyható. És a 4. is. Az 5-öst pedig változtatni kell. Ehhez a fennmaradó elemekből sorba kell venni a következőt, fel kell tenni az 5.-re és hozzá kell rendelni a minimális folytatást. Kiderül (4, 2, 1, 7, 5, 3, 6).

dia 13

Közvetlen algoritmus a permutációk lexikográfiai felsorolására - 2

Jegyezzük fel a következő permutációkat. (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)

14. dia

Az algoritmus formális leírása

Működési állapot: A p permutáció és a logikai előjel aktív. Kezdeti állapot: triviális permutációt írunk, és isActive = True. Normál lépés: Ha aktív, adja vissza a permutációt eredményként. A végétől haladva keresse meg a legnagyobb monoton csökkenő utótagot a permutációban. Legyen k az utótag előtti pozíció. Tedd isActive:= (k > 0). Ha aktív, akkor keresse meg az utótag legkisebb elemét, amely meghaladja a pk-t, cserélje fel pk-ra, majd „fordítsa meg” az utótagot.

dia 15

Egy másik permutációs algoritmus

Most próbáljuk meg felsorolni a permutációkat úgy, hogy két egymást követő permutáció alig tér el egymástól. Milyen kevés? Egy elemi transzpozícióval, amelyben két szomszédos elem felcserélődik. Lehetséges? Megmutatjuk egy ilyen algoritmus sematikus diagramját, érdekes lesz számunkra. Képzeljünk el n-1 elemi „mechanizmust”, amelyek mindegyike mozgatja elemét a halmazon belül. A mechanizmus minden lépésnél balra vagy jobbra tolódik. Az irány megváltozik, amikor az elem eléri a szélét. Az irányváltáshoz egy lépés kell, amely során a következő mechanizmus tesz egy lépést, amely azonban irányt is változtathat.

16. dia

Egy másik permutáció-felsorolási algoritmus -2

Lássunk egy példát. 1 2 3 4 máj, amelyek játéka 1 2 3 4 5 soron 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 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 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 d c e b a a c b d e b d a c e b a a c d b e a d c egy e B A C egy d B e a d c e a b a

17. dia

A permutációk listája. egy

függvény ExistsNextPerm(var kCh: integer): Logikai; var iV,iP,iVC,iPC: egész szám; beginresult:= False; iV:= nV esetén 2 do if count

18. dia

A páronkénti szorzatok minimális összegének problémája

Legyen két n számból álló halmaz, mondjuk (ak|k1:n) és (bk|k1:n) . Ezeket a számokat párokra osztjuk (ak,bk), és kiszámítjuk a páronkénti szorzataik k1:n akbk összegét. Módosíthatja a számozást (ak) és (bk). Olyan számozást kell választani, amelynél az összeg minimális. Ebben a feladatban rögzíthetünk néhány számozást (ak) és (bk), és kereshetünk egy  permutációt, amelyre elérjük a k1:n akb(k) összeg minimumát. A számozást akkor választjuk ki, ha az (ak) növekvő sorrendben, a (bk) pedig csökkenő sorrendben van.

19. dia

Tétel a páronkénti szorzatok minimális összegéről

A páronkénti szorzatok összegének minimumát triviális permutációval érjük el. Bizonyíték. Tegyük fel, hogy van két olyan k és r index, amelyre ak 0, azaz. ar br + ak bk > ar bk + ak br . Számozásunkban (ak) növekvő sorrendben vannak. Ha (bk) nincs növekvő sorrendben, akkor van egy k és r pár, ahogy fentebb említettük. A bk és br átrendezésével erre a párra csökkentjük az összeg értékét. Ezért az optimális megoldásban (bk) növekvő sorrendben vannak. Ezzel az egyszerű tétellel többször is találkozni fogunk a következőkben.

20. dia

A maximálisan növekvő részsorozat probléma

Adott egy n hosszúságú számsorozat (ak|k1:n). Meg kell találni a legnagyobb hosszúságú sorozatát, amelyben a számok (ak) növekvő sorrendben mennének. Például a 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9 sorozatban a maximális részsorozat 2, 11, 14, 16 lesz. , 17, 25, 37, 41 Ez a probléma a permutációkkal kapcsolatos, mivel az eredeti sorozat lehet permutáció. A probléma megoldásának bemutatására szorítkozunk, az algoritmus formalizálását és indoklását a hallgatóságra bízzuk.

dia 21

A maximális növekvő részsorozat megkeresése

A miénket a lehető leggazdaságosabban bontjuk fel csökkenő szekvenciákra (példa módosítva) a legfelső sorokra, ahol nem bontja meg a sorrendet. Vegyük az alsó sor számát, a 21-et. Miért van a 8. sorban? A 19 zavarja, de a 17 zavarja a 19-et. És a 16 zavarja meg. És így tovább. A 9, 11, 14, 16, 17, 19, 21 sorozat növekszik, és 7 hosszúságú. Minden nagyobb hosszúságú sorozat két számot tartalmaz egy sorból Dirichlet-elv) és nem lehet növekvő.

dia 22

Az inverziók minimális számának problémája

Adott egy n hosszúságú számsorozat (ak|k1:n). Az inverzió egyes részkarakterláncainak tükörtükrözése, egy folytonos részsorozat, amelyet helyben hajtanak végre, és a sorozat elemeit a minimális számú inverzióhoz növekvő sorrendbe kell rendezni. Például egy "szilárd" permutációt így lehet átalakítani (a piros betűk átrendeződnek, a nagyok már a helyükön vannak)

dia 23

Vizsgakérdések

Permutációk. Felsorolásuk és számozásuk. A skalárszorzat minimumának problémája. A legnagyobb növekvő részsorozat problémája.

dia 24

1. Kétirányú átmenet permutáció  szám 2. Keress egy permutációt, amely adott számú lépésnyire van az adotttól. 3. Permutációk felsorolása elemi transzpozíciókkal. 4. Futtasson példát a skalárszorzat minimumának problémájára.

Tippek egy jó prezentáció vagy projektjelentés elkészítéséhez

1. Próbálja bevonni a közönséget a történetbe, alakítson ki interakciót a közönséggel a vezető kérdések, a játékrész segítségével, ne féljen viccelni és őszintén mosolyogni (adott esetben).
2. Próbáld meg saját szavaiddal elmagyarázni a diát, adj hozzá további érdekességeket, nem csak a diákról kell elolvasnod az információkat, a közönség maga is elolvashatja.
3. Nem kell túlterhelni a projektdiáit szövegblokkokkal, több illusztráció és minimális szöveg jobban közvetíti az információkat és felkelti a figyelmet. Csak a legfontosabb információk szerepeljenek a dián, a többit jobb szóban elmondani a hallgatóságnak.
4. A szövegnek jól olvashatónak kell lennie, különben a közönség nem láthatja a közölt információkat, nagymértékben elvonja a figyelmét a történetről, megpróbál legalább valamit kitalálni, vagy teljesen elveszíti érdeklődését. Ehhez ki kell választani a megfelelő betűtípust, figyelembe véve, hogy hol és hogyan sugározzák a prezentációt, valamint ki kell választani a megfelelő háttér és szöveg kombinációt.
5. Fontos, hogy ismételje meg a beszámolót, gondolja át, hogyan köszönti a hallgatóságot, mit mond először, hogyan fejezi be az előadást. Minden tapasztalattal jön.
6. Válassza ki a megfelelő ruhát, mert. A beszélő ruházata is nagy szerepet játszik beszédének észlelésében.
7. Próbáljon magabiztosan, folyékonyan és koherensen beszélni.
8. Próbáld meg élvezni az előadást, így nyugodtabb és kevésbé szorongó lehetsz.

A „Permutációk” című előadás oktatási anyagokat mutat be egy iskolai leckéhez ebben a témában. Az előadás tartalmazza a permutációk definícióját, szemléltető példákat a művelet jelentésének megértéséhez, a matematikai apparátus leírását a permutációkkal kapcsolatos problémák megoldására, példákat a problémák megoldására. Az előadás feladata, hogy az oktatási anyagot kényelmes, közérthető formában közvetítse a tanulókhoz, hozzájáruljon annak jobb megértéséhez, memorizálásához.

Az előadás speciális technikákkal segíti a tanárt egy új téma magyarázatában. Az oktatási anyagok előre strukturáltak. Animációs effektusok segítségével példákat, feladatokat mutatnak be, hangsúlyozva a bemutató során a példák, feladatok fontos jellemzőit. A fontos fogalmakat színnel kiemeljük, hogy könnyebben megjegyezhetőek legyenek.

Az óra témájának bemutatása után a tanulók bemutatják a permutációk definícióját, mint a legegyszerűbb kombinációkat, amelyek egy bizonyos elemkészletből létrehozhatók. A szöveg felkiáltójellel van kiemelve, mert fontos megjegyezni.

Az alábbiakban egy példa látható a színes ceruzák permutációira, amelyek eltérő sorrendben helyezhetők el. Ehhez a ceruzákat a színnevük kezdőbetűjével írják alá: S, K, Zh. Egy animált bemutató segítségével egyértelműen bemutatják a ceruzák sorrendbe helyezésének lehetőségeit. Az egyik dián először kék ceruzák kerülnek, mellettük pedig két elhelyezési lehetőség - piros és sárga, sárga és piros. A következő dia bemutatja a ceruzák piros – kék és sárga, sárga és kék – utáni elhelyezésének lehetőségeit. Az utolsó lehetséges opciók a sárga piros és kék, kék és piros után következnek. Vizuális bemutató után a végrehajtott műveletek három elem permutációjaként kerülnek aláírásra. A három elemből álló permutáció pontosabb definíciója egy külön dián található 7. A memóriadobozban kiemelve van az a szöveg, hogy ezen elemek minden egyes elrendezését egy bizonyos sorrendben három elem permutációjának nevezzük.

A 8. dia n elem permutációjának jelölését mutatja - P n . Jelezzük, hogy a három elem permutációit a ceruza példáján részletesen megvizsgáltuk, miközben nyilvánvaló, hogy ilyen permutációk lesznek 6. A permutációk számának matematikai rekordja a dián van jelölve: P 3 =6 . Továbbá a képernyőn látható, hogy létezik egy kombinatorikus szorzási szabály három elem permutációinak számának meghatározására.

A következő dián a permutációs eljárást lépésekre bontjuk, hogy megkapjuk a permutációk számának meghatározására szolgáló szabályt. Jelezzük, hogy a számításhoz a három elem bármelyikét az első helyre kell tenni. Két lehetősége van a második elem kiválasztására. Az egyetlen lehetőség a harmadik elem kiválasztása. Ez azt jelenti, hogy 3 elem permutációinak számát 3.2.1=6 szorzásával kapjuk meg. Megkapjuk a lehetséges permutációk teljes számát. Hasonlóan a permutációs változatok keresésének folyamatához, n elem variabilitását is figyelembe vesszük.

Legyen valamilyen n elemű halmaz. Ehhez n-1 elem egyike a második helyre, n-2 elem közül egy a harmadik helyre kerül, és így tovább. Így levezethetünk egy általános szabályt n elem permutációinak meghatározására: P n =n(n-1)(n-2).….3.2.1.

A 11. dián a P n képlet P n =1.2.3.….(n-2)(n-1)n formában jelenik meg. Így kerül bevezetésre a faktoriális fogalma, melynek jelölése a képlet alatt látható: n!. Példák valamelyik szám faktoriálisának megtalálására: 3!=1.2.3=6, valamint 6!=1.2.3.4.5.6=720. Azt is írja, hogy 1!=1. A permutációk számának n faktoriálisként való meghatározására vonatkozó általános szabály szövege a dia alján található.

A következőkben azt javasoljuk, hogy vegyünk figyelembe néhány problémát a permutációk számának meghatározásához. A 12. dián azt javasoljuk, hogy oldjuk meg a hét golyó hét cellára bontásának számos módját. Jelezzük, hogy a megoldás 7 elem permutációinak számának kiszámítása: P 7 =7!=5040.

A 13. dia a 0, 1, 2, 3 számokból álló négyjegyű számok számának megtalálásának megoldását tárgyalja, miközben az egy számban lévő számok nem ismétlődnek. A megoldást két lépésben adjuk meg - először megkeresik 4 elem összes permutációjának számát, majd kivonják belőlük a permutációk számát, amelyekben a 0 előtt álló számok, tehát a nullától kezdődő számok nem lesznek négyesek. számjegy. Így a megoldás a P 4 -P 3 =4!-3!=18 kiszámítása. Vagyis 18 lehetőség van az ilyen számok kialakítására.

Az utolsó dia a feladat megoldását tárgyalja, amely azt javasolja, hogy megkeressük, hány módon lehet elhelyezni 9 lemezt, amelyek közül 4 piros, hogy a pirosak egymás mellett legyenek. A probléma megoldásának fő nehézsége annak megértése, hogy ezekben a permutációkban a vörös lemezeket egynek kell tekinteni. Így a megoldás a P 6 .P 4 =6!.4!=17280 szorzat megtalálására redukálódik.

A „Permutációk” című előadás célja, hogy vizuálisan kísérje a tanár „Permutációk” témával kapcsolatos magyarázatát. Az oktatási anyag részletes, érthető bemutatása a távoktatásban is hasznos lehet, az ilyenkor figyelembe vett feladatok pedig segítik a tanulót a megoldás önálló megbirkózásában.

A kombinatorika alapjai.

Elhelyezések, permutációk,

kombinációk.

szemtelen majom

Szamár,

Kecske,

Igen, lúdtalpú Mishka

Elkezdett kvartetten játszani

Álljatok meg, testvérek, álljatok meg! -

Majom kiabál, - várj!

Hogy megy a zene?

Nem ülsz így...

És így, és úgy átültetve - megint nem megy jól a zene.

Itt minden eddiginél jobban ment az elemzésük

És viták

Ki és hogyan üljön...

tud:

• A kombinatorika három legfontosabb fogalmának meghatározása:
• n elem elhelyezése m-rel;
• n elem kombinációi m-rel;
• n elem permutációja;
• alapvető kombinatorikus képletek

képesnek lenni:

• a feladatok „permutációra”, „kombinációra”, „elhelyezésre” való megkülönböztetése egymástól;
• az alapvető kombinatorikai képleteket alkalmazza a legegyszerűbb kombinatorikai feladatok megoldásában.

Egy csomó

Egy halmazt néhány homogén objektum egyetlen egésszé egyesülése jellemez.

A halmazt alkotó objektumokat a halmaz elemeinek nevezzük.

A halmazt úgy fogjuk felírni, hogy az elemeit zárójelbe tesszük ( a, b, c, … , e, f}.

Egy halmazban az elemek sorrendje nem számít, így ( a, b} = {b, a}.

Olyan halmazt hívunk meg, amely nem tartalmaz elemet üres készletés ø szimbólummal jelöljük.

Egy csomó

Ha a halmaz minden eleme A eleme a B halmaznak, akkor azt mondjuk, hogy a halmaz A a halmaz egy részhalmaza V.

Egy csomó ( a, b) a halmaz ( a, b, c, … , e, f}.

Jelölve

Sorolja fel a halmaz egy részhalmazának lehetséges opcióit ( 3 , 4 , 5 , 7, 9 }.

A kombinatorika a matematikának egy olyan ága, amely azt a kérdést vizsgálja, hogy egy adott halmazhoz tartozó elemekből hány különböző kombináció készíthető bizonyos feltételek mellett.

A kombinatorika a matematikának egy fontos ága, amely a rögzített halmazból származó elemek elrendezésének, rendezésének, kiválasztásának és eloszlásának mintáit vizsgálja.

SZUMMAZÁSI SZABÁLY

Ha két egymást kizáró cselekvés végezhető a szerint kés m módokon, akkor ezen műveletek egyike végrehajtható k+m módokon.

1. példa

A városból B városba 12 vonattal, 3 repülővel, 23 busszal lehet eljutni. Hányféleképpen juthatsz el A városból B városba?

Megoldás

2. példa

Egy dobozban n színes golyó van. Véletlenszerűen vegyen ki egy labdát. Hányféleképpen lehet ezt megtenni?

Megoldás. Biztosan, n módokon.

Most ez az n golyó két dobozban van elosztva: Az elsőben m labdák, a másodikban k. Véletlenszerűen vegyél ki egy labdát bármelyik dobozból. Hányféleképpen lehet ezt megtenni?

Megoldás.

A labdát az első dobozból lehet húzni m különféle módokon, a másodiktól kezdve k különböző módokon összesen N = m + k módokon.

TERMÉKSZABÁLY

Hagyja, hogy két egymás után végrehajtott művelet hajtható végre ennek megfelelően kés m módjai Akkor mindkettőt meg lehet tenni k ∙ m módokon.

3. példa

A tornán 8 jégkorongcsapat vesz részt. Hányféleképpen lehet elosztani az első, második és harmadik helyet?

Megoldás

4. példa

Hány kétjegyű szám írható fel decimális jelöléssel?

Megoldás. Mivel a szám kétjegyű, a tízesek száma ( m) kilenc érték valamelyikét veheti fel: 1,2,3,4,5,6,7,8,9. Egységek száma ( k) ugyanazokat az értékeket veheti fel, és emellett egyenlő lehet nullával. Ebből következik tehát m= 9, és k= 10. Összesen kétjegyű számokat kapunk

N= m · k= 9 10 =90.

5. példa

A diákcsoportban 14 lány és 6 fiú szerepel. Hányféleképpen választható ki két azonos nemű tanuló különböző feladatok elvégzésére?

Megoldás. A két lány szorzási szabálya szerint 14 13 = 182, két fiú 6 5 = 30 mód közül választhat. Két azonos nemű tanulót kell kiválasztani: két diákot vagy diáklányt. Az ilyen választások összeadási szabálya szerint

N = 182 + 30 = 212.

Csatlakozás típusai

Az elemek halmazait nevezzük vegyületek.

Háromféle kapcsolat létezik:

• permutációk -ból n elemek;
• szállástól n elemek által m;
• kombinációi n elemek által m (m < n).

Meghatározás: permutáció ebből n elemek bármely rendezett halmaza n elemeket.

Vagyis ez egy olyan halmaz, amelynél meg van jelölve, hogy melyik elem van az első helyen, melyik a második, melyik a harmadik, ..., melyik az n-edik.

PERMUTUÁCIÓK

Permutációk vannak ilyen kapcsolatok n adott elemekből olyan elemeket, amelyek az elemek sorrendjében különböznek egymástól.

Az n elem permutációinak számát Pn jelöli.

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

Meghatározás:

Hadd n- természetes szám. Át n! (értsd: "en faktoriális") olyan számot jelöl, amely egyenlő az összes természetes szám 1-től ig szorzatával n:

n! = 1 2 3 ... n.

Ha n= 0, definíció szerint feltételezzük: 0! = 1.

FAKTORIÁLIS

6. példa

Keressük meg a következő kifejezések értékeit: 1! 2! 3!

7. példa

Amivel egyenlő

a) R 5 ;

b) R 3.

8. példa

Egyszerűsítsd

b) 12! 13 14

v) κ ! · ( κ + 1)

9. példa

A döntő futam 8 résztvevője hányféleképpen helyezhető el nyolc futópadon?

Megoldás.

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

SZÁLLÁS

Meghatározás. Szállás tól n elemet m bármely megrendelt halmazt hívják m elemek, elemekből álló n elem halmaz.

Elhelyezések száma innen m elemek által nÁll valamiből:

képlettel számolva:

9. példa

A 11. évfolyam tanulói 9 tantárgyat tanulnak. Az egynapos képzési ütemtervben 4 különböző tantárgyat helyezhet el. Hányféleképpen lehet beosztani egy napot?

Megoldás.

Van egy 9 elemes készletünk, melynek elemei oktatási tárgyak. Az ütemezésnél kiválasztunk egy 4 elemből álló részhalmazt (az órákat), és abban állítjuk be a sorrendet. Az ilyen módok száma megegyezik a kilencből négy elhelyezések számával ( m=9, n=4) vagyis A 94:

10. példa

Hányféleképpen lehet egy 24 fős osztályból prefektust és segédprefektust kiválasztani?

Megoldás.

Van egy 24 elemes készletünk, melynek elemei az osztály tanulói. Az igazgató és a segédvezető megválasztásánál egy 2 elemű részhalmazt (tanulót) választunk és abban állítunk fel sorrendet. Az ilyen módok száma megegyezik a kilencből négy elhelyezések számával ( m=24, n=2), vagyis A 242:

KOMBINÁCIÓK

Meghatározás. Ismétlődés nélküli kombináció n elemek által m- hívott bármelyik m elemi részhalmaz n-elemkészlet

Az n elem kombinációinak számát m-vel jelöljük

és a következő képlettel számítjuk ki:

11. példa

Hányféleképpen lehet két kísérőt kiválasztani egy 24 fős osztályból?

Megoldás.

n =24, m=2

KOMBINÁCIÓK

SZÁLLÁS

PERMUTUÁCIÓK

Рn = n!

Határozza meg, hogy a feladat milyen típusú kapcsolatokhoz tartozik.

1. Hányféleképpen tud beosztani egy tanítási napot 5 különböző órából?

2. A 9B osztályba 12 tanuló jár. Hányféleképpen alakítható ki egy 4 fős csapat a matematikai olimpián való részvételhez?

Figyelembe veszik az elemek sorrendjét az összekapcsolásban?

Minden elem benne van a kapcsolatban?

Következtetés: permutáció

Figyelembe veszik az elemek sorrendjét az összekapcsolásban?

Minden elem benne van a kapcsolatban?

(erre a kérdésre nem kell válaszolni)

Következtetés: kombinációk

3. Hány különböző kétjegyű szám van, amelyben az 1, 2, 3, 4, 5, 6 számok használhatók, ha a számban szereplő számoknak különbözőnek kell lenniük?

Figyelembe veszik az elemek sorrendjét az összekapcsolásban?

Minden elem benne van a kapcsolatban?

Következtetés: elhelyezés

szemtelen majom

Igen, lúdtalpú Mishka

Elkezdett kvartetten játszani

Álljatok meg, testvérek, álljatok meg! -

Majom kiabál, - várj!

Hogy megy a zene?

Nem ülsz így...

És így, és úgy átültetve - megint nem megy jól a zene.

Itt minden eddiginél jobban ment az elemzésük

Ki és hogyan üljön...

Hányféle zenész feldolgozás lehetséges?

Megoldás.

Figyelembe veszik az elemek sorrendjét az összekapcsolásban?

Minden elem benne van a kapcsolatban?

Következtetés: permutáció

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

P4 = 4! = 4 3 2 1 = 24

„Előbb-utóbb minden helyes matematikai ötlet alkalmazásra talál ebben vagy abban az üzletben”?

permutációk

szállás

kombináció

Problémamegoldási eredmények

HÁZI FELADAT

Tanuljon absztraktot és képleteket.

S. 321 1062. sz

A permutációk azonos elemekből álló, sorrendjükben eltérő kombinációk. Az elemek összes lehetséges permutációjának számát P n jelöljük, és a következő képlettel számíthatjuk ki: Permutációs képlet: P n =n! A permutáció során az objektumok száma változatlan marad, csak a sorrendjük változik.Az objektumok számának növekedésével a permutációk száma nagyon gyorsan növekszik és vizuálisan is nehézkessé válik a megjelenítésük.

Feladat 1. Hét csapat vesz részt a tornán. Hány lehetőség van köztük a helyek elosztására? Р 7 =7!=1*2*3*4*5*6*7=5040 Válasz: 5040 2. feladat. Hányféleképpen ülhet 10 ember a kerekasztalnál? P 10 = 10! = = 1*2*3*4*5*6*7*8*9*10 = Válasz:

Legyen n különböző objektum. M tárgyat választunk ki közülük, és minden lehetséges módon átrendezzük őket egymás között. Az így létrejövő kombinációkat n objektum m-es elhelyezésének nevezzük, számuk egyenlő: Elhelyezéskor mind a kiválasztott objektumok összetétele, mind sorrendjük megváltozik. Elhelyezési képlet:

Feladat: Hányféleképpen osztható ki öt ember között három utalvány egy szanatóriumra? Mivel az utalványokat egy szanatórium kapja, az elosztási lehetőségek legalább egy személy esetében eltérnek egymástól. Ezért a terjesztési módok száma Válasz: 10 módon.

Feladat: 12 fő dolgozik a műhelyben: 5 nő és 7 férfi. Hányféleképpen alakítható ki egy 7 fős csapat úgy, hogy 3 nő legyen benne? Az öt nőből hármat kell kiválasztani, tehát a kiválasztási módok száma. Mivel hétből négy férfit kell kiválasztani, a férfiak kiválasztásának módjainak száma Válasz: 350