A kombináció egy véges halmaz elemeinek rendezetlen, rögzített számmal és elemismétlődés nélküli válogatása. 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ó, hogy 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 egy 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 igazságos. 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|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0. Ha most beállítjuk a Z=X/Y-t, és a bal és jobb oldalt megszorozzuk 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 nemnegatív egész hatványaira őrzi meg kombinatorikus jelentését. Ebben az esetben a binomiális együtthatók több hasznos azonosságának bizonyítására használható. 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 fent. A hiányzó felső index összegzési azonossága könnyen megkapható 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öghöz kapcsolódik.
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ájú:
Á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 a következő végtelen számú binomiális együttható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ű alakos 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ÓINAK 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ást követő 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 szemlélteti 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ás akkor sem történik meg, ha a transzponálás után kapott 10 pár előtt a legjelentősebb bitekben nincsenek nullák. 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 rendre az aktuális bináris kombináció kisrendű 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. Példa // 52-ből 3-as kombinációk erre: (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Itt egy összetettebb problémát fogunk megvizsgálni, aminek a megoldását a RuNetben nem találtam meg (egy hivatkozást azonban adok, de ez a képlet egyértelműen hibás) - maga a kombináció (jelen esetben egy halmaz) alapján. három szám) keresse meg az indexét. Tegyük fel a határozottság kedvéért, hogy i1 = 3, i2 = 7, i3 = 12 rendezés után. Egy tipikus generálási algoritmus az, hogy 52-ből 2 kombinációt generálunk, és egy beágyazott ciklusban minden ilyen kombinációhoz 50-ből 3 kombinációt generálunk, és ellenőrizzük, hogy az indexek (i3, i4, i5) a beágyazott kombinációban nem esnek egybe az indexekkel (i1, i2) külső kombinációban: C++ kód // KÜLSŐ KOMBINÁCIÓ for (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
C++ kód if (i3 >= i1) --i3; if (i3 >= i2) --i2; // hasonló az i4-hez, i5-höz Példakód az index felosztásához 2-vel, 3-mal, 47-tel int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Az 52-ből 2 kombinációjának indexe, szorozva C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600 // „Újraindexelje” a belső csoportot úgy, hogy a számozás 0...49 legyen, ha (i3 >= i1; ) --i3 (i3 >= i2) --i3 if (i5 >= i2) --i5; 0: // ÖSSZEG, n = 0 x i3-1 KOMBINÁCIÓK (2, 49-n) // = SZUM, m = 50-i3 x 49 (m * (m-1) / 2) eltolás += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) // 1: / 2); / ÖSSZEG n = i3+1 - i4-1 KOMBINÁCIÓK (1, 49-n) eltolása += (((48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); Általában a kombinatorikus algoritmusokat a következő osztályokra osztanám: 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 kisebb, 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. Az első sorban egy páros természetes szám található M – az ellopott hüvelyek száma, 2 ≤ M ≤ 1000. 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. #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 ; 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 szempontokat 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 megjelenítjük a barátok által hozott podok számának összes lehetséges kombinációját, soronként egyet, az első szám csökkenő sorrendjében. 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. 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: Wikimédia Alapítvány. 2010. 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 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 halmazból kiválasztott, különböző elemeket tartalmazó 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. EfronKombinációs index
Minden kombináció, permutáció, elrendezés és egyéb kombinatorikus objektumok társíthatók egy indexhez - ebben a számban jelenik meg az algoritmuson keresztüli iteráció során.
Lehetőség van a „fejjel” keresésre. Bekapcsoljuk a kombinációszámlálót, vesszük a fenti algoritmust, és mindent megpróbálunk, amíg el nem érjük a kívánt opciót. Ennek az opciónak nagyon nagy az időbonyolítása, ezért ezt a lehetőséget elvetjük.
Tegyük fel, hogy a bemenet i1, i2, i3 számokat tartalmaz. Először is növekvő sorrendbe kell őket rendeznünk (megjegyzendő, hogy maga a fentebb megadott generálási algoritmus mindig rendezett formában állítja elő őket, bár maga a „kombináció” fogalma tetszőleges sorrendet feltételez).
Ez azt jelenti, hogy „átmentünk” minden olyan kombináción, ahol i1 0, 1 és 2 volt.
Ha i1 = 0, végigmentünk a C(2, 51) kombinációkon, mivel az i1, i2 indexek az 51 számból 2 összes kombinációján végigmennek.
Az i1 = 1 esetén C(2, 50) kombinációkon mentünk keresztül.
Az i1 = 2 esetén C(2, 49) kombinációkon mentünk keresztül.
Összességében a SUM-on mentünk keresztül (n = 0-tól n = i1-1-ig) C(2, 51-n).
Az i1 = 3 esetén vegyük figyelembe azokat a kombinációkat, amelyeken az i2 indexen keresztül mentünk (és nálunk i2 = i1+1 = 4-el kezdődik).
Ha i2 = 4, akkor a C(1, 47) kombinációk sikeresek, ha az i2 = 5, a C(1, 46) kombinációk, ha az i2 = 6, a C(1, 45) kombinációk.
Teljes analógia alapján i2 = 7 esetén azokat a kombinációkat vesszük figyelembe, amelyeken az i3 index átfutott.
Az általános képletet kapjuk:
A szükséges kombinációs index = SUM (n = 0-tól i1-1-ig) C(2, 51-n) + SZUM (n = i1+1-től i2-1-ig) C(1, 51-n) + SZUM (tól n = i2+1-től i3-1-ig) C (0, 51-n).Részhalmaz indexe
A kombinatorikában van egy bonyolultabb objektum - részhalmazokra particionálás. Például egy 52 elemből álló halmaz felosztása három, mondjuk 2, 3 és 47 elemből álló részhalmazra, ahol az elemek sorrendje az egyes részhalmazokon belül nem fontos. (Mellesleg, az 52-ből 2 kombinációja egyszerűen egy speciális eset, amikor két, illetve 50 elemből álló részhalmazra oszlik fel).
Ismét minden ilyen partíciónak saját indexe van.
Kiderült, hogy a kombinációs index megtalálására szolgáló algoritmusunk módosítható a partícióindex megtalálásához.
Megjegyzendő, hogy az i1, i2 „külső kombináció” indexeit egymás között, az i3, i4, i5 indexeket pedig egymás között, de az első kettőtől függetlenül kell rendeznünk.
Azt is figyelembe kell venni, hogy „beágyazott kombinációban” lényegében 50 elemű halmazzal dolgozunk, de az i3, i4, i5 indexeket bizonyos módon „el kell tolni”, hogy ne 0-ról változzanak. 51-ig, de 0-tól 49-ig:
(úgymond kivágjuk az i1, i2 indexeket az 52 elemű halmazunkból, majd a maradék halmazt eltoljuk a lyukak bezárásához, míg az i3-i5 indexeket eltoljuk).
Figyelembe kell venni, hogy minden „külső” kombináción belül pontosan C(3, 50) „beágyazott” kombinációink vannak.
Ezután az algoritmus a következőre redukálódik:
COMBINATION_INDEX (i1, i2/52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5/50 indexeltolás után). Az algoritmusok állandó összetettsége
Azonnal meg kell jegyeznem, hogy „hiba” fordul elő a képletben, ha például i1 = 0 (az n = 0 és -1 közötti összeget számoljuk) vagy i2 = 1 (az összeget 1-től 0-ig számoljuk). Valójában ilyen esetekben a megfelelő összeget nullának kell venni, és az eredmény helyes lesz.
Figyelmet kell fordítanom algoritmusaink időbonyolultságára is: lineáris komplexitásúak, feltéve, hogy C-t állandó időnek tekintjük. Ez már sokkal jobb, mint a nyers erő.
De valójában (esetünkben 52) semmi sem akadályoz meg bennünket abban, hogy az algoritmust állandó komplexitásra redukáljuk. Ehhez a matematikai ismereteket alkalmazzuk, és analitikusan kiszámítjuk az összes összeget.
Például a C(2, K) kombinációk számát, ha K képlet formájában „bővíted”! / ((K-2)! * 2!), 2. fokú polinomra redukál. És mivel ez az összeg jele alatt van, alkalmazhatjuk a számok N-edik hatványainak összegére vonatkozó képleteket a természetes sorozatban (lásd Wikipédia), és egyetlen 3. fokú polinomot kapunk. Aminek nyilván állandó az időbonyolultsága. (Ráadásul az a „hiba”, amit az alcím elején idéztem, semmiképpen nem nyilvánul meg, a képlet helyes marad).
Ismétlem, ezt az alapkészlet rögzített méretéhez. Abban azonban biztos vagyok, hogy a metaprogramozás segítségével meg tudod „tanítani” a fordítót úgy, hogy az elvégezze ezt a munkát. Utószó
A pókerszimulátoromban (Texas Hold'em) előre ki akartam számítani és eltárolni a nyerési valószínűségeket a kézkártyáim (2 db) és az összes flop kártya (3 lap az asztalon) esetén. Ez az osztódásnak felel meg az 52-es halmaz 2, 3, 47 részhalmazokkal.
Kiszámolva és elmentve.
De amikor eljött az idő, hogy egy adott kombinációhoz adatokat olvassam ki egy fájlból, nem akartam sokáig számolni valamit, vagy gigabájtos fájlban keresni. Most csak meghatározom az eltolást a fájlban, és közvetlenül elolvasom, amire szükségem van.
Érdekes lenne egy referenciakönyv a kombinatorikus algoritmusokról minden kombinatorikus objektumhoz, beleértve a permutációkat, kombinációkat, elhelyezéseket, részhalmazokat, kombinációkat ismétlődésekkel, elhelyezéseket ismétlődésekkel. Beviteli adat
Kimenet
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
Program kód
A probléma megoldása
Explicit képletek
Linkek
Nézze meg, mi a „Kombinációk száma” más szótárakban:
Könyvek
