A lehetséges választások a 10-ből 4. A kombinatorika képletei. Permutációk. A permutációk számának számolása

Mind az N elem, és egyik sem ismétlődik, akkor ez a permutációk számának problémája. A megoldás egyszerűen megtalálható. Az N elem bármelyike elfoglalhatja az első helyet a sorban, így N opciót kapunk. A második helyen - bármely, kivéve azt, amelyet már használtak az első helyen. Ezért a már megtalált N választási lehetőségek mindegyikéhez (N - 1) van második hely választás, és teljes kombinációkból N*(N - 1) lesz.
Ugyanez megismételhető a sorozat többi elemére is. A legutolsó helyre már csak egy lehetőség maradt - az utolsó megmaradt elem. Az utolsó előtti - két lehetőség, és így tovább.
Ezért N számú nem ismétlődő elem sorozata esetén a lehetséges permutációk egyenlők az 1-től N-ig terjedő összes egész szám szorzatával. Ezt a szorzatot N faktoriálisának nevezzük, és N-vel jelöljük! (Olvassa el: "en faktorial").

Az előző esetben a lehetséges elemek száma és a helyek száma a sorozatban egybeesett, és számuk egyenlő volt N-vel. De lehetséges az a helyzet, hogy a sorozatban kevesebb hely van, mint amennyi lehetséges elem. Más szóval, a mintában lévő elemek száma megegyezik valamilyen M és M számmal< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Először is meg kell számolni, hogy összesen hány lehetséges módon lehet N-ből M elemet sorba rendezni.Az ilyen módokat elhelyezéseknek nevezzük.
Másodszor, a kutatót érdekelheti, hogy hány módon választható ki M elem N közül. Ebben az esetben az elemek sorrendje már nem fontos, de bármelyik két lehetőségnek legalább egy elemben el kell térnie egymástól. . Az ilyen módszereket kombinációknak nevezzük.

Az N-ből M elem szerinti elhelyezések számának meghatározásához ugyanazt az érvelést használhatjuk, mint a permutációk esetében. Az első helyen még mindig lehet N elem, a másodikban (N - 1), és így tovább. De az utolsó helyen a szám lehetőségek nem 1, hanem (N - M + 1), mert az allokáció befejeztével továbbra is marad (N - M) nem használt elem.
Így az M elem feletti elhelyezések száma N-ből egyenlő az (N - M + 1)-től N-ig terjedő összes egész szám szorzatával, vagy ennek megfelelően az N!/(N - M)! hányadosával.

Nyilvánvaló, hogy az N-ből származó M elem kombinációinak száma kevesebb lesz, mint az elhelyezések száma. Minden lehetséges kombinációhoz tartozik egy M! lehetséges elhelyezések a kombináció elemeinek sorrendjétől függően. Ezért ennek a számnak a megtalálásához el kell osztania az N-ből származó M elem feletti elhelyezések számát N-vel!. Más szóval, az N-ből származó M elem kombinációinak száma N!/(M!*(N - M)!).

Barátok! Mivel már megvan ez a halott jegyzetfüzet, felteszek egy olyan problémát, amellyel tegnap három fizikus, két közgazdász, egy a Műszaki és egy bölcsész szakos küzdött. Az egész agyunkat összetörtük, és folyamatosan különböző eredményeket kapunk. Talán vannak közöttetek programozók és matematikai zsenik, ráadásul a probléma általában iskolai és nagyon egyszerű, egyszerűen nem vezetünk le képletet. Mert kiestünk egzakt tudományokés helyette valamiért könyveket írunk és képeket rajzolunk. Sajnálom.

Szóval háttértörténet.

Kaptam egy új bankkártyát, és szokásomhoz híven könnyedén kitaláltam a pin kódját. De nem sorban. Úgy értem, mondjuk a pin kód 8794 volt, és felhívtam a 9748-at. Vagyis diadalmasan kitalálta az összes számot a megadott négyjegyű szám tartalmazza. Nos, igen, nem csak egy szám, hanem egyszerűen alkatrészei at tűnődött. De a számok mind igazak! MEGJEGYZÉS - Véletlenszerűen cselekedtem, vagyis nem kellett a már ismert számokat megfelelő sorrendbe raknom, csak a szellemben cselekedtem: itt van négy számomra ismeretlen szám, és úgy gondolom, hogy ezek között lehet 9, 7, 4 és 8 lehet, és ezek sorrendje nem fontos. Rögtön megkérdeztük magunktól Hány lehetőségem volt(valószínűleg azért, hogy megértsem, milyen klassz, hogy átvettem és kitaláltam). Vagyis hány négy szám kombinációja közül kellett választanom? Aztán persze elkezdődött a pokol. Egész este szétrobbant a fejünk, és végül mindenki abszolút kijött különböző változatok válasz! El is kezdtem ezeket a kombinációkat sorban írni egy füzetbe, ahogy nőttek, de négyszáznál rájöttem, hogy több mint négyszáz van belőlük (mindenesetre ez cáfolta Thrash fizikus válaszát, aki biztosított arról, hogy négyszáz kombináció volt, de még mindig nem egészen világos) – és feladta.

Tulajdonképpen, a kérdés lényege. Mennyi a valószínűsége annak, hogy kitaláljuk (bármilyen sorrendben) egy négyjegyű számban található négy számot?

Illetve nem, fogalmazzuk újra (humanista vagyok, bocsánat, bár mindig is volt egy hatalmas gyengeségem a matematikához), hogy egyre világosabb legyen. Hogyan nem ismétlődő 0 és 9999 közötti sorszámok sorozatában található számkombinációk? ( kérjük, ne keverje össze ezt a "hány kombinációt" kérdéssel nem ismétlődő számok"!!! a számok ismételhetők! Úgy értem, 2233 és 3322 van benne ez az eset ugyanaz a kombináció!

Vagy pontosabban. Négyszer tízből egy számot kell kitalálnom. De nem sorban.

Nos, vagy valami más. Általában azt kell kideríteni, hogy hány lehetőségem volt a számkombinációra, amely a kártya PIN kódját képezte. Segítsetek, jó emberek! Csak kérem, segítsen, ne kezdje el azonnal írni, hogy ezekre 9999 lehetőség van(tegnap mindenkinek ez jutott elsőre) mert ez nonszensz – elvégre abban a perspektívában, ami aggaszt bennünket, az 1234-es, a 3421-es, a 4312-es és így tovább egy és ugyanaz! Hát igen, a számok megismételhetők, mert ott van egy pin kód 1111 vagy ott pl 0007. Elképzelhetsz egy autószámot a pin kód helyett. Tegyük fel, mekkora a valószínűsége annak, hogy kitaláljuk az összes egyjegyű számjegyet, amelyek az autó számát alkotják? Vagy a valószínűségelmélet teljes kiküszöböléséhez - hány numerikus kombináció közül kellett egyet választanom?

Kérem, támogassa válaszait, érvelését néhány pontos formulával, mert tegnap majdnem elment az eszünk. Előre is nagyon köszönöm mindenkinek!

P.S. Egy okos ember, programozó, művész és feltaláló, csak nagyon helyesen javasolta a helyes megoldást a problémára, így néhány percnyi jó hangulatban voltam: " a probléma megoldása a következő: rögeszmés-kényszeres betegsége van, a kezelés a következő: férjhez menni és paradicsomot pucolni. Ha én lennék a helyében, nem a „mi a valószínűsége” kérdéssel foglalkoznék jobban, hanem azzal, hogy „kibaszottul odafigyelek ezekre a számokra”?Általában nincs mit hozzáfűzni :)

Az alábbi számológépet úgy tervezték, hogy n x m elemből álló összes kombinációt generáljon.
Az ilyen kombinációk száma az Elements of Combinatorics kalkulátor segítségével számítható ki. Permutációk, elhelyezések, kombinációk.

A generáló algoritmus leírása a számológép alatt.

Algoritmus

A kombinációk lexikográfiai sorrendben jönnek létre. Az algoritmus a halmaz elemeinek ordinális indexeivel dolgozik.
Tekintsük az algoritmust egy példán keresztül.
A bemutatás megkönnyítése érdekében vegyünk egy öt elemből álló halmazt, amelyek indexei 1-gyel kezdődnek, nevezetesen 1 2 3 4 5.
Minden m = 3 méretű kombinációt elő kell állítani.
Először a megadott m méret első kombinációja inicializálódik - indexek növekvő sorrendben
1 2 3
Ezután az utolsó elemet ellenőrizzük, azaz i = 3. Ha értéke kisebb, mint n - m + i, akkor 1-gyel növeljük.
1 2 4
Az utolsó elemet ismét ellenőrzi, és ismét növeli.
1 2 5
Most az elem értéke egyenlő a lehetséges maximális értékkel: n - m + i = 5 - 3 + 3 = 5, az előző i = 2 elemet ellenőrizzük.
Ha értéke kisebb, mint n - m + i, akkor 1-gyel növekszik, és minden utána következő elemnél az érték megegyezik az előző elem értékével plusz 1-gyel.
1 (2+1)3 (3+1)4 = 1 3 4
Ezután ismét ellenőrizzük, hogy i = 3.
1 3 5
Ezután ellenőrizze, hogy i = 2.
1 4 5
Ezután jön az i = 1 fordulat.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
És tovább,
2 3 5
2 4 5
3 4 5 - az utolsó kombináció, mivel minden eleme egyenlő n - m + i-vel.

Annak ellenére, hogy a PIN-kódok fontos szerepet játszanak a világ infrastruktúrájában, még nem végeztek tudományos kutatást arról, hogyan választják ki az emberek a PIN-kódokat.

A Cambridge-i Egyetem kutatói, Sören Preibusch és Ross Anderson úgy orvosolták a helyzetet, hogy közzétették a világ első kvantitatív elemzését a 4 számjegyű banki PIN-kód kitalálásának nehézségeiről.

A nem banki forrásokból származó jelszókiszivárogtatásra vonatkozó adatok és online felmérések alapján a kutatók azt találták, hogy a felhasználók sokkal komolyabban veszik a PIN-kódok kiválasztását, mint a weboldalak jelszavainak megválasztását: a legtöbb kód szinte véletlenszerű számkészletet tartalmaz. Ennek ellenére a kezdeti adatok között vannak egyszerű kombinációk és születésnapok is - vagyis némi szerencsével a támadó egyszerűen kitalálja az áhított kódot.

A vizsgálat kiindulópontja a RockYou adatbázisból (1,7 millió) származó 4 számjegyű jelszósorozatból, valamint az iPhone képernyőzár programjából származó 200 ezer PIN kódból álló adatbázis volt (az adatbázist Daniel Amitay alkalmazásfejlesztő biztosította). . Az ezekre az adatokra épített grafikonokon érdekes minták jelennek meg - dátumok, évek, ismétlődő számok, sőt 69-re végződő PIN-kódok is. E megfigyelések alapján a tudósok lineárist építettek regressziós modell, amely 25 tényező alapján értékeli az egyes PIN-kódok népszerűségét, például, hogy a kód DDMM dátum-e, növekvő sorrend-e stb. Ezeknek az általános feltételeknek a PIN kódok 79%-a és 93%-a megfelel az egyes készletekben.

Így a felhasználók néhány egyszerű tényező alapján választanak négyjegyű kódokat. Ha így választanánk ki a banki PIN kódokat, akkor mindössze három próbálkozással 8-9%-uk lenne kitalálható! De persze az emberek sokkal figyelmesebbek a bankkódokra. Valós banki adatok nagy halmazának hiányában a kutatók több mint 1300 embert kérdeztek meg, hogy felmérjék, miben térnek el a valós PIN-kódok a már figyelembe vettektől. Tekintettel a vizsgálat sajátosságaira, a válaszadókat nem magukról a kódokról kérdeztük, hanem csak arról, hogy megfelelnek-e a fenti tényezők valamelyikének (növekedés, DDMM formátum stb.).

Kiderült, hogy az emberek valóban sokkal körültekintőbbek a banki PIN-kódok kiválasztásánál. A megkérdezettek hozzávetőleg negyede használ egy bank által véletlenszerűen generált PIN kódot. Több mint egyharmaduk a régi telefonszámával, számával választja PIN-kódját diákigazolvány, vagy más véletlenszerűnek tűnő számkészlet. Az eredmények szerint a kártyabirtokosok 64%-a használ ál-véletlen PIN kódot, ami jóval több, mint a korábbi, nem banki kódokkal végzett kísérletek 23-27%-a. További 5% használ számmintát (pl. 4545), 9% pedig a billentyűzetmintát (pl. 2684). Általánosságban elmondható, hogy egy támadó hat próbálkozással (három ATM-mel és három fizetési terminállal) kevesebb mint 2%-os eséllyel találja ki valaki más kártya PIN kódját.

Tényező	Példa	ringat téged	iPhone	Interjú
*Dátumok*
DDMM	2311	5.26	1.38	3.07
DMYY	3876	9.26	6.46	5.54
MMDD	1123	10.00	9.35	3.66
mmé	0683	0.67	0.20	0.94
ÉÉÉÉ	1984	33.39	7.12	4.95
Teljes		58.57	24.51	22.76
*Billentyűzet minta*
összefüggő	6351	1.52	4.99	-
négyzet	1425	0.01	0.58	-
sarkok	9713	0.19	1.06	-
kereszt	8246	0.17	0.88	-
átlós vonal	1590	0.10	1.36	-
vízszintes vonal	5987	0.34	1.42	-
szó	5683	0.70	8.39	-
függőleges vonal	8520	0.06	4.28	-
Teljes		3.09	22.97	8.96
*digitális minta*
69-el végződik	6869	0.35	0.57	-
csak a számok 0-3	2000	3.49	2.72	-
csak a számok 0-6	5155	4.66	5.96	-
visszatérő párok	2525	2.31	4.11	-
ugyanazok a számjegyek	6666	0.40	6.67	-
csökkenő sorrendben	3210	0.13	0.29	-
növekvő sorrendben	4567	3.83	4.52	-
Teljes		15.16	24.85	4.60
*véletlenszerű számkészlet*		23.17	27.67	63.68

Minden rendben is lenne, de sajnos a válaszadók jelentős része (23%) randevú formájában választ PIN kódot - közel harmaduk pedig a születési dátumát használja. Ez jelentős különbséget jelent, hiszen a válaszadók szinte mindegyike (99%) azt válaszolta, hogy bankkártyákkal együtt tartanak a pénztárcájában különféle azonosító kártyákat, amelyekre ez a dátum rá van nyomtatva. Ha a támadó ismeri a kártyabirtokos születésnapját, akkor hozzáértő megközelítéssel a PIN-kód kitalálásának valószínűsége 9%-ra emelkedik.

A 100 legnépszerűbb PIN kód

0000, 0101-0103, 0110, 0111, 0123, 0202, 0303, 0404, 0505, 0606, 0707, 0808, 0909, 1010, 1101-1103, 1110-1112, 1123, 1201-1203, 1210-1212, 1234, 1956-2015, 2222, 2229, 2580, 3333, 4444, 5252, 5683, 6666, 7465, 7667.

P.S. A gyakorlatban persze sokkal könnyebb a támadónak kémkedni a PIN-kód után, mint kitalálni. De megvédheti magát a kukucskálástól is - még úgy tűnik, reménytelen helyzetben is:

A kombinatorika a matematikának egy olyan ága, amely azt a kérdést vizsgálja, hogy adott objektumokból bizonyos feltételek mellett hány különböző kombináció készíthető. A kombinatorika alapjai nagyon fontosak a véletlenszerű események valószínűségének becsléséhez, mert ezek teszik lehetővé az események alakulására vonatkozó, alapvetően lehetséges különböző forgatókönyvek számának kiszámítását.

Alapvető kombinatorikai képlet

Legyen k elemcsoport, és i-edik csoport n i elemből áll. Minden csoportból válasszunk egy elemet. Akkor teljes szám Az N=n 1 *n 2 *n 3 *...*n k összefüggés határozza meg, hogy egy ilyen választást hogyan lehet meghozni.

1. példa Magyarázzuk meg ezt a szabályt egy egyszerű példával. Legyen két elemcsoport, az első csoport n 1 elemből áll, a második pedig n 2 elemből áll. Hány különböző elempár készíthető ebből a két csoportból úgy, hogy a pár minden csoportból egy elemet tartalmazzon? Tegyük fel, hogy az első csoportból vettük az első elemet, és anélkül, hogy megváltoztattuk volna, végigmentünk minden lehetséges páron, és csak a második csoport elemeit változtattuk meg. Ehhez az elemhez n 2 ilyen pár tartozik. Ezután az első csoportból vesszük a második elemet, és készítsünk hozzá minden lehetséges párt. Lesz n 2 ilyen pár is. Mivel az első csoportban csak n 1 elem van, ezért n 1 *n 2 lehetőség lesz.

2. példa Hány háromjegyű páros szám készíthető a 0, 1, 2, 3, 4, 5, 6 számjegyekből, ha a számjegyek ismételhetők?
Megoldás: n 1 \u003d 6 (mivel az 1, 2, 3, 4, 5, 6 bármelyik számjegyét veheti első számjegynek), n 2 \u003d 7 (mivel a 0-tól bármely számjegyet felveheti második számjegyként, 1 , 2, 3, 4, 5, 6), n 3 \u003d 4 (mivel a 0, 2, 4, 6 bármelyik számjegyét felveheti harmadik számjegyként).
Tehát N=n 1 *n 2 *n 3 =6*7*4=168.

Abban az esetben, ha minden csoport ugyanannyi elemből áll, pl. n 1 =n 2 =...n k =n feltételezhetjük, hogy minden választás ugyanabból a csoportból történik, és az elem a választás után visszatér a csoportba. Ekkor az összes választási mód száma egyenlő n k -vel. Ezt a választási módot a kombinatorikában ún mintákat visszaküldeni.

3. példa Hány négyjegyű szám készíthető az 1, 5, 6, 7, 8 számokból?
Megoldás. Egy négyjegyű szám minden számjegyére öt lehetőség van, tehát N=5*5*5*5=5 4 =625.

Tekintsünk egy n elemből álló halmazt. Ezt a halmazt a kombinatorikában ún Általános népesség.

Elhelyezések száma n elemből m-re

1. definíció. Szállás tól n elemek által m a kombinatorikában bármely megrendelt készlet tól től m az általános lakosságból kiválasztott különféle elemek n elemeket.

4. példa Három elem (1, 2, 3) különböző elrendezései kettesével (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) lesznek halmazok. , 2). Az elhelyezések eltérhetnek egymástól mind elemekben, mind sorrendjükben.

A kombinatorika elhelyezéseinek számát A n m jelöli, és a következő képlettel számítjuk ki:

Megjegyzés: n!=1*2*3*...*n (értsd: "en faktoriális"), ráadásul feltételezzük, hogy 0!=1.

5. példa. Hány olyan kétjegyű szám van, amelyben a tízes számjegy és az egységszámjegy különböző és páratlan?
Megoldás: mert öt páratlan számjegy van, nevezetesen 1, 3, 5, 7, 9, akkor ez a probléma az öt különböző számjegy közül kettő kiválasztására és két különböző pozícióba helyezésére redukálódik, azaz. a megadott számok a következők lesznek:

Definíció 2. Kombináció tól től n elemek által m a kombinatorikában bármely rendezetlen készlet tól től m különféle elemek ben az általános lakosságból választották ki n elemeket.

6. példa. Az (1, 2, 3) halmazhoz a kombinációk: (1, 2), (1, 3), (2, 3).

N elem kombinációinak száma m-rel

A kombinációk számát C n m jelöli, és a következő képlettel számítjuk ki:

7. példa Hányféleképpen választhat ki az olvasó a hat könyv közül kettőt?

Megoldás: Az utak száma megegyezik hat könyv kombinációinak számával kettővel, azaz. egyenlő:

n elem permutációi

Definíció 3. Permutáció tól től n elemeket tetszőlegesnek nevezzük megrendelt készlet ezeket az elemeket.

7a. példa. A három elemből (1, 2, 3) álló halmaz összes lehetséges permutációja: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2).

Az n elem különböző permutációinak számát P n jelöljük, és a P n =n! képlettel számítjuk ki.

8. példa Hányféleképpen lehet egy polcon egymás után hét könyvet elhelyezni különböző szerzőktől?

Megoldás: ez a probléma hét különböző könyv permutációinak számáról szól. P 7 =7!=1*2*3*4*5*6*7=5040 mód van a könyvek elrendezésére.

Vita. Azt látjuk, hogy a lehetséges kombinációk számát különböző szabályok szerint (permutációk, kombinációk, elhelyezések) lehet kiszámítani, és az eredmény más lesz, mert a számolás elve és maguk a képletek különböznek. Ha alaposan megvizsgáljuk a definíciókat, láthatjuk, hogy az eredmény egyszerre több tényezőtől is függ.

Először is, hány elemből tudjuk összevonni a halmazukat (mekkora az elemek általános populációja).

Másodszor, az eredmény attól függ, hogy milyen méretű elemkészletekre van szükségünk.

Végül fontos tudni, hogy a halmazban az elemek sorrendje jelentős-e számunkra. Magyarázzuk meg az utolsó tényezőt a következő példával.

9. példa A szülői értekezleten 20 fő vesz részt. Hány különböző lehetőség van a szülői bizottság összetételére, ha 5 főből kell állnia?
Megoldás: Ebben a példában nem vagyunk kíváncsiak a bizottsági listán szereplő nevek sorrendjére. Ha ennek eredményeként ugyanazok az emberek jelennek meg az összetételében, akkor számunkra ez ugyanaz a lehetőség. Ezért használhatjuk a képletet a szám kiszámításához kombinációk 20 elemből 5.

A helyzet más lesz, ha a bizottság minden tagja kezdetben egy bizonyos munkaterületért felelős. Akkor a bizottság azonos bérszámfejtésével 5 is lehetséges benne! lehetőségek permutációk az számít. A különböző (összetételben és felelősségi körben egyaránt) lehetőségek számát ebben az esetben a szám határozza meg. elhelyezések 20 elemből 5.

Önellenőrzési feladatok
1. Hány háromjegyű páros szám készíthető a 0, 1, 2, 3, 4, 5, 6 számokból, ha a számok ismételhetők?
Mert a harmadik helyen álló páros szám lehet 0, 2, 4, 6, azaz. Négy számjegy. A második hely a hét számjegy bármelyike lehet. Az első hely a nulla kivételével a hét számjegy bármelyike lehet, pl. 6 lehetőség. Eredmény =4*7*6=168.
2. Hány olyan ötjegyű szám van, amely ugyanúgy olvasható balról jobbra és jobbról balra?
Az első hely a 0 kivételével tetszőleges szám lehet, pl. 9 lehetőség. A második hely tetszőleges szám lehet, pl. 10 lehetőség. A harmadik hely is tetszőleges szám lehet, pl. 10 lehetőség. A negyedik és ötödik számjegy előre meghatározott, egybeesik az elsővel és a másodikkal, ezért az ilyen számok száma 9*10*10=900.
3. Tíz tantárgy van az osztályban és napi öt óra. Hányféleképpen lehet beosztani egy napra?

4. Hányféleképpen lehet 4 küldöttet kiválasztani a konferenciára, ha 20 fő van a csoportban?

n = C 20 4 = (20!)/(4!*(20-4)!)=(16!*17*18*19*20)/((1*2*3*4)*(16! ))=(17*18*19*20)/(1*2*3*4)=4845.
5. Hányféleképpen helyezhető nyolc különböző levél nyolc különböző borítékba, ha minden borítékba csak egy betű van?
Az első borítékba a nyolc betű közül egyet, a másodikba a fennmaradó hét betűből egyet, a hatból a harmadikba egyet stb. n = 8! = 1*2*3*4*5*6*7*8 = 40320.
6. Három matematikusból és tíz közgazdászból két matematikusból és hat közgazdászból álló bizottságot kell készíteni. Hányféleképpen lehet ezt megtenni?

KOMBINATORIKA

A kombinatorika a matematikának egy olyan ága, amely valamely alaphalmaz elemeinek adott szabályok szerint történő kiválasztásának és elrendezésének problémáit vizsgálja. A valószínűségszámításhoz a kombinatorika képleteit és alapelveit használják a valószínűségszámításban véletlenszerű eseményekés ennek megfelelően az elosztási törvények beszerzése Véletlen változók. Ez pedig lehetővé teszi a tömeges véletlenszerű jelenségek törvényszerűségének tanulmányozását, ami nagyon fontos a természetben és a technológiában megnyilvánuló statisztikai törvényszerűségek helyes megértéséhez.

Összeadás és szorzás szabályai a kombinatorikában

Összeg szabály. Ha két A és B cselekvés kölcsönösen kizárja egymást, és az A művelet m, B pedig n módon hajtható végre, akkor ezen műveletek bármelyike (akár A, akár B) végrehajtható n + m módon.

1. példa

16 fiú és 10 lány van az osztályban. Hányféleképpen nevezhető ki egy kísérő?

Megoldás

Akár fiút, akár lányt is kijelölhet ügyeletesre, pl. a 16 fiú vagy a 10 lány közül bármelyik lehet ügyeletes.

Az összegezési szabály szerint azt kapjuk, hogy egy ügyeletes 16+10=26 módon osztható be.

Termékszabály. Legyen k szekvenciális végrehajtása szükséges. Ha az első műveletet n 1 módon, a másodikat n 2 módon, a harmadikat n 3 módon lehet végrehajtani, és így tovább egészen a k-adik műveletig, amelyet n k módon lehet végrehajtani, akkor az összes k művelet együtt elvégezhető. teljesített:

módokon.

2. példa

16 fiú és 10 lány van az osztályban. Hányféleképpen lehet két kísérőt kijelölni?

Megoldás

Az első szolgálatban lévő személy lehet fiú vagy lány. Mert osztályban 16 fiú és 10 lány jár, akkor 16 + 10 = 26 módon lehet kinevezni az első ügyeletes tisztet.

Miután kiválasztottuk az első ügyeletes tisztet, a maradék 25 fő közül választhatjuk a másodikat, i. 25 módon.

A szorzási tétellel két kísérő választható ki 26*25=650 módon.

Ismétlés nélküli kombinációk. Kombinációk ismétlésekkel

A kombinatorika klasszikus problémája az ismétlés nélküli kombinációk számának problémája, melynek tartalma a következő kérdéssel fejezhető ki: mennyi módokon tud választ m-től n különféle tárgyakat ?

3. példa

Az ajándékba kapható 10 különböző könyv közül 4-et kell kiválasztanod. Hányféleképpen lehet ezt megtenni?

Megoldás

10 könyvből 4-et kell választanunk, és a választás sorrendje nem számít. Így meg kell találnia a 10 elem kombinációinak számát 4-gyel:

Tekintsük az ismétléses kombinációk számának problémáját: n mindegyiknek r azonos objektuma van. különféle típusok; mennyi módokon tud választ m() of ezek (n*r) tételek?

4. példa

A cukrászdában 4 féle süteményt árultak: napóleont, eklért, omlós tésztát és puffost. Hányféleképpen vásárolható meg 7 torta?

Megoldás

Mert 7 sütemény között lehetnek azonos fajtájú sütemények, akkor a 7 torta vásárlási módjainak számát a 7-től 4-ig terjedő ismétlődésű kombinációk száma határozza meg.

Elhelyezések ismétlés nélkül. Elhelyezések ismétlésekkel

A kombinatorika klasszikus problémája az ismétlés nélküli elhelyezések számának problémája, melynek tartalma a következő kérdéssel fejezhető ki: mennyi módokon tud választ és hely tovább m más helyeken m-től n különböző tételek?

5. példa

Néhány újság 12 oldalas. Négy fényképet kell elhelyezni ennek az újságnak az oldalain. Hányféleképpen lehet ezt megtenni, ha az újság egyik oldala sem tartalmazhat egynél több fényképet?

Megoldás.

Ebben a feladatban nem csak kiválasztunk fényképeket, hanem az újság bizonyos oldalain helyezzük el azokat, és az újság minden oldalán legfeljebb egy fotó szerepeljen. Így a probléma redukálódik arra a klasszikus problémára, hogy az elhelyezések számát ismétlés nélkül 12 elemből 4 elemmel határozzuk meg:

Így 12 oldalon 4 fotó 11880 módon rendezhető el.

Is klasszikus probléma A kombinatorika az ismétléses elhelyezések számának problémája, melynek tartalma a következő kérdéssel fejezhető ki: mennyi módokon tud Önbhadsereg és hely tovább m más helyeken m-től n elemVal velredi melyik van ugyanaz?

6. példa

A fiú elment a forgatásról társasjáték bélyegek 1-es, 3-as és 7-es számmal. Úgy döntött, hogy ezekkel a bélyegekkel ötjegyű számokat helyez el minden könyvön – egy katalógus összeállításához. Hány különböző ötjegyű számot tud készíteni a fiú?

Permutációk ismétlés nélkül. Permutációk ismétlésekkel

A kombinatorika klasszikus problémája az ismétlés nélküli permutációk számának problémája, melynek tartalma a következő kérdéssel fejezhető ki: mennyi módokon tud hely n különféle tételeket a n különböző helyek?

7. példa

Hány négybetűs „szó” készíthető a „házasság” szó betűiből?

Megoldás

Az általános készlet a "házasság" szó 4 betűje (b, p, a, k). A "szavak" számát ennek a 4 betűnek a permutációi határozzák meg, pl.

Abban az esetben, ha a kiválasztott n elem között ugyanaz van (kiválasztás visszatéréssel), az ismétlődő permutációk számának problémája a következő kérdéssel fejezhető ki: Hányféleképpen rendezhető át n objektum n különböző helyen, ha n objektum között van k különböző típus (k< n), т. е. есть одинаковые предметы.