Az n közül k elem kiválasztásának módjainak száma. Permutációk, elhelyezések és kombinációk

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 paradoxon 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

• Sorsszám. Kompatibilitási horoszkóp. Vágyak. Szenvedély. Fantáziák (kötetszám: 3), Mayer Maxim. Sorsszám. Hogyan készítsünk egyéni numerológiai előrejelzést. A numerológia az egyik legősibb ezoterikus rendszer. Lehetetlen pontosan meghatározni az előfordulásának időpontját. Azonban a…

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 különbözik a sorrendtő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ünk szónak bármely, ebben a halmazban szereplő betűkészletet. Keresse meg a 2 hosszúságú szavak számát, amelyek ezekből a betűkből készíthetők:
.

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:

Számoljuk meg MS EXCEL-ben n elem kombinációinak számát k-val. Képletek segítségével megjelenítjük a lapon a kombinációk összes változatát (a kifejezés angol fordítása: Ismétlés nélküli kombinációk).

K elem n különböző elemének kombinációi olyan kombinációk, amelyek legalább egy elemben különböznek. Például az alábbiakban az ÖSSZES 3 elemből álló kombináció látható egy 5 elemből álló halmazból (1; 2; 3; 4; 5):

(1; 2; 3); (1; 2; 4); (1; 2; 5); (1; 3; 4); (1; 3; 5); (1; 4; 5); (2; 3; 4); (2; 3; 5); (2; 4; 5); (3; 4; 5)

jegyzet: Ez a cikk a kombinációk számának MS EXCEL használatával történő számlálásáról szól. Javasoljuk, hogy az elméleti alapokat egy speciális tankönyvben olvassa el. Rossz ötlet kombinációkat tanulni ebből a cikkből.

A kombinációk és az elhelyezések közötti különbség

A kombinációk összes kombinációjának megjelenítése

A példafájlban képletek jönnek létre, amelyek megjelenítik az adott n és k összes kombinációját.

A halmaz elemszámának (n) és a belőle kiválasztandó elemek számának (k) megadásával képletek segítségével az összes kombinációt megjeleníthetjük.

Feladat

Egy autószállító 4 autót tud szállítani. 7 különböző autó szállítása szükséges (LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo, Lada Largus). Hányféleképpen tölthető meg az első autószállító? Az autó konkrét helye az autószállítóban nem fontos.

Meg kell határoznunk a számot Kombinációk 7 autó 4 helyen egy autószállító. Azok. n=7 és k=4. Kiderült, hogy 35 ilyen opció van =NUMCOMB(7,4).

A kombinatorikában olyan kérdéseket vizsgálnak, hogy adott objektumokból (elemekből) egy adott típusból hány kombináció készíthető.

A kombinatorika, mint ág születése B. Pascal és P. Fermat szerencsejáték-elméleti munkáihoz kötődik. A kombinatorikus módszerek fejlesztéséhez nagyban hozzájárult G.V. Leibniz, J. Bernoulli és L. Euler.

Blaise Pascal (1623–1662) francia filozófus, író, matematikus és fizikus korán megmutatta kiemelkedő matematikai képességeit. Pascal matematikai érdeklődési köre igen változatos volt. Pascal egy dolgot bizonyított
a projektív geometria alaptételei közül (Pascal-tétel), összegző gépet (Pascal-összeadó gépet) tervezett, binomiális együttható számítási módszert adott (Pascal-háromszög), elsőként definiálta és alkalmazta a matematikai indukció módszerét a bizonyításra, jelentős lépést tett az infinitezimális elemzés fejlődésében, fontos szerepet játszott a valószínűségszámítás megjelenésében. A hidrosztatikában Pascal megalkotta alaptörvényét (Pascal törvényét). Pascal „Levelek egy provinciálishoz” című műve a francia klasszikus próza remekműve volt.

Gottfried Wilhelm Leibniz (1646–1716) német filozófus, matematikus, fizikus és feltaláló, jogász, történész és nyelvész. A matematikában I. Newtonnal együtt differenciál- és integrálszámítást fejlesztett ki. Jelentős mértékben hozzájárult a kombinatorikához. Nevéhez különösen számelméleti problémák kapcsolódnak.

Gottfried Wilhelm Leibniznek nem volt lenyűgöző megjelenése, ezért egy meglehetősen egyszerű ember benyomását keltette. Egyik nap Párizsban bement egy könyvesboltba, abban a reményben, hogy megvesz egy könyvet egy ismert filozófustól. Amikor egy látogató erről a könyvről kérdezett, a könyvkereskedő tetőtől talpig megvizsgálta, gúnyosan azt mondta: „Mire van szüksége? Tényleg képes vagy ilyen könyveket olvasni? Mielőtt a tudósnak ideje lett volna válaszolni, maga a könyv szerzője lépett be a boltba a következő szavakkal: „Üdvözlet és tisztelet a Nagy Leibniznek!” Az eladó nem értette, hogy ez valóban a híres Leibniz, akinek könyvei nagy keresletet mutattak a tudósok körében.

A jövőben a következők játszanak fontos szerepet

Lemma. Engedjen be egy elemkészletet, és egy halmazba - elemeket. Ekkor az összes különböző pár száma, ahol egyenlő lesz .

Bizonyíték. Valóban, egy halmaz egy elemével ilyen különböző párokat tudunk alkotni, és összesen egy elemhalmazban.

Elhelyezések, permutációk, kombinációk

Legyen három elemből álló halmazunk. Milyen módon választhatunk ki két elem közül? .

Meghatározás. Különböző elemek halmazának elemenkénti elrendezései olyan kombinációk, amelyek adott elemekből állnak > elemek szerint, és vagy magukban az elemekben, vagy az elemek sorrendjében különböznek.

Egy elemhalmaz összes elemenkénti elrendezésének számát (a francia „arrangement” szó kezdőbetűjéből, amely elrendezést jelent), ahol és .

Tétel. Egy elemhalmaz elemenkénti elhelyezéseinek száma egyenlő

Bizonyíték. Tegyük fel, hogy vannak elemeink. Legyenek lehetséges elhelyezések. Ezeket az elhelyezéseket egymás után építjük fel. Először is határozzuk meg az első elhelyezési elemet. Egy adott elemkészletből többféleképpen választható ki. Az első elem kiválasztása után még mindig van mód a második elem kiválasztására stb. Mivel minden ilyen választás új helyet ad, ezek a választások szabadon kombinálhatók egymással. Ezért rendelkezünk:

Példa. Hányféleképpen lehet egy zászlót három különböző színű vízszintes csíkból összeállítani, ha öt színű anyag van?

Megoldás. A szükséges háromsávos zászlók száma:

Meghatározás. Egy elemhalmaz permutációja az elemek meghatározott sorrendben való elrendezése.

Így egy három elemből álló halmaz összes különböző permutációja

Az elemek összes permutációjának száma fel van tüntetve (a „permutation” francia szó kezdőbetűjéből, ami „permutációt”, „mozgást” jelent). Ezért az összes különböző permutáció számát a képlet számítja ki

Példa. Hányféleképpen helyezhetők el a bástya a sakktáblán, hogy ne támadják meg egymást?

Megoldás. A szükséges számú bástya

A-priory!

Meghatározás. A különböző elemek elemenkénti kombinációi olyan kombinációk, amelyek elemenként adott elemekből állnak össze, és legalább egy elemben különböznek egymástól (más szóval egy adott elemhalmaz -elem részhalmazai).

Mint látható, a kombinációkban, az elhelyezésekkel ellentétben, az elemek sorrendjét nem veszik figyelembe. Fel van tüntetve az összes elemkombináció, mindegyik elem száma (a francia „combinasion” szó kezdőbetűjéből, ami „kombinációt” jelent).

Számok

A kettőből álló összes kombináció .

A számok tulajdonságai (\sf C)_n^k

Valójában egy adott -elem halmaz minden -elem részhalmaza ugyanazon halmaz egy elemű részhalmazának felel meg.

Valójában a következő módon választhatjuk ki az elemek részhalmazait: egy elem rögzítése; az elemet tartalmazó -elem részhalmazok száma egyenlő ; az ezt az elemet nem tartalmazó -elem részhalmazok száma egyenlő .

Pascal háromszöge

Ebben a háromszögben a szélső számok minden sorban egyenlőek 1-gyel, és minden nem szélső szám egyenlő az előző sor feletti két szám összegével. Így ez a háromszög lehetővé teszi számok kiszámítását.

Tétel.

Bizonyíték. Tekintsünk egy elemhalmazt, és oldjuk meg a következő problémát kétféleképpen: hány sorozat készíthető egy adott elemből
halmazok, amelyek mindegyikében egyetlen elem sem jelenik meg kétszer?

1 út. Kiválasztjuk a sorozat első tagját, majd a másodikat, harmadikat stb. tag

2. módszer. Először válasszunk ki elemeket egy adott halmazból, majd rendezzük őket valamilyen sorrendbe

Szorozzuk meg ennek a törtnek a számlálóját és nevezőjét a következővel:

Példa. Hányféleképpen választhatsz ki 5 számot a 36-ból a „Sportloto” játékban?

Kötelező számú mód

Feladatok.

1. Az autók rendszáma az orosz ábécé 3 betűjéből (33 betű) és 4 számból áll. Hány különböző rendszám létezik?
2. A zongorán 88 billentyű található. Hányféleképpen tudsz egymás után 6 hangot előállítani?
3. Hány olyan hatjegyű szám van, amely osztható 5-tel?
4. Hányféleképpen helyezhető el 7 különböző érme három zsebben?
5. Hány olyan ötjegyű számot tud készíteni, amelynek decimális jelölésében legalább egyszer szerepel az 5-ös számjegy?
6. Hányféleképpen lehet 20 embert egy kerek asztalhoz ültetni, ha a módokat azonosnak tekintjük, ha körben mozgatva lehet őket megszerezni a másiktól?
7. Hány olyan ötjegyű szám van, amely osztható 5-tel, és nem tartalmaz azonos számjegyeket?
8. 1 cm-es cellaoldali kockás papírra egy 100 cm sugarú kört rajzolunk, amely nem megy át a cellák tetején, és nem érinti a cellák oldalát. Hány cellát metszhet ez a kör?
9. Hányféleképpen lehet sorba rendezni a számokat úgy, hogy a számok egymás mellett és növekvő sorrendben legyenek?
10. Hány ötjegyű szám készíthető számjegyekből, ha minden számjegy csak egyszer használható?
11. A ROT szóból a betűk átrendezésével a következő szavakat kaphatja: TOP, ORT, OTR, TRO, RTO. Ezeket anagrammáknak hívják. Hány anagrammát készíthetsz a LOGARITMUS szóból?
12. Hívjuk hasítás természetes szám, ábrázolása természetes számok összegeként. Itt van például egy szám összes partíciója:

A partíciókat akkor tekintjük eltérőnek, ha számban vagy kifejezési sorrendben különböznek.

Hány különböző partíciója van egy számnak?
13. Hány nem növekvő számsorrendű háromjegyű szám van?
14. Hány nem növekvő számsorrendű négyjegyű szám van?
15. Hányféleképpen lehet 17 embert egy sorba leültetni úgy, hogy egymás mellé kerüljenek?
16. a lányok és a fiúk véletlenszerűen ülnek be egy üléssorba. Hányféleképpen lehet úgy leültetni őket, hogy ne üljön két lány egymás mellett?
17. a lányok és a fiúk véletlenszerűen ülnek be egy üléssorba. Hányféleképpen lehet úgy leültetni őket, hogy az összes lány egymás mellett üljön?

A kombináció egy véges halmaz elemeinek rendezetlen válogatása rögzített számmal, elemismétlések nélkül. A különböző kombinációknak legalább egy elemben különbözniük kell, és az elemek sorrendje nem számít. Például a latin betűk magánhangzóinak készletéből (AEIOU) 10 különböző kombinációt hozhat létre 3 betűből, amelyek a következő rendezetlen hármasokat alkotják:

AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.

Érdekes megjegyezni, hogy ugyanabból az öt betűből 10 különböző kombinációt is kaphat, ha egyszerre 2 betűt kombinál, így a következő rendezetlen párokat alkotja:

AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.

Ha azonban ugyanazt a magánhangzó latin betűit 4-gyel kombinálja, akkor csak a következő 5 különböző kombinációt kapja:

AEIO, AEIU, AIOU, EIOU, AEOU.

Általában az m elemből álló n különböző elem kombinációinak számának jelölésére a következő funkcionális, index- vagy vektoros (Appel) szimbolikát használjuk:

A jelölés formájától függetlenül az n elem kombinációinak száma m elemmel a következő szorzó- és faktorképletekkel határozható meg:

Könnyen ellenőrizhető, hogy az ezekkel a képletekkel végzett számítások eredménye egybeesik-e a fentebb tárgyalt, latin betűs magánhangzó-kombinációkkal végzett példa eredményeivel. Különösen n=5 és m=3 esetén az ezekkel a képletekkel végzett számítások a következő eredményt adják:

Általános esetben a kombinációk számának képletei kombinatorikus jelentéssel bírnak, és bármely n és m egész értékre érvényesek úgy, hogy n > m > 0. Ha m > n és m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:

Ezenkívül hasznos megjegyezni a következő korlátozó számú kombinációkat, amelyek könnyen ellenőrizhetők a szorzó- és faktorképletekkel való közvetlen helyettesítéssel:

Azt is meg kell jegyezni, hogy a szorzóképlet akkor is érvényes marad, ha n valós szám, mindaddig, amíg m továbbra is egész szám. Ekkor azonban az ezt használó számítás eredménye a formai érvényesség megőrzése mellett elveszíti kombinatorikus értelmét.

A KOMBINÁCIÓK AZONOSSÁGAI

A szorzó- és faktorképletek gyakorlati alkalmazása az n és m tetszőleges értékeinek kombinációinak számának meghatározására kevéssé termelékeny a számlálójuk és nevezőjük faktoriális szorzatának exponenciális növekedése miatt. Még viszonylag kis n és m értékek esetén is, ezek a termékek gyakran meghaladják az egész számok megjelenítésének képességét a modern számítástechnikai és szoftverrendszerekben. Ezen túlmenően ezek értékei lényegesen nagyobbak, mint a kombinációk számának eredő értéke, amely viszonylag kicsi lehet. Például az n=10 m=8 elem kombinációinak száma mindössze 45. Ahhoz azonban, hogy ezt az értéket a faktoriális képlet segítségével megtaláljuk, először sokkal nagyobb, 10-es értékeket kell kiszámítani! a számlálóban és a 8-ban! a nevezőben:

A nagy mennyiségek feldolgozásának időigényes műveleteinek kiküszöbölésére, a kombinációk számának meghatározására különféle ismétlődési relációkat használhat, amelyek közvetlenül a szorzó- és faktorképletekből következnek. A multiplikatív képletből különösen a következő ismétlődési reláció következik, amely lehetővé teszi, hogy indexeinek arányát a kombinációk számának előjelén túlra vigyük:

Végül az alsó index állandó tartása a következő ismétlődési relációt eredményezi, amely könnyen megkapható a kombinációk számának faktoriális képletéből:

Az elemi transzformációk után a három eredő ismétlődési relációt a következő formában ábrázolhatjuk:

Ha most összeadjuk az első 2 képlet bal és jobb oldalát, és az eredményt n-nel csökkentjük, akkor egy fontos ismétlődési relációt kapunk, amelyet a kombinációs számok összeadásának azonosságának nevezünk:

Az összeadási azonosság alapvető ismétlődési szabályt biztosít a kombinációk számának hatékony meghatározásához nagy n és m értékek esetén, mivel lehetővé teszi, hogy a faktoriális szorzatokban a szorzási műveleteket lecseréljék az egyszerűbb összeadási műveletekre, és kisebb számú kombináció esetén. Konkrétan, az összeadási azonosság használatával most már könnyen meghatározható az n=10 m=8 elem kombinációinak száma, amit fentebb tárgyaltunk, a következő ismétlődő transzformációk végrehajtásával:

Ezenkívül az összeadási azonosságból számos hasznos reláció származtatható a véges összegek kiszámításához, különösen az alsó index szerinti összegzés képlete, amelynek alakja a következő:

Ezt az összefüggést akkor kapjuk meg, ha az összeadási azonosságban az ismétlődést kiterjesztjük a tag mentén a legnagyobb felső indexszel, miközben az alsó indexe nagyobb, mint 0. A következő numerikus példa szemlélteti az ismétlődő transzformációk folyamatát:

Az alsó index összegzési képletét gyakran használják a természetes számok hatványainak összegének kiszámítására. Különösen, ha m=1-et feltételezünk, ezzel a képlettel könnyen megtalálhatjuk a természetes sorozat első n számának összegét:

Az összegzési képlet másik hasznos változatát úgy kaphatjuk meg, ha az összeadási azonosság ismétlődését a kifejezés mentén a legkisebb felső indexszel bővítjük. A következő numerikus példa az ismétlődő átalakítások ezen verzióját szemlélteti:

Általános esetben az ilyen transzformációk eredményeként a kombinációk számának összegét kapjuk, amelyek mindkét indexe eggyel eltér a szomszédos tagoktól, és az indexek különbsége állandó marad (a vizsgált példában ez is egyenlő eggyel). Így a következő összegzési képletet kapjuk a kombinációs számok mindkét indexére:

A fentebb tárgyalt ismétlődési relációk és összegzési képletek mellett a kombinációs számok számos más hasznos azonosságát is sikerült elérni a kombinatorikus elemzés során. Közülük a legfontosabb az szimmetria azonosság, ami így néz ki:

A szimmetria-azonosság érvényessége a következő példában ellenőrizhető, ha összevetjük az 5 elemből álló kombinációk számát 2-vel és (5 2) = 3-mal:

A szimmetria-azonosságnak nyilvánvaló kombinatorikus jelentése van, mivel az n elem közül m elem kiválasztására vonatkozó lehetőségek számának meghatározásával egyidejűleg megállapítja a fennmaradó (nm) ki nem választott elem kombinációinak számát. A jelzett szimmetriát azonnal megkapjuk, ha m-t (nm)-re cserélünk a kombinációk számának faktorképletében:

A számokat és a kombinációs azonosságokat széles körben használják a modern számítási matematika különböző területein. A legnépszerűbb alkalmazásaik azonban a Newton-binomiálishoz és a Pascal-háromszöghöz kapcsolódnak.

BINOMIÁLIS TÉTEL

Különböző matematikai transzformációk és számítások elvégzéséhez fontos, hogy egy algebrai binomiális (binomiális) bármilyen természetes hatványát polinom formájában lehessen ábrázolni. Kis hatványok esetén a kívánt polinom könnyen megkapható a binomiálisok közvetlen szorzásával. Az elemi matematikából különösen jól ismertek a következő képletek két tag összegének négyzetére és kockájára:

Általános esetben egy binomiális tetszőleges n fokához a szükséges polinom formájú reprezentációt Newton binomiális tétele biztosítja, amely a következő egyenlőséget nyilvánítja ki igaznak:

Ezt az egyenlőséget általában Newton-binomiálisnak nevezik. A jobb oldalán lévő polinomot a bal oldali binomiális X és Y n tagjának szorzata alkotja, és az előttük lévő együtthatókat binomiálisnak nevezzük, és egyenlők az indexekkel való kombinációk számával, hatalmukból nyerik. Tekintettel a Newton-féle binomiális képlet különös népszerűségére a kombinatorikus elemzésben, a binomiális együttható és a kombinációk száma kifejezéseket általában szinonimáknak tekintik.

Nyilvánvalóan a négyzetes és a kockaösszeg képlete a binomiális tétel speciális esetei n=2, illetve n=3 esetén. A magasabb fokok (n>3) kezelésére a Newton-binomiális képletet kell használni. Alkalmazását a negyedik fokú binomiálisra (n=4) a következő példa szemlélteti:

Meg kell jegyezni, hogy a binomiális képletet már Newton előtt ismerték az arab keleti és nyugat-európai középkori matematikusok. Ezért az általánosan elfogadott neve történelmileg nem helytálló. Newton érdeme, hogy ezt a képletet általánosította egy tetszőleges r valós kitevő esetére, amely bármilyen pozitív vagy negatív racionális és irracionális értéket vehet fel. Általános esetben egy ilyen Newton-binomiális képletnek a jobb oldalán végtelen összege van, és általában a következőképpen írják le:

Például az r=1/2 kitevő pozitív törtértékével, figyelembe véve a binomiális együtthatók értékeit, a következő kiterjesztést kapjuk:

Általános esetben a Newton-féle binomiális képlet bármely kitevőre a Maclaurin-képlet egy speciális változata, amely egy tetszőleges függvény hatványsorba való kiterjesztését adja. Newton megmutatta, hogy |z|-re< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0. Ha most beállítjuk a Z=X/Y-t, és megszorozzuk a bal és jobb oldalt Yn-nel, akkor megkapjuk a Newton-binomiális képlet fentebb tárgyalt változatát.

Univerzálissága ellenére a binomiális tétel csak a binomiális nem negatív egész hatványaira őrzi meg kombinatorikus jelentését. Ebben az esetben a binomiális együtthatók számos hasznos azonosságának bizonyítására használható. A fentiekben különösen a kombinációk számának alsó index és mindkét index szerinti összegzésére szolgáló képleteket tárgyaltuk. A hiányzó felső index összegzési azonossága könnyen megszerezhető Newton binomiális képletéből, ha X = Y = 1 vagy Z = 1 szerepel benne:

Egy másik hasznos azonosság megállapítja a binomiális együtthatók összegének egyenlőségét páros és páratlan számokkal. A Newton-binomiális képletből azonnal megkapjuk, ha X = 1 és Y = 1 vagy Z = 1:

Végül mindkét figyelembe vett azonosságból megkapjuk a páros vagy csak páratlan számokkal rendelkező binomiális együtthatók összegének azonosságát:

A figyelembe vett identitások és a kombinációk számának előjele alól az indexek eltávolításának ismétlődő szabálya alapján számos érdekes összefüggést kaphatunk. Például, ha a felső index összegző képletében n-et mindenhol (n1)-re cserélünk, és minden tagból eltávolítjuk az indexeket, akkor a következő összefüggést kapjuk:

Hasonló technikával a páros és páratlan számokkal rendelkező binomiális együtthatók összegének képletében igazolható például a következő összefüggés érvényessége:

Egy másik hasznos azonosság lehetővé teszi, hogy könnyen kiszámítsa két tetszőleges n és k fokú binomiális együttható szimmetrikusan elhelyezkedő együtthatóinak összegét a következő Cauchy-képlet segítségével:

Ennek a képletnek az érvényessége a következő azonos reláció bal és jobb oldalán lévő Z változó tetszőleges m fokára vonatkozó együtthatók szükséges egyenlőségéből következik:

Abban a speciális esetben, amikor n=k=m, figyelembe véve a szimmetriazonosságot, egy népszerűbb képletet kapunk a binomiális együtthatók négyzetösszegére:

A binomiális együtthatók sok más hasznos azonossága megtalálható a kombinatorikus elemzés kiterjedt szakirodalmában. Leghíresebb gyakorlati alkalmazásuk azonban a Pascal-háromszöggel kapcsolatos.

PASCAL-HÁROMSZÖG

Pascal aritmetikai háromszöge egy végtelen numerikus táblázatot alkot, amely binomiális együtthatókból áll. Sorai binomiális hatványok szerint vannak rendezve fentről lefelé. Minden sorban a binomiális együtthatók a megfelelő kombinációs számok felső indexei szerint balról jobbra növekvő sorrendben vannak elrendezve. A Pascal-háromszöget általában egyenlő szárú vagy téglalap alakúra írják.

Vizuálisabb és gyakoribb az egyenlő szárú formátum, ahol a binomiális együtthatók lépcsőzetesen végtelen egyenlő szárú háromszöget alkotnak. Kezdő töredéke a 4. fokozatig (n=4) a binomiálisokhoz a következő formában van:

Általánosságban elmondható, hogy a Pascal-féle egyenlő szárú háromszög kényelmes geometriai szabályt biztosít a binomiális együtthatók meghatározásához, amely az összeadás azonosságán és a számkombinációk szimmetriáján alapul. Konkrétan, az összeadási azonosság szerint bármely binomiális együttható a hozzá legközelebb eső előző sor két együtthatójának összege. A szimmetria-azonosság szerint Pascal egyenlő szárú háromszöge szimmetrikus a felezőszögéhez képest. Így minden vonala binomiális együtthatók numerikus palindromja. A jelzett algebrai és geometriai jellemzők lehetővé teszik Pascal egyenlő szárú háromszögének egyszerű kiterjesztését, és következetesen megtalálják a tetszőleges hatványok binomiális együtthatóinak értékét.

A Pascal-háromszög különféle tulajdonságainak tanulmányozásához azonban kényelmesebb a formálisan szigorúbb téglalap formátum használata. Ebben a formátumban a binomiális együtthatók alsó háromszögmátrixa határozza meg, ahol végtelen derékszögű háromszöget alkotnak. A Pascal-féle derékszögű háromszög kezdeti töredéke a 9. fokig (n=9) lévő binomiálisoknál a következő alakú:

Geometriailag egy ilyen téglalap alakú táblázatot Pascal egyenlő szárú háromszögének vízszintes deformálásával kapunk. Ennek eredményeként a Pascal-féle egyenlő szárú háromszög oldalsó oldalaival párhuzamos számsorok Pascal derékszögű háromszögének függőlegeseivé és átlóivá alakulnak, és mindkét háromszög vízszintesei egybeesnek. Ugyanakkor a binomiális együtthatók összeadásának és szimmetriájának szabályai érvényben maradnak, bár Pascal derékszögű háromszöge elveszti az egyenlő szárú megfelelőjére jellemző vizuális szimmetriát. Ennek kompenzálására kényelmesebbé válik a Pascal-féle derékszögű háromszög vízszinteseinek, függőlegeseinek és átlóinak binomiális együtthatóinak különféle numerikus tulajdonságainak formális elemzése.

A Pascal-féle derékszögű háromszög vízszinteseinek elemzését elkezdve könnyen észrevehető, hogy bármely n számú sor elemeinek összege a binomiálisok felső index szerinti összegzésének képlete szerint egyenlő 2n-nel. Ebből következik, hogy az n számú vízszintes egyenesek bármelyike ​​feletti elemek összege egyenlő (2 n 1). Ez az eredmény egészen nyilvánvalóvá válik, ha az egyes vízszintesek elemeinek összegét kettes számrendszerbe írjuk. Például n=4 esetén ez az összeadás a következőképpen írható fel:

Íme a vízszintesek néhány további érdekes tulajdonsága, amelyek szintén a kettő hatványaihoz kapcsolódnak. Kiderül, hogy ha a vízszintes szám kettő hatványa (n=2 k), akkor minden belső eleme (a külsők kivételével) páros szám. Éppen ellenkezőleg, egy vízszintes egyenes minden száma páratlan lesz, ha a száma eggyel kisebb, mint kettő hatványa (n=2 k 1). Ezen tulajdonságok érvényessége a belső binomiális együtthatók paritásának ellenőrzésével ellenőrizhető, például az n=4 és n=3 vagy n=8 és n=7 vízszintesekben.

Legyen most Pascal derékszögű háromszögének sorszáma p prímszám. Ekkor minden belső binomiális együtthatója osztható p-vel. Ez a tulajdonság könnyen ellenőrizhető a prímkontúrszámok kis értékeinél. Például az ötödik vízszintes összes belső binomiális együtthatója (5, 10 és 5) nyilvánvalóan osztható 5-tel. Bármely p prím vízszintes számra ennek az eredménynek a bizonyításához fel kell írni a binomiális együtthatói szorzóképletét a következőképpen:

Mivel p prímszám, ezért nem osztható m-mel!, a képlet számlálójának fennmaradó tényezőinek szorzatának oszthatónak kell lennie m-mel, hogy a binomiális együttható egész értéke legyen. Ebből következik, hogy a szögletes zárójelben lévő arány egy N természetes szám, és a kívánt eredmény nyilvánvalóvá válik:

Ennek az eredménynek a segítségével megállapíthatjuk, hogy a Pascal-háromszög minden olyan vízszintes egyenesének a száma, amelynek belső elemei oszthatók egy adott p prímszámmal, p hatványai, azaz n=p k alakúak. Konkrétan, ha p=3, akkor a p prímszám nemcsak a 3. sor összes belső elemét osztja fel, ahogy fentebb megállapítottuk, hanem például a 9. vízszintesét (9, 36, 84 és 126). Másrészt a Pascal-háromszögben lehetetlen olyan vízszintes egyenest találni, amelynek belső elemei mind oszthatók egy összetett számmal. Ellenkező esetben egy ilyen vízszintes egyenes számának egyidejűleg az összetett szám prímosztóinak hatványának kell lennie, amellyel minden belső eleme el van osztva, de ez nyilvánvaló okokból lehetetlen.

A figyelembe vett megfontolások lehetővé teszik, hogy a következő általános kritériumot fogalmazzuk meg a Pascal-háromszög vízszintes elemeinek oszthatóságára. A Pascal-háromszög n számú vízszintes vonalának összes belső elemének legnagyobb közös osztója (GCD) egyenlő a p prímszámmal, ha n=pk vagy 1 minden más esetben:

GCD(Cmn) = ( ) bármely 0 esetén< m < n .

A horizontálisok elemzésének végén érdemes még egy érdekes tulajdonságot figyelembe venni, amellyel az őket alkotó binomiális együtthatók sorozata rendelkezik. Ha bármely n számú vízszintes egyenes binomiális együtthatóit megszorozzuk a 10 szám egymást követő hatványaival, majd ezeket a szorzatokat összeadjuk, az eredmény 11 n. Ennek az eredménynek a formális indoklása az X=10 és Y=1 (vagy Z=1) értékek behelyettesítése a Newton-binomiális képletbe. A következő numerikus példa szemlélteti ennek a tulajdonságnak a teljesítését n=5 esetén:

A Pascal-féle derékszögű háromszög függőlegesei tulajdonságainak elemzése kezdődhet az alkotóelemeik egyedi jellemzőinek vizsgálatával. Formálisan minden m függőleges binomiális együtthatók következő végtelen sorozatából áll, állandó felső indexszel (m) és az alsó index növekményével:

Nyilvánvaló, hogy ha m=0 egyek sorozata, m=1 esetén pedig természetes számok sorozata keletkezik. Ha m=2, a függőleges háromszög számokból áll. Minden háromszög szám egy síkon ábrázolható egyenlő oldalú háromszög formájában, amely tetszőleges objektumokkal (magokkal) van kitöltve, sakktábla mintázatban. Ebben az esetben az egyes T k háromszögszámok értéke határozza meg a reprezentáló kernelek számát, az index pedig azt mutatja meg, hogy hány kernelsor szükséges a reprezentációhoz. Például 4 kezdeti háromszög szám a megfelelő számú nukleáris „@” szimbólum alábbi konfigurációit jelenti:

Megjegyzendő, hogy hasonló módon figyelembe lehet venni az S k négyzetszámokat is, amelyeket természetes számok négyzetre emelésével kapunk, és általában a szabályos sokszögek szabályos kitöltésével képzett sokszög alakú számokat. A 4 kezdeti négyzetszám a következőképpen ábrázolható:

Visszatérve a Pascal-háromszög függőlegeseinek elemzésére, megállapíthatjuk, hogy a következő függőleges m=3-nál tetraéderes (piramis) számokkal van kitöltve. Minden ilyen P k szám megadja a tetraéder alakban elrendezhető magok számát, az index pedig azt, hogy hány vízszintes háromszög alakú magsorréteg szükséges a háromdimenziós térben való ábrázolásához. Ebben az esetben az összes vízszintes réteget egymást követő háromszög számként kell ábrázolni. A Pascal-háromszög következő függőlegeseinek m>3 elemei olyan hipertetraedális számsorokat alkotnak, amelyeknek nincs vizuális geometriai értelmezése síkon vagy háromdimenziós térben, hanem formálisan megfelelnek a háromszög- és tetraéderszámok többdimenziós analógjainak.

Bár a Pascal-háromszög függőleges számsorai rendelkeznek a figyelembe vett egyedi alakú jellemzőkkel, ezeknél a kezdeti elemek értékeinek részösszegei ugyanúgy kiszámíthatók, a kombinációk számának alsó indexenkénti összegzésére szolgáló képlet segítségével. . A Pascal-háromszögben ennek a képletnek a geometriai értelmezése a következő. Bármely függőleges n felső binomiális együttható értékének összege megegyezik a következő függőleges elem értékével, amely egy sorral alatta található. Ez az eredmény összhangban van a háromszög-, tetraéder- és hipertetraéderszámok geometriai szerkezetével is, mivel mindegyik ilyen szám ábrázolása olyan magrétegekből áll, amelyek alacsonyabb rendszámokat képviselnek. Az n-edik Tn háromszögszámot úgy kaphatjuk meg, hogy összeadjuk a lineáris rétegeit reprezentáló természetes számokat:

Hasonlóképpen, nem nehéz megtalálni a Pn tetraéderszámot a vízszintes magrétegeket alkotó első n háromszögszám következő összegének kiszámításával:

A Pascal derékszögű háromszögben a vízszintesek és függőlegesek mellett átlós elemsorok is nyomon követhetők, amelyek tulajdonságainak vizsgálata szintén érdekes. Ebben az esetben általában különbséget tesznek a csökkenő és a növekvő átlók között. A lefelé mutató átlók párhuzamosak Pascal derékszögű háromszögének befogójával. Ezeket binomiális együtthatók sorozatából képezik, mindkét index növekményével. A szimmetria azonossága miatt a csökkenő átlók elemeik értékében egybeesnek a Pascal-háromszög megfelelő függőleges soraival, és ezért megismétlik a fent tárgyalt összes tulajdonságukat. A jelzett megfelelés nyomon követhető a csökkenő átló és a függőleges elemeinek értékeinek egybeesésével tetszőleges n számmal, ha a függőleges nullákat nem vesszük figyelembe:

A növekvő átlók számsorokat alkotnak, amelyek geometriailag merőlegesek Pascal derékszögű háromszögének befogójára. Ezeket binomiális együtthatókkal töltik fel, a felső index alsó értékének csökkenésével és növekményével. A 7 felső növekvő átló a következő numerikus sorozatot alkotja anélkül, hogy figyelembe venné a záró nullákat:

Általában az n növekvő átlószám a következő binomiális együtthatókat tartalmazza, amelyek mindegyikének indexeinek összege egyenlő (n1):

A számkombinációk összeadása miatt minden átlós elem egyenlő az előző két növekvő átló indexében szereplő két elem összegével. Ez lehetővé teszi, hogy minden következő növekvő átlót a két előző átló szomszédos vízszintes elemeinek páronkénti összegzésével állítsunk elő, végtelenül kiterjesztve a Pascal-háromszöget az átló mentén. A Pascal-háromszög következő töredéke a 6-os és 7-es számozott átlók mentén egy 8-as növekvő átló felépítését szemlélteti:

Ezzel a konstrukciós módszerrel bármely növekvő átló elemeinek összege a 3.-tól kezdve egyenlő lesz a két előző növekvő átló elemeinek összegével, és az első 2 átló csak egy elemből áll, az érték amelyből 1. A megfelelő számítások eredménye a következő numerikus sorozatot alkotja, amely alapján ellenőrizheti a Pascal-féle derékszögű háromszög növekvő átlóinak figyelembe vett tulajdonságának érvényességét:

Ezeket a számokat elemezve látható, hogy egy hasonló törvény szerint létrejön a jól ismert Fibonacci-számsorozat, ahol minden következő szám egyenlő az előző két szám összegével, az első két szám pedig 1-gyel:

Így a következő fontos következtetést vonhatjuk le: a Pascal-háromszög elemeinek átlós összegei alkotják a Fibonacci-sorozatot. Ez a tulajdonság lehetővé teszi, hogy megállapítsuk a Pascal-háromszög másik érdekes jellemzőjét. A Fibonacci-képletet rekurzívan bővítve könnyen bebizonyítható, hogy az első n Fibonacci-szám összege egyenlő (F n+2 1).

Ezért a felső n átlót kitöltő binomiális együtthatók összege is egyenlő (F n+2 1). Ebből következik, hogy a Pascal-háromszög első n átlójának összege 1-gyel kisebb, mint az (n+2) számú átlóján álló binomiális együtthatók összege.

Végezetül meg kell jegyezni, hogy a Pascal-háromszög vízszinteseinek, függőlegeseinek és átlóinak figyelembe vett tulajdonságai nem merítik ki a lehetőségek széles választékát, amelyek összekapcsolják a különféle matematikai szempontokat, amelyekben első pillantásra semmi közös. Az ilyen szokatlan tulajdonságok lehetővé teszik, hogy a Pascal-háromszöget az egyik legtökéletesebb numerikus rendszernek tekintsük, amelynek minden képességét nem lehet felsorolni, és nehéz túlbecsülni.

Az alábbiakban bemutatjuk a Pascal-háromszög segítségével a kombinációk számának kiszámítására szolgáló algoritmust:

SochTT privát függvény (ByVal n egész szám, ByVal k egész szám) Dupla dim i egész Dim j egész Dim TT () Dupla ReDim TT (n, k) For i = 0 - n TT (0, i) = 1 TT (i, i) = 1 Következő Ha i = 2 - n Ha j = 1 - i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Következő Következő SochTT = TT (n, k) Vége funkció

Ha többször kell kiszámolni a kombinációk számát, akkor kényelmesebb lehet egyszer megszerkeszteni a Pascal-háromszöget, majd adatokat fogadni a tömbből.

Dim TT () Mint Dupla privát Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) Mint Dupla If n > Ubound (TT) Akkor BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Funkció vége Privát al-lezárásTT () ReDim TT (0, 0) Sub-Private Sub BuildTT vége (ByVal kezdés egész számként, ByVal vége egész számként) Dim i egész szám Dim j As Integer ReDim Preserve TT (vége, vége) For i = elejétől a végéig TT (0, i) = 1 TT (i, i) = 1 Következő Ha vége< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub

Először meg kell hívnia a CreateTT eljárást. Ezután a SochTT funkció segítségével lekérheti a kombinációk számát. Ha már nincs szüksége a háromszögre, hívja meg a TerminateTT eljárást. A fenti kódban a SochTT függvény hívásakor, ha a háromszög még nem készült el a kívánt szintre, akkor a BuildTT eljárással fejeződik be. A függvény ezután megkapja a TT tömb kívánt elemét, és visszaadja azt.

Dim X () As Integer Dim Counter () Mint Integer Dim K Mint Integer Dim N Mint Integer Public Sub Soch() Dim i As Integer N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Következő txtOut.Text = "" Redim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K Akkor ReDim Out(K) X1 = X For i = 1 to K - 1 n1 = 0 Ha j = 1 - N Ha X1(j)<>0 Akkor n1 = n1 + 1 Ha n1 = Számláló(i) Akkor Ki(i) = X1(j) X1(j) = 0 Kilépés a végéhez Ha Következő txtOut.Text = txtOut.Text & CStr(Out(i)) Tovább

TERMÉSZETES SZÁMOK KOMBINÁCIÓJÁNAK FELSOROLÁSA

Számos gyakorlati probléma megoldásához fel kell sorolni az adott véges halmaz elemeiből nyerhető fix számosság összes kombinációját, és nem csak a számukat kell meghatározni. Figyelembe véve bármely véges halmaz elemeinek egész számozásának mindig fennálló lehetőségét, a legtöbb esetben megengedhető, hogy a természetes számok kombinációinak felsorolására szolgáló algoritmusokra korlátozódjunk. Közülük a legtermészetesebb és legegyszerűbb a természetes számok kombinációinak listázására szolgáló algoritmus lexigráfiai rend.

Ennek az algoritmusnak a formális leírásához célszerű feltételezni, hogy a főhalmaz, amelynek m elemének összes kombinációját fel kell sorolni, egymást követő természetes számokat alkot 1-től n-ig. Ezután az m tetszőleges kombinációja

A rendezés eredményeként az ilyen kombinációk vektorának minden pozíciójában az érték természetesen felülről és alulról korlátozott értéknek bizonyul, az alábbiak szerint:

A lexigráfiai algoritmus szekvenciálisan generál olyan kombinációs vektorokat, kezdve a lexigráfiailag legkisebb vektorral, ahol minden pozíció a következő minimálisan lehetséges elemértékeket tartalmazza az indexükkel megegyezően:

Minden egymást követő kombinációs vektor az aktuálisból jön létre, miután elemeit balról jobbra pásztázza, hogy megtalálja a jobb szélső elemet, amely még nem érte el a határértékét:

Egy ilyen elem értékét növelni kell 1-gyel. Minden tőle jobbra lévő elemhez hozzá kell rendelni a lehető legkisebb értéket, amely 1-gyel nagyobb, mint a bal oldali szomszédja. E változtatások után a következő kombinációk vektorának elemi összetétele a következő lesz:

Így a következő kombinációs vektor lexigráfiailag nagyobb lesz, mint az előző, mivel a kezdeti (j1) elemeik értéke egyenlő, és a j pozícióban lévő elem értéke 1-gyel nagyobb, mint az előzőé. . A növekvő lexigráfiai sorrend meghatározott relációja garantáltan teljesül az algoritmus minden iterációjában. Az eredmény egy növekvő lexigráfiai sorozat, amelyet a lexigráfiailag legnagyobb kombinációs vektor egészít ki, ahol az elemek minden pozícióban a következő maximális értékekkel rendelkeznek:

A vizsgált lexigráfiai algoritmust a következő példa szemlélteti, ahol növekvő lexigráfiai sorrendben kell felsorolni az n=6 első természetes szám mind a 15 kombinációját m=4 számmal, vagyis a főgenerátor összes lehetséges 4 elemű részhalmazát. készlet (1, 2, 3, 4 , 5, 6) 6 elemből. A számítási eredményeket az alábbi táblázat tartalmazza:

Ebben a példában a számok legnagyobb megengedett értéke a kombinációs vektorok pozíciójában rendre 3, 4, 5 és 6. Az eredmények értelmezésének megkönnyítése érdekében minden kombinációs vektorban a jobb szélső elem, amely még nem érte el maximális értékét, aláhúzott. A kombinációs vektorok numerikus indexei lexigráfiai sorrendben határozzák meg a számukat. Általános esetben az n elemből álló tetszőleges kombinációk N lexigráfiai száma m-rel kiszámítható a következő képlettel, ahol kozmetikai okokból Appel szimbolikát használunk a kombinációk számának jelölésére:

Konkrétan, a következő számítások ezzel a képlettel az m=4 n=6 elemének kombinációszámára (1, 3, 4, 6) lexigráfiai sorrendben N=8 eredményt adnak, amely megfelel a fent tárgyalt példának:

Általános esetben mindkét index kombinációszámának összegére vonatkozó azonosságot felhasználva kimutatható, hogy a lexigráfiailag legkisebb kombináció (1, ... i, ... m) száma ezzel számítva. képlet mindig egyenlő lesz 1-gyel:

Az is nyilvánvaló, hogy a lexigráfiailag legnagyobb kombináció (m, … nm+i, … n) száma ezzel a képlettel számolva egyenlő lesz n elem kombinációinak számával m-vel:

A lexigráfiai kombinációs számok kiszámításának képlete használható az inverz probléma megoldására, ahol a kombinációs vektort a szám alapján kell meghatározni lexigráfiai sorrendben. Egy ilyen inverz probléma megoldásához egyenlet formájában kell felírni, ahol a kívánt kombináció vektor elemeinek összes ismeretlen értéke (C 1, ... C i, ... C m ) a jobb oldalának kombinációiban koncentrálódnak, és a kombinációk számának ismert L különbsége minden m n elem bal oldalára van írva, és a kívánt kombináció száma N:

Ennek az egyenletnek a megoldását a következő „kapzsi” algoritmus adja, amelynek iterációi során a kívánt kombináció vektorának elemeinek értékeit szekvenciálisan választják ki. A kezdeti iterációnál a lehető legkisebb (korlátain belül) C 1 értéke kerül kiválasztásra, amelynél a jobb oldali első tag maximális értéke nem haladja meg az L-t:

Most az L bal oldalát csökkenteni kell a jobb oldalon lévő első számú kombinációval a kiválasztott C 1 értékkel, és hasonlóképpen meg kell határozni a C 2 értékét a második iterációnál:

Hasonlóképpen minden további iterációt el kell végezni a kívánt kombináció összes többi elemének C i értékének kiválasztásához, egészen az utolsó C m elemig:

Nyilvánvaló okokból az utolsó C m elem értéke úgy határozható meg, hogy kombinációinak száma egyenlő L bal oldalának maradékértékével:

Meg kell jegyezni, hogy a C m kombináció utolsó elemének értéke még egyszerűbben megtalálható anélkül, hogy felsorolnánk a lehetséges értékeket:

A vizsgált algoritmus iterációinak megvalósítását a következő példa szemlélteti, ahol lexigráfiai sorrendben N=8-as kombinációkat kell meghatározni, ha n=6 és m=4:

Az algoritmikus képesség, amely egy adott szám alapján lexigráfiai sorrendben határoz meg egy kombinációt, többféle irányban használható. Különösen a kombinációk lexigráfiai sorrendben történő felsorolásakor szükséges biztosítani a visszatérést bármely korábban kapott kombinációhoz, elegendő csak a számát ismerni. Ezenkívül lehetővé válik a kombinációk tetszőleges sorrendben történő létrehozása, amelyet a lexigráfiai számok tetszőlegesen megadott sorozata szabályoz.

Most bemutatunk egy algoritmust a kombinációk lexikográfiai sorrendben történő előállításához:

2 i:= 1-től k-ig A[i] := i;

5 kezdi az írást (A, …, A[k]);

6 ha A[k] = n, akkor p:= p 1 különben p:= k;

8 i:= k le p do A[i] := A[p] + i p + 1

KOMBINÁCIÓK ISMÉTLŐ ELEMEKKEL

Ellentétben a klasszikus kombinációkkal, ahol minden elem különbözik, az ismétlődésekkel való kombináció egy véges halmaz elemeinek rendezetlen válogatását alkotja, ahol bármely elem korlátlanul gyakran előfordulhat, és nem feltétlenül van jelen egyetlen példányban. Ebben az esetben az elemek ismétlődéseinek számát általában csak a kombináció hossza korlátozza, és a legalább egy elemben eltérő kombinációkat különbözőnek tekintjük. Például, ha az 1-es, 2-es és 3-as készletből 4 opcionálisan eltérő számot választ, a következő 15 kombinációt hozhatja létre ismétlésekkel:

1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.

Általánosságban elmondható, hogy n darab tetszőleges típusú elem kiválasztásával ismétlődő kombinációk alakíthatók ki. Azonban mindig társíthatók egymás után következő természetes számokhoz 1-től n-ig. Ekkor ebbe a tartományba tartozó m opcionálisan különböző számok tetszőleges kombinációja felírható vektor formában, balról jobbra nem csökkenő sorrendbe rendezve:

Természetesen ezzel a jelölési formával bármely szomszédos elem egyenlő lehet a korlátlan ismétlési lehetőség miatt. Mindazonáltal minden n elem m-es ismétlődésű kombinációs vektora társítható egy m-es (n+m-1) elemből álló kombinációs vektorral, amely a következőképpen épül fel:

Nyilvánvaló, hogy az f vektor elemeinek bármely értékénél a C vektor elemei garantáltan eltérőek és szigorúan az értékük növekvő sorrendjében vannak rendezve 1-től (n+m1) tartományig. :

Az f és C kombinációs vektorok elemei közötti egy az egyhez megfelelőség megléte lehetővé teszi számunkra, hogy a következő egyszerű módszert javasoljuk az n elem m-vel ismétlődő kombinációinak szisztematikus felsorolására. Csak például lexigráfiai sorrendben kell felsorolni az m (n+m1) elemeinek összes C kombinációját, szekvenciálisan átalakítva mindegyik elemét az f ismétlődésű kombinációk megfelelő elemeivé a következő képlet segítségével:

Ennek eredményeként létrejön az elemek ismétlődő kombinációinak sorozata, amelyek a megfelelő kombinációk elemismétlődés nélküli felsorolásával generált sorrendben vannak elrendezve. Különösen annak érdekében, hogy a fenti 3 számjegyből álló 1, 2 és 3 kombinációs sorozatot kapjuk 4 számjegy ismétlésével, lexigráfiai sorrendben kell felsorolni az összes kombinációt 6 számjegy 1, 2, 3, 4, 5 ismétlődése nélkül. és a 6 egyenként 4 számjegyből áll, a jelzett módon konvertálva őket. A következő példa az (1,3,4,6) kombináció ilyen átalakítását mutatja be a 8-as lexikográfiai számmal:

Az elemek ismétlődését tartalmazó és anélküli kombinációk egy az egyhez való megfeleltetése azt jelenti, hogy halmazaik egyformán erősek. Ezért általános esetben az n elemű m-es ismétlődésű kombinációk száma megegyezik az (n+m1) elem ismétlődése nélküli kombinációk számával m-vel. Ugyanazt a szimbolikát használva az f ismétlődésű és a C ismétlődés nélküli kombinációk számának jelölésére, ez az egyenlőség a következőképpen írható fel:

Könnyen ellenőrizhető, hogy a fenti példában, ahol n=3 és m=4, az ismétlési kombinációk száma 15 lesz, ami egybeesik a közvetlen felsorolásuk eredményével:

Meg kell jegyezni, hogy a klasszikus változattól eltérően az n és m ismétlődésű kombinációs paraméterek értékei nem kapcsolódnak közvetlenül egymáshoz, ezért pozitív értékük bármely kombinációja esetén f(n,m)>0. A megfelelő peremfeltételeket az (n+m1) és (n1) vagy (n+m1) és m értékek egyenlőségéből határozzuk meg:

Az is teljesen nyilvánvaló, hogy ha m egyenlő 1-gyel, akkor nem lehetséges az elemek ismétlése, és ezért bármely n>0 pozitív értékre a következő egyenlőség lesz igaz:

Ezen túlmenően, az ismétlődő kombinációk számára bármely pozitív n és m érték esetén a következő ismétlődési összefüggés érvényes, amely hasonló az elemek ismétlődése nélküli kombinációk számának összeadási azonosságához:

Valójában akkor válik a jelzett összeadási azonossággá, ha a megfelelő számú kombinációt ismétlés nélkül a bal és a jobb oldalára formálisan helyettesítjük:

A figyelembe vett ismétlődési reláció segítségével hatékonyan határozható meg az ismétlődéses kombinációk száma, amikor fontos a faktoriális szorzatszámítás munkaigényes műveleteinek kiküszöbölése és egyszerűbb összeadási műveletekkel való helyettesítése. Ebben az esetben az f(n,m) értékének kiszámításához csak ezt az ismétlődési relációt kell alkalmazni, amíg meg nem kapjuk az f(1,m) és f(i,1) alakú tagok összegét, ahol i n-től 1-ig terjedő tartományban vesz fel értékeket. A mennyiség definíciója szerint ezek a tagok 1-el, illetve i-vel egyenlők. A következő példa bemutatja ennek a transzformációs technikának a használatát n=3 és m=4 esetén:

BINÁRIS KOMBINÁCIÓK FELSOROLÁSA

Hardveres kombinációk implementálásakor vagy assembly nyelvű programozáskor fontos, hogy a kombinációs rekordokat bináris formátumban tudjuk feldolgozni. Ebben az esetben az m n elemének tetszőleges kombinációját n-bites bináris szám formájában kell megadni (B n,...B j,...B 1), ahol m egységszámjegy jelzi a kombinációt, és a fennmaradó (nm) számjegyek értéke nulla. Nyilvánvaló, hogy ezzel a jelölési formával a különböző kombinációknak különbözniük kell az 1-es számjegyek elrendezésében, és csak C(n,m) mód van m egyesek vagy (nm) nullák elrendezésére egy n bites bináris halmazban. Például a következő táblázat felsorolja mind a 6 ilyen bináris kombinációt, amelyek 4 bites bináris számokat adnak egy tetszőleges halmaz 4 elemének (E 1 , E 2 , E 3 , E 4 ) összes kombinációjához 2-vel:

Általános esetben az ilyen bináris kombinációk felsorolásának feladata az összes n-bites bináris halmaz szisztematikus keresése, m egy és (nm) nulla bitek különböző elrendezésével. A legegyszerűbb formában az ilyen keresést a szomszédos bitek eltolásos transzponálásának különféle módszereivel valósítják meg (transzpozitív-eltolási algoritmusok). Ezek iteratív algoritmusok, és nevük az egyes lépésekben végrehajtott műveletek jellegét tükrözi. A transzpozitív eltolódásos algoritmusok iteratív eljárásai bináris kombinációk sorozatait alkotják, amelyek egy bináris halmazzal kezdődnek, ahol mindegyik az alacsonyabb rendű számjegyekben összpontosul (jobb oldalon), és akkor ér véget, amikor az összes 1 a magasabb rendű számjegyekben van ( bal oldalon):

Miközben a kezdeti és a végső kombinációkban illeszkednek, ezek a sorozatok különböznek a köztes bináris halmazok felsorolásának sorrendjében. Azonban minden esetben minden következő bináris kombináció az előzőből jön létre a megfelelő transzponálási és eltolási műveletek végrehajtása eredményeként. Ugyanakkor a különféle transzpozitív eltolási algoritmusok abban különböznek egymástól, ahogyan kiválasztanak egy bitpárt az átültetéshez és egy bitcsoportot az eltoláshoz. Ezt a specifitást az alábbiakban tárgyaljuk a balra és jobbra eltolású transzponálási algoritmusok esetében.

A balra tolással végzett transzponálási algoritmusban minden lépésben a következő bináris kombinációt kapjuk az aktuálisból úgy, hogy a bal szélső 01 számjegypárt 10-re cseréljük (transzpozíció), és a vezető egység számjegyek csoportját, ha van ilyen, közel a az átültetés (shift) után kapott 10-es pár. Ha ebben az esetben az aktuális bináris kombinációban nincsenek egységek a bevezető számjegyekben, akkor az eltolás nem történik meg, még akkor sem, ha ebben a lépésben a bevezető egységet megkapjuk a transzponálás után. Az eltolást akkor sem hajtják végre, ha a transzponálás után kapott 10 pár előtt nincsenek nullák a legjelentősebb bitekben. A vizsgált műveleteket az alábbi példa szemlélteti az algoritmus két egymást követő iterációjának végrehajtására, ahol az egyik iterációnál (15) csak transzponálás (T") történik, a másik iterációnál (16) pedig a transzponálást egy eltolás egészíti ki ( T"+S"):

A jobbra eltolásos transzpozíciós algoritmusban minden lépésben elvileg hasonló lépéseket hajtanak végre. Csak a transzponálás biztosítja, hogy a 01 jobb szélső bitjeit 10 cserélje ki (a bal szélső bitek helyett), majd a tőle jobbra lévők mindegyike eltolódik a legkisebb jelentőségű bitekre. A korábbiakhoz hasonlóan az eltolás csak akkor történik meg, ha vannak jobbra tolható egységek. A vizsgált műveleteket az alábbi példa szemlélteti az algoritmus két egymást követő iterációjának végrehajtására, ahol az egyik iterációnál (3) csak transzponálás (T") történik, a másik iterációnál (4) pedig a transzponálást egy eltolás egészíti ki ( T"+S"):

Meg kell jegyezni, hogy mindkét algoritmus iterációja összeadódó formában írható fel, ha a bináris kombinációkat egész számokként értelmezzük a 2-es alapszámrendszerben. Különösen a jobbra tolással rendelkező transzpozíciós algoritmus esetén minden következő bináris kombináció (B" n ,…B" j , …B" 1), mindig megkapható az aktuális (B n,…B j,…B 1) kombinációból az egész számok összeadási műveleteinek végrehajtásával a következő additív képlet segítségével:

Ebben az additív képletben az f és t kettős hatványok kitevői az aktuális bináris kombináció alacsony rendű nulla számjegyeinek számát, illetve a tőlük balra lévő sorban lévő egyesek számát jelölik. Például az n=6 számjegyből álló 4. bináris kombinációhoz (001110) f =1 és t =3. Ezért a következő bináris kombináció kiszámítása az additív képlet segítségével az 5. iterációnál a következő eredményt kapja, ami egyenértékű a transzponálási és eltolási műveletek végrehajtásával:

A balra és jobbra eltolt transzpozíciós algoritmusok összehasonlító elemzéséhez tanácsos összehasonlítani az iterációik során generált bináris kombinációk sorozatait. A következő táblázat két ilyen bináris szekvenciát mutat be 4 elemből 2-ből, amelyeket a bal (TSL) és jobb (TSR) eltolási algoritmusok kapnak:

Ha összehasonlítja ezt a 2 sorozatot, láthatja, hogy ezek fordított tükör. Ez azt jelenti, hogy bármely két bináris kombináció, amely azonos távolságra helyezkedik el bennük sorozataik egymással ellentétes végétől, egymás tükörképe, vagyis egybeesik, ha bármelyikben a bitek indexelése megfordul. Például a második bináris minta a TSL sorozat elejétől (0101) a bináris minta (1010) tükörképe, amely a második a TSR sorozat végétől számítva. Általánosságban elmondható, hogy bármely bináris kombináció egy sorozat i számával egy másik sorozat (ni+1) számával rendelkező bináris kombináció tükörképe. Ez a kapcsolat a sorozatok között a transzpozíciós és eltolási műveletek szimmetrikus jellegének a következménye a két vizsgált bináris kombinációk felsorolására szolgáló algoritmusban.

Meg kell jegyezni, hogy a bináris formátum az elemek ismétlődését tartalmazó kombinációk rögzítésére is használható. Ehhez egy az egyhez megfeleltetést kell létrehozni az ismétlődő kombinációk és a bináris kombinációk között, amelyek a következőképpen épülnek fel. Legyen egy tetszőleges kombináció ismétlődésekkel, amelyet úgy kapunk, hogy a generáló halmaz n eleme közül m opcionálisan eltérő elemet választunk. A kívánt egyezés megállapításához először hozzá kell adni a kombinációhoz a formáló halmaz (cat) összes elemét, majd a kapott összefűzést (rendezés) úgy kell rendezni, hogy az összes azonos elem egymás mellett legyen. Az eredmény egy (n+m) elemből álló sorozat, ahol n darab azonos elemcsoport van. Összesen (n+m1) rés lesz az elemek között, amelyek között (n1) rés lesz az azonos elemekből álló csoportok között és m rés a csoportokon belüli elemek között. Az egyértelműség kedvéért a „|” szimbólumokat elhelyezheti a jelzett helyeken. és ennek megfelelően. Ha most az 1-et a csoportok közötti szóközökhöz (|), a 0-t pedig az összes többi szóközhöz () illesztjük, bináris kombinációt kapunk. Egy (n+m1) bitből álló bináris halmaz alkotja, ahol (n1) egyesek és m nulla bitek, amelyek helye egyértelműen megfelel az eredeti kombinációnak, n-től m-ig ismétlődő elemek. A vizsgált transzformációs technikát a következő példa szemlélteti egy bináris kombináció (1001101) létrehozására ismétlésekkel (BBD) használva, amelynek elemeit az első öt latin betű generátorkészletéből választjuk ki:

Általában az ilyen bináris halmazok száma határozza meg, hogy hány módon lehet (n1) egyeseket (vagy m nullát) elrendezni (n+m1) bináris számjegyekben. Ez az érték nyilvánvalóan megegyezik az (n+m1) és az (n1) vagy m kombinációk számával, azaz C(n+m1,n1) vagy C(n+m1,m), ami egyenlő a kombinációk száma f( n,m) ismétlődéssel n elemből, mindegyik m. Így, mivel az ismétlődő kombinációk és a bináris kombinációk egy az egyhez megfelelnek, jogos az ismétlődő kombinációk felsorolását a bináris kombinációk felsorolására redukálni, például balra vagy jobbra eltolású transzponálási algoritmusok használatával. Ezt követően már csak a szükséges kombinációkat kell visszaállítani ismétlésekkel a kapott bináris kombinációk segítségével. Ez mindig megtehető a következő helyreállítási technikával.

A főhalmazt, amelynek elemeiből m-es ismétlődésű kombinációk keletkeznek, nem feltétlenül különböző elemekkel, tetszőlegesen rendezzük úgy, hogy minden elemének egy bizonyos sorszáma legyen 1-től n-ig. Valósítsuk meg az (n+m1) bináris számjegyek bináris kombinációinak felsorolását is, ahol (n1) egyesek és m nulla számjegy. Minden eredményül kapott bináris kombináció kiegészíthető a bal oldalon egy fiktív egység számjeggyel, és az összes egységjegy számozható balról jobbra 1-től n-ig terjedő egész számokkal. Ekkor a bináris kombináció minden i-edik egysége után egy sorban lévő nullák száma megegyezik a fő halmaz i-edik elemének előfordulásainak számával a megfelelő kombinációban ismétlődésekkel. A vizsgált technikát a következő példa szemlélteti, ahol egy bináris kombináció (1001101) használatával a BBD ismétlődéseit tartalmazó kombinációt állítanak vissza, amelynek elemeit az első öt latin betű generátorkészletéből választják ki, ábécé sorrendben. , és az overline azokat az elemeket jelöli, amelyek hiányoznak ebből a kombinációból:

Ha hasonló műveleteket hajt végre ebben a példában, akkor listázhatja mind a 35 bináris kombinációt, amelyek 7 bites bináris halmazokat alkotnak, ahol 4 egyes és 3 nulla található, és visszaállíthatja a megfelelő kombinációkat 5 elem 3 ismétlésével.

Előző cikk: Mekkora a fénysebesség Következő cikk: Harmonikus rezgések Az oszcillációs frekvencia fizikai képlete