Lehetséges kombinációk. Kombinatorikus algoritmusok: kombinációs index, részhalmaz index

Közeledett a tél, és Khoma és Suslik úgy döntöttek, hogy felhalmoznak borsót. Egész nap az istállóhoz szaladgáltak, és több hüvelyt hordtak: Khomát (négy éves) és Suslikot (kettőt). Estére megszámolták az összes betakarított hüvelyt, és azon töprengtek, hogyan osztják fel most ezt a borsót. Khoma azzal érvelt, hogy ha kétszer annyit húz egyszerre, mint Suslik, akkor kétszer annyi borsót kell kapnia. Suslik ezt joggal kifogásolta, hogy egyrészt Khoma sebessége észrevehetően alacsonyabb, mint Susliké, másrészt, ki tudja, lehet, hogy Khoma csak egyszer-kétszer szökött el, a többi időben pedig tétlenkedett...

Segíts barátaidnak legalább egy kicsit megérteni ezt a nehéz helyzetet. Határozza meg az összes lehetséges lehetőséget, hogy hány hüvelyt hozott Suslik és hány Khomát.

Beviteli adat

Az első sorban egy természetes páros szám található M – az ellopott hüvelyek száma, 2 ≤ M ≤ 1000.

Kimenet

A Suslik és Khoma által hozott hüvelyek mennyiségének minden lehetséges kombinációja, soronként egy kombináció. Mindegyik kombináció két, szóközzel elválasztott, nem negatív egész számot jelöl: az első szám a Suslik által, a második pedig a Khoma által hozott hüvelyek száma. Rendezd a kombinációkat az első szám szerinti csökkenő sorrendbe.

Tesztek

Beviteli adat	Kimenet
6	\\ 6 \; 0 \\ 2 \; 4
11	\\ 11\;0 \\ 7\;4 \\ 3\;8
18	\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16

Programkód

#beleértve névtér használata std ; int main()( int a, b = 0; cin >> a ; míg (a >= 0 ) ( cout<< a << " " << b << "\n" ; a -= 4; b += 4; return 0 ;

A probléma megoldása

Legyen a a Homa által hozott hüvelyek száma, b pedig a Suslik által hozott hüvelyek száma. Mivel a probléma körülményei szerint Khoma csak négy hüvelyt hordozott, a = a-4 és b = b + 4-et fogjuk figyelembe venni, hogy így számba vegyük a Suslik és Khoma által hozott hüvelyek számának összes lehetséges kombinációját. Használjunk hurkot is míg, amely megismétli a fent leírt műveletet \geq 0-ig. A válaszban kiírjuk a barátok által hozott tokok számának összes lehetséges kombinációját, soronként egyet, az első szám csökkenő sorrendjében.

Tekintsük egy adott halmaz mintáinak megszámlálásának problémáját általános formában. Legyen valami készlet N, a következőket tartalmazza n elemeket. Bármely részhalmaz, amelyből áll m elemek sorrendjének figyelembe vétele nélkül, vagy annak figyelembevétele nélkül tekinthetők, pl. a sorrend megváltoztatásakor lépjen át egy másikra m– mintavétel.

Fogalmazzuk meg a következő definíciókat:

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

Elhelyezés ismétlés nélküln elemek általm Ntartalmazómkülönféle elemek.

A definícióból az következik, hogy a két elrendezés mind elemeiben, mind sorrendjében különbözik egymástól, még akkor is, ha az elemek azonosak.

3. tétel. Az ismétlés nélküli elhelyezések száma megegyezik a szorzattal m tényezők, amelyek közül a legnagyobb a szám n . Írd le:

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

Permutációk innenn az elemeket a halmaz különböző sorrendjének nevezzükN.

Ebből a definícióból következik, hogy a két permutáció csak az elemek sorrendjében tér el egymástól, és az elhelyezések speciális esetének tekinthetők.

4. tétel. Az ismétlés nélküli különböző permutációk számát a képlet számítja ki

Ismétlés nélküli kombinációk

Ismétlés nélküli kombináción elemek általm egy halmaz bármely rendezetlen részhalmazát meghívjukNtartalmazóm különféle elemek.

A definícióból az következik, hogy a két kombináció csak elemekben tér el egymástól.

5. tétel. Az ismétlés nélküli kombinációk számát a következő képletek egyikével számítjuk ki:

1. példa. 5 szék van a szobában. Hányféleképpen helyezheted el őket?

a) 7 fő; b) 5 fő; c) 3 fő?

Megoldás: a) Először is ki kell választanod 5 embert a 7-ből, akik székekre ülnek. Meg lehet csinálni
út. Egy adott öt kiválasztásával előállíthat
átrendezések. A szorzási tétel szerint a leszállási módszerek szükséges száma egyenlő.

Megjegyzés: A probléma csak a szorzattétel segítségével oldható meg, a következő érveléssel: az 1. székre 7, a 2. székre 6, a 3. -5, a 4. -4 és az 5. th -3. Ekkor 7 ember 5 székre való leültetési módja: . Mindkét módszer megoldása konzisztens, hiszen

b) A megoldás kézenfekvő -

V) - az elfoglalt székek választásainak száma.

- az ülőhelyek száma három fő részére három kiválasztott széken.

A választások teljes száma .

Nem nehéz ellenőrizni a képleteket
;

;

A következőből álló halmaz összes részhalmazának száma n elemeket.

Ismételje meg az elhelyezéseket

tól ismétléssel történő elhelyezésseln elemek általm egy halmaz minden rendezett részhalmazát meghívjukN, a következőket tartalmazzam elemeket úgy, hogy ebbe a részhalmazba tetszőleges elem kerüljön 1-tőlmalkalommal, vagy teljesen távol marad.

Az ismétlődő elhelyezések számát jelöli és a következő képlettel számítjuk ki, amely a szorzási tétel következménye:

2. példa. Legyen N = (a, b, c) három betűből álló halmaz. Nevezzük szónak az ebben a halmazban szereplő bármely betűkészletet. Határozzuk meg, hogy hány 2 hosszúságú szó készíthető ezekből a betűkből:
.

Megjegyzés: Nyilván az ismétlődő elhelyezések is számításba jöhetnek, amikor
.

3. példa. Az (a, b) betűket kell használni az összes lehetséges 3 hosszúságú szó létrehozásához. Hányféleképpen lehet ezt megtenni?

Válasz:

Kombinációk száma

Kombináció tól től nÁltal k készletnek nevezik k adatokból kiválasztott elemek n elemeket. Azok a halmazok, amelyek csak az elemek sorrendjében (de nem összetételükben) különböznek egymástól, azonosnak számítanak, ezért különböznek a kombinációk az elhelyezésektől.

Explicit képletek

A kombinációk száma nÁltal k egyenlő a binomiális együtthatóval

Fix értékért n a kombinációk számának függvénye az ismétlésekkel nÁltal k ez:

Az ismétlésekkel rendelkező kombinációk számának kétdimenziós generáló függvénye:

Linkek

• R. Stanley Enumeratív kombinatorika. - M.: Mir, 1990.
• Számítsa ki a kombinációk számát online

Wikimédia Alapítvány. 2010.

Nézze meg, mi a „Kombinációk száma” más szótárakban:

70 hetven 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Factorizálás: 2×5×7 Római jelölés: LXX Bináris: 100 0110 ... Wikipédia

Fényszám, feltételes szám, amely egyértelműen kifejezi a külsőt körülmények a fényképezés során (általában a téma fényereje és a felhasznált fényképészeti anyag fényérzékenysége). Az E. h bármely értéke többször is kiválasztható. rekeszszám kombinációk ...... Nagy enciklopédikus politechnikai szótár

A szám olyan alakja, amely megkülönböztet két objektumot egyetlen objektumhoz és sok objektumhoz képest is. Ez a forma nem létezik a modern oroszban, de hatásának maradványai megmaradnak. Tehát két tábla kombinációi (vö. többes szám... ... Nyelvészeti szakkifejezések szótára

Kombinatorikus matematika, kombinatorika, a matematikának egy olyan ága, amely egy bizonyos, általában véges halmaz elemeinek adott szabályok szerinti kiválasztásával és elrendezésével kapcsolatos problémák megoldására hivatott. Minden ilyen szabály meghatározza az építés módját...... Matematikai Enciklopédia

A kombinatorikában a by kombinációja egy adott, különböző elemeket tartalmazó halmazból kiválasztott elemek halmaza. Azok a halmazok, amelyek csak az elemek sorrendjében (de nem összetételükben) különböznek egymástól, azonosnak számítanak, ezek a kombinációk ... ... Wikipédia

Olyan események tanulmányozásával foglalkozik, amelyek bekövetkezése nem ismert bizonyossággal. Lehetővé teszi számunkra annak megítélését, hogy egyes események bekövetkezésének ésszerű volt-e másokhoz képest, bár sokszor felesleges számértékeket rendelni az események valószínűségéhez... ... Collier enciklopédiája

1) ugyanaz, mint a matematikai kombinatorikus elemzés. 2) Az elemi matematika egy része, amely egy adott véges objektumhalmazból összeállítható kombinációk számának vizsgálatához kapcsolódik, bizonyos feltételek mellett... ... Nagy Szovjet Enciklopédia

- (görög paradoxos váratlan, furcsa) tág értelemben: az általánosan elfogadott, kialakult véleménytől élesen eltér állítás, a „feltétel nélkül helyesnek” tűnő tagadás; szűkebb értelemben két ellentétes állítás, mert... ... Filozófiai Enciklopédia

- (vagy a bezárások és kizárások elve) egy kombinatorikus képlet, amely lehetővé teszi, hogy meghatározza véges számú véges halmaz egyesülésének számosságát, amelyek általános esetben metszik egymást ... Wikipédia

Egy matematikai elmélet, amely az adott objektumok ismert sorrendben történő elosztásának különböző módjainak meghatározásával foglalkozik; különösen fontos az egyenletelméletben és a valószínűségszámításban. A legegyszerűbb ilyen jellegű feladatok a...... Enciklopédiai szótár F.A. Brockhaus és I.A. Efron

Könyvek

• angol nyelvű tankönyv. Két részben. 2. rész, N. A. Bonk, G. A. Kotiy, N. A. Lukyanova. A könyv az angol tankönyv második része. 20 leckéből, egy leckénkénti nyelvtani könyvből és referencia nyelvtani táblázatokból áll. A kötet az új lexikális...

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 azok, amelyek lehetővé teszik, hogy kiszámítsuk az események alakulására vonatkozó, alapvetően lehetséges különböző forgatókönyvek számát.

A kombinatorika alapképlete

Legyen k elemcsoport, és az i-edik csoport n i elemből áll. Válasszunk ki egy elemet minden csoportból. Ekkor az N=n 1 *n 2 *n 3 *...*n k összefüggés határozza meg, hogy egy ilyen választási módot összesen N hány módon lehet meghozni.

1. példa Magyarázzuk meg ezt a szabályt egy egyszerű példával. Legyen két elemcsoport, és az első csoport n 1 elemből, 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 mindegyik 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. Ennél az elemnél n 2 ilyen pár lehet. 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, az összes lehetséges opció n 1 *n 2 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 =6 (mert 1, 2, 3, 4, 5, 6 közül tetszőleges számot vehet fel első számjegynek), n 2 =7 (mert 0-tól tetszőleges számot vehet második számjegynek, 1, 2 , 3, 4, 5, 6), n 3 =4 (mivel a 0, 2, 4, 6 számok bármelyike ​​felvehető harmadik számjegynek).
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 kijelölés ugyanabból a csoportból történik, és a kijelölés utáni elem visszakerül a csoportba. Ekkor az összes kiválasztási mód száma n k. Ezt a kiválasztási módszert a kombinatorikában ún minták visszaküldéssel.

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

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

n elem elhelyezéseinek száma 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 a lakosságból kiválasztott különféle elemek n elemeket.

4. példa A három elem (1, 2, 3) két különböző elrendezése lesz az (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) halmaz. , 2). Az elhelyezések eltérhetnek egymástól mind elemekben, mind sorrendjükben.

A kombinatorikákban az elhelyezések 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 Ha öt páratlan számjegy van, nevezetesen 1, 3, 5, 7, 9, akkor ez a feladat abból áll, hogy az öt különböző számjegy közül kettőt ki kell választani és két különböző pozícióba helyezni, azaz. a feltüntetett 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 a lakosságból kiválasztott különféle elemek 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, egyenként m

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 egy olvasó a hat könyv közül kettőt?

Megoldás: A metódusok száma megegyezik hat két könyv kombinációinak számával, azaz. egyenlő:

n elem permutációi

Definíció 3. Permutáció tól től n az 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 egy sorban elhelyezni hét könyvet 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ával kapcsolatos. P 7 =7!=1*2*3*4*5*6*7=5040 mód van a könyvek elrendezésére.

Vita. 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ámítási elv és maguk a képletek eltérőek. Ha figyelmesen megvizsgálja a definíciókat, észre fogja venni, 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 összessége).

Másodszor, az eredmény a szükséges elemkészletek méretétől függ.

Végül fontos tudni, hogy a halmazban az elemek sorrendje fontos-e számunkra. Magyarázzuk meg az utolsó tényezőt a következő példa segítségével.

9. példa. A szülői értekezleten 20 fő van jelen. 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 érdekel minket a bizottsági listán szereplő nevek sorrendje. Ha ennek eredményeként kiderül, hogy ugyanazok az emberek a részesei, 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, egyenként 5.

A helyzet más lesz, ha kezdetben minden bizottsági tag egy adott munkaterületért felel. Akkor a bizottság azonos listás összetételével esetleg 5 van 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, egyenként 5.

Önellenőrző feladatok
1. 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?

2. Hány olyan ötjegyű szám van, amelyet balról jobbra és jobbról balra ugyanúgy olvasunk?

3. Tíz tantárgy van az osztályban és napi öt óra. Hányféleképpen lehet egy napra ütemtervet készíteni?

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

5. Hányféleképpen helyezhető el nyolc különböző levél nyolc különböző borítékba, ha minden borítékba csak egy betű van?

6. A két matematikusból és hat közgazdászból álló bizottság három matematikusból és tíz közgazdászból álljon. Hányféleképpen lehet ezt megtenni?