Ktorýkoľvek z N prvkov môže byť na prvom mieste v rade, preto sa získa N možností. Na druhom mieste - akékoľvek, okrem toho, ktorý už bol použitý na prvé miesto. Preto pre každú z už nájdených N možností existuje (N - 1) možností druhého miesta a celkový počet kombinácií bude N*(N - 1).
To isté možno zopakovať pre zostávajúce prvky série. Na úplne posledné miesto ostáva už len jediná možnosť – posledný zostávajúci prvok. Pre predposledné - dve možnosti atď.
Preto pre sériu N neopakujúcich sa prvkov sú možné permutácie rovné súčinu všetkých celých čísel od 1 do N. Tento súčin sa nazýva N a N! (čítaj „en faktoriál“).
V predchádzajúcom prípade číslo možné prvky a počet miest v sérii sa zhodoval a ich počet bol rovný N. Ale je možná situácia, keď je v sérii menej miest, ako je možných prvkov. Inými slovami, počet prvkov vo vzorke sa rovná nejakému číslu M a M< N. В этом случае задача определения возможных комбинаций может иметь два различных варианта.
Najprv môže byť potrebné spočítať celkovú sumu možné spôsoby, pomocou ktorého môžete zoradiť M prvkov z N. Takýmito metódami sú umiestnenia.
Po druhé, výskumníka môže zaujímať počet spôsobov, akými možno vybrať M prvkov z N. V tomto prípade už nie je dôležité poradie prvkov, ale akékoľvek dve možnosti sa musia od seba líšiť aspoň o jeden prvok. . Takéto metódy sa nazývajú kombinácie.
Na nájdenie počtu umiestnení podľa M prvkov z N sa možno uchýliť k rovnakému spôsobu uvažovania ako v prípade permutácií. Na prvom mieste môže byť ešte N prvkov, na druhom (N - 1) atď. Ale na poslednom mieste nie je počet možných možností jeden, ale (N - M + 1), pretože po dokončení umiestnenia budú stále (N - M) nevyužité prvky.
Počet umiestnení nad M prvkami od N sa teda rovná súčinu všetkých celých čísel od (N - M + 1) po N, alebo ekvivalentne podielu N!/(N - M)!.
Je zrejmé, že počet kombinácií prvkov M z N bude menší ako počet umiestnení. Pre každú možnú kombináciu existuje M! možné umiestnenia v závislosti od poradia prvkov tejto kombinácie. Preto, aby ste našli toto číslo, musíte vydeliť počet umiestnení na M prvkov z N číslom N!. Inými slovami, počet kombinácií prvkov M z N je N!/(M!*(N - M)!).
Zdroje:
- počet kombinácií
Faktorový prirodzené číslo je súčinom všetkých predchádzajúcich prirodzených čísel, vrátane čísla samotného. Faktorový nula sa rovná jednej. Zdá sa, že výpočet faktoriálu čísla je veľmi jednoduchý – stačí vynásobiť všetky prirodzené čísla, ktoré nepresahujú dané. Hodnota faktoriálu však rastie tak rýchlo, že niektoré kalkulačky si s touto úlohou nevedia poradiť.
Budete potrebovať
- kalkulačka, počítač
Poučenie
Ak chcete vypočítať faktoriál prirodzeného čísla, vynásobte všetky, ktoré nepresahujú dané číslo. Každé číslo sa počíta iba raz. Vo forme vzorca to možno zapísať takto: n! = 1*2*3*4*5*…*(n-2)*(n-1)*n, kde n je prirodzené číslo, ktorého faktoriál sa má vypočítať.
0! sa berie ako jedna (0!=1).S rastúcim argumentom sa hodnota faktoriálu veľmi rýchlo zvyšuje, takže obvyklý (účtovný) faktoriál 15 namiesto výsledku môže spôsobiť chybu.
Ak chcete vypočítať faktoriál veľkého prirodzeného čísla, vezmite si inžiniersku kalkulačku. Teda taká kalkulačka, na ktorej klávesnici sú symboly matematických funkcií (cos, sin, √). Zadajte pôvodné číslo na kalkulačke a potom kliknite na tlačidlo faktoriálu. Zvyčajne tlačidlo ako "n!" alebo podobne (namiesto „n“ môže byť „N“ alebo „x“, ale výkričník „!“ v zápise faktoriálu musí byť v každom prípade prítomný).
o veľké hodnoty argument, výsledky výpočtov sa začnú zobrazovať v „exponenciálnej“ (exponenciálnej) forme. Takže napríklad faktoriál 50 by bol v tvare: 3,0414093201713378043612608166065e+64 (alebo podobný). Ak chcete získať výsledok výpočtov v obvyklej forme, pridajte toľko núl k číslu zobrazenému pred symbolom "e", ako je uvedené za "e +" (ak je, samozrejme, dostatok miesta).
Niekedy si vyberáme z mnohých bez ohľadu na poradie. Takáto voľba je tzv kombinácia . Ak napríklad hráte karty, viete, že vo väčšine situácií na poradí, v akom karty držíte, nezáleží.
Príklad 1 Nájdite všetky kombinácie 3 písmen prevzatých zo sady 5 písmen (A, B, C, D, E).
rozhodnutie Tieto kombinácie sú:
(A, B, C), (A, B, D),
(A, B, E), (A, C, D),
(A, C, E), (A, D, E),
(B, C, D), (B, C, E),
(B, D, E), (C, D, E).
Existuje 10 kombinácií troch písmen, vybraných z piatich písmen.
Keď nájdeme všetky kombinácie z množiny s 5 objektmi, ak vezmeme 3 objekty naraz, nájdeme všetky 3-prvkové podmnožiny. V tomto prípade sa neberie do úvahy poradie objektov. potom
(A, C, B) sa nazýva rovnaká množina ako (A, B, C).
Podmnožina
Množina A je podmnožinou B a znamená, že A je podmnožinou a/alebo je rovnaká ako B, ak každý prvok A je prvkom B.
Prvky podmnožiny nie sú usporiadané. Pri zvažovaní kombinácií sa neberie do úvahy objednávka!
Kombinácia
kombinácia,
obsahujúci k objektov je podmnožina pozostávajúca z k objektov.
Chceme napísať vzorec na výpočet počtu kombinácií n objektov, ak sa súčasne vezme k objektov.
Kombinovaný zápis
Počet kombinácií n objektov, ak sa zoberú súčasne, označíme n C k .
Nazývame n C k počet kombinácií . Chceme napísať všeobecný vzorec pre n C k pre ľubovoľné k ≤ n. Po prvé, platí, že n C n = 1, pretože množina s n prvkami má iba jednu podmnožinu s n prvkami, je množina samotná. Po druhé, n C 1 = n, pretože množina s n prvkami má iba n podmnožín s 1 prvkom. Nakoniec n C 0 = 1, pretože množina s n prvkami má iba jednu podmnožinu s 0 prvkami, teda prázdnu množinu ∅. Aby sme zvážili ďalšie kombinácie, vráťme sa k príkladu 1 a porovnajme počet kombinácií s počtom permutácií.
Všimnite si, že každá kombinácia 3 prvkov má 6 alebo 3!, permutácií.
3! . 5 C 3 \u003d 60 \u003d 5 P 3 \u003d 5. 4. 3,
tak 
.
Vo všeobecnosti by sa počet kombinácií k prvkov vybraných z n objektov, n C k krát permutácií týchto prvkov k!, mal rovnať počtu permutácií n prvkov na k prvkom:
k!. n C k = n P k
n C k = n P k / k!
nCk = (1/k!). nP k
n Ck = 
Kombinácie k objektov z n objektov
Celkový počet kombinácií k prvkov z n objektov sa označí n C k , určeným
(1) n C k = ,
alebo
(2) n C k = 
Iný typ zápisu pre n C k je binomický koeficient . Dôvod tejto terminológie bude objasnený nižšie.
Binomický koeficient
Príklad 2 Vypočítajte pomocou vzorcov (1) a (2).
rozhodnutie
a) Podľa (1) 
.
b) Podľa (2), 
Majte na pamäti, že to neznamená n/k.
Príklad 3 Vypočítajte a .
rozhodnutie Pre prvý výraz použijeme vzorec (1) a pre druhý vzorec (2). Potom 
,
pomocou (1) a 
,
pomocou vzorca (2).
poznač si to 
,
a použitím výsledku z príkladu 2 dostaneme
.
To znamená, že počet 5-prvkovej podmnožiny množiny 7 prvkov je rovnaký ako počet 2-prvkovej podmnožiny množiny 7 prvkov. Keď je vybratých 5 prvkov zo sady, nezahŕňajú 2 prvky. Aby ste to videli, zvážte množinu (A, B, C, D, E, F, G): 
Vo všeobecnosti máme nasledovné. Tento výsledok dáva alternatívny spôsob kombinačné výpočty.
Podmnožiny veľkosti k a veľkosti
a nCk = nCn-k
Počet podmnožín veľkosti k množiny s n objektmi je rovnaký ako počet podmnožín veľkosti n - k Počet kombinácií k objektov z množiny n objektov je rovnaký ako počet kombinácií n predmety odobraté v rovnakom čase.
Teraz budeme riešiť problémy s kombináciami.
Príklad 4 Michiganská lotéria. WINFALL sa koná v Michigane dvakrát týždenne a má jackpot vo výške najmenej 2 milióny dolárov. Za jeden dolár si hráč môže preškrtnúť ľubovoľných 6 čísel od 1 do 49. Ak sa tieto čísla zhodujú s číslami, ktoré padnú počas lotérie, hráč vyhráva. (
Počet kombinácií
kombinácia od n na k volal súpravu k prvky vybrané z údajov n prvkov. Sady, ktoré sa líšia iba poradím prvkov (nie však zložením), sa považujú za rovnaké, a preto sa kombinácie líšia od umiestnení.
Explicitné vzorce
Počet kombinácií od n na k sa rovná binomickému koeficientu
Za pevnú hodnotu n generujúca funkcia počtov kombinácií s opakovaniami z n na k je:
Dvojrozmerná generujúca funkcia počtu kombinácií s opakovaniami je:
Odkazy
- R. Stanley Enumeratívna kombinatorika. - M.: Mir, 1990.
- Výpočet počtu kombinácií online
Nadácia Wikimedia. 2010.
Pozrite sa, čo je "Počet kombinácií" v iných slovníkoch:
70 sedemdesiat 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Faktorizácia: 2×5×7 Rímsky zápis: LXX Binárny: 100 0110 ... Wikipedia
Svetlé číslo, podmienené číslo, ktoré jednoznačne vyjadruje vonkajšie. podmienky pri fotografovaní (zvyčajne jas objektu a citlivosť použitého fotografického materiálu). Akákoľvek hodnota E. h. môže byť zvolená z niekoľkých. kombinácie clonových čísel ... ... Veľký encyklopedický polytechnický slovník
Forma čísla, ktorá rozlišuje dva objekty vo vzťahu k jednému objektu aj vo vzťahu k množstvu objektov. Táto forma v modernej ruštine neexistuje, ale zachovali sa zvyšky jej vplyvu. Takže kombinácie dvoch tabuliek (porov. množné číslo ... ... Slovník lingvistických pojmov
Kombinatorická matematika, kombinatorika, odbor matematiky venovaný riešeniu úloh výberu a usporiadania prvkov určitej, spravidla konečnej, množiny podľa daných pravidiel. Každé takéto pravidlo určuje spôsob konštrukcie ... ... Matematická encyklopédia
V kombinatorike je kombináciou by množina prvkov vybraných z danej množiny obsahujúcej rôzne prvky. Zostavy, ktoré sa líšia iba poradím prvkov (nie však zložením) sa považujú za rovnaké, tieto kombinácie ... ... Wikipedia
Zaoberá sa štúdiom udalostí, ktorých výskyt nie je s určitosťou známy. Umožňuje vám posúdiť primeranosť očakávania výskytu niektorých udalostí v porovnaní s inými, hoci priraďovanie číselných hodnôt pravdepodobnostiam udalostí je často nadbytočné ... ... Collierova encyklopédia
1) rovnako ako matematická kombinatorická analýza. 2) Sekcia elementárna matematika, spojené so štúdiom počtu kombinácií podliehajúcich určitým podmienkam, ktoré možno poskladať z danej konečnej množiny objektov ... ... Veľká sovietska encyklopédia
- (grécky paradoxos neočakávaný, zvláštny) v širšom zmysle: vyhlásenie, ktoré je ostro v rozpore so všeobecne uznávaným, ustáleným názorom, popieranie toho, čo sa zdá byť „nepochybne správne“; v užšom zmysle dva protikladné výroky, za ... ... Filozofická encyklopédia
- (alebo princíp inklúzií vylúčení) kombinatorický vzorec, ktorý umožňuje určiť silu spojenia konečného počtu konečných množín, ktoré sa vo všeobecnom prípade môžu navzájom prelínať ... Wikipedia
Matematická teória zaoberajúca sa definíciou čísla rôznymi spôsobmi distribúcia týchto položiek v známom poradí; má osobitný význam v teórii rovníc a v teórii pravdepodobnosti. Najjednoduchšie úlohy tohto druhu sú ... ... encyklopedický slovník F. Brockhaus a I.A. Efron
knihy
- Osudové číslo. Horoskop kompatibility. Túžby. Vášeň. Fantasy (počet zväzkov: 3), Maier Maxim. Osudové číslo. Ako urobiť individuálnu numerologickú predpoveď. Numerológia je jedným z najstarších ezoterických systémov. Nie je možné presne určiť čas jeho výskytu. Avšak v…
Kombinácia je neusporiadaný výber prvkov konečnej množiny s pevným počtom a bez opakovania prvkov. Rôzne kombinácie sa musia líšiť aspoň o jeden prvok a na poradí prvkov nezáleží. Napríklad zo súboru všetkých samohlások latinských písmen (AEIOU) možno vytvoriť 10 rôznych kombinácií 3 písmen, ktoré tvoria nasledujúce neusporiadané trojice:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Je zaujímavé poznamenať, že z rovnakých piatich písmen môžete získať aj 10 rôznych kombinácií, ak z nich skombinujete 2 písmená, čím vytvoríte nasledujúce neusporiadané páry:
AE, AI, AO, AU, EI, EO, EÚ, IO, IU, OU.
Ak však skombinujete rovnaké latinské samohlásky o 4, získate iba nasledujúcich 5 rôznych kombinácií:
AEIO, AEIU, AIOU, EIOU, AEOU.
Vo všeobecnom prípade sa na označenie počtu kombinácií n rôznych prvkov m prvkami používa nasledujúca funkčná, indexová alebo vektorová (Appel) symbolika:
Bez ohľadu na formu označenia možno počet kombinácií n prvkov na m prvkov určiť pomocou nasledujúcich multiplikatívnych a faktoriálnych vzorcov:
Je ľahké skontrolovať, či sa výsledok výpočtov pomocou týchto vzorcov zhoduje s výsledkami vyššie uvedeného príkladu s kombináciami latinských samohlások. Najmä pre n=5 a m=3 výpočty pomocou týchto vzorcov poskytnú tento výsledok:
Vo všeobecnom prípade majú vzorce pre počet kombinácií kombinatorický význam a sú platné pre akékoľvek celočíselné hodnoty n a m tak, že n > m > 0. Ak m > n a m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Okrem toho je užitočné zapamätať si nasledujúce limitné počty kombinácií, ktoré sa dajú ľahko skontrolovať priamou substitúciou do multiplikatívnych a faktoriálnych vzorcov:
Treba tiež poznamenať, že multiplikatívny vzorec zostáva platný, aj keď n je reálne číslo, pokiaľ m je stále celé číslo. Potom však výsledok výpočtu na ňom pri zachovaní formálnej platnosti stráca kombinačný význam.
KOMBINAČNÉ IDENTITY
Praktické využitie multiplikatívnych a faktoriálnych vzorcov na určenie počtu kombinácií pre ľubovoľné hodnoty n a m nie je príliš produktívne z dôvodu exponenciálneho rastu faktorových súčinov ich čitateľa a menovateľa. Aj pre relatívne malé hodnoty n a m tieto produkty často presahujú možnosti reprezentácie celých čísel v moderných výpočtových a softvérových systémoch. Zároveň sa ukáže, že ich hodnoty sú oveľa väčšie ako výsledná hodnota počtu kombinácií, ktorá môže byť relatívne malá. Napríklad počet kombinácií n=10 pomocou m=8 prvkov je len 45. Ak však chcete nájsť túto hodnotu pomocou faktoriálneho vzorca, musíte najskôr vypočítať oveľa väčšie hodnoty 10! v čitateli a 8! v menovateli:
Ak chcete vylúčiť časovo náročné operácie spracovania veľkých hodnôt, určiť počet kombinácií, môžete použiť rôzne vzťahy opakovania, ktoré priamo vyplývajú z multiplikatívnych a faktoriálnych vzorcov. Z multiplikatívneho vzorca vyplýva najmä nasledujúci rekurentný vzťah, ktorý nám umožňuje vziať pomer jeho indexov za znamienko počtu kombinácií:
Nakoniec, ponechanie dolného indexu nezmenené poskytuje nasledujúci vzťah opakovania, ktorý možno ľahko získať z faktoriálneho vzorca pre počet kombinácií:
Po elementárnych transformáciách môžu byť tri výsledné rekurentné vzťahy reprezentované v nasledujúcich formách:
Ak teraz spočítame ľavú a pravú časť prvých 2 vzorcov a znížime výsledok o n, dostaneme dôležitý rekurentný vzťah, ktorý sa nazýva identita sčítania čísel kombinácií:
Identita sčítania poskytuje základné rekurzívne pravidlo pre efektívna definícia počet kombinácií pre veľké hodnoty n a m, pretože nám umožňuje nahradiť operácie násobenia vo faktoriálnych súčinoch jednoduchšími operáciami sčítania a pre menšie počty kombinácií. Najmä pomocou adičnej identity je teraz ľahké určiť počet kombinácií n = 10 pomocou m = 8 prvkov, ktoré boli uvažované vyššie, vykonaním nasledujúcej postupnosti opakujúcich sa transformácií:
Okrem toho je možné zo sčítacej identity odvodiť niekoľko užitočných vzťahov na výpočet konečných súčtov, najmä vzorec súčtu dolného indexu, ktorý má nasledujúci tvar:
Takýto vzťah sa získa rozšírením opakovania v adičnej identite cez výraz s najväčším horným indexom, pokiaľ je jeho dolný index väčší ako 0. Nasledujúci číselný príklad ilustruje naznačený proces rekurzívnych transformácií:
Na výpočet súčtu mocnin prirodzených čísel sa často používa sumačný vzorec dolného indexu. Najmä za predpokladu, že m = 1, pomocou tohto vzorca je ľahké nájsť súčet prvých n čísel prirodzeného radu:
Ďalší užitočná možnosť sčítacie vzorce možno získať rozšírením opakovania adičnej identity cez člen s najmenším horným indexom. Nasledujúci číselný príklad ilustruje tento variant opakujúcich sa transformácií:
Vo všeobecnom prípade sa v dôsledku takýchto transformácií získa súčet počtov kombinácií, ktorých oba indexy sa líšia od susedných členov o jednu a rozdiel indexov zostáva konštantný (v uvažovanom príklade je to tiež rovná jednej). Takto sa získa nasledujúci sumačný vzorec pre oba indexy kombinačných čísel:
Okrem vyššie uvedených vzťahov opakovania a sumačných vzorcov sa v kombinatorickej analýze získalo mnoho ďalších užitočných identít pre kombinačné čísla. Najdôležitejší z nich je identita symetrie, ktorý má nasledujúci tvar:
Platnosť identity symetrie je možné vidieť v nasledujúcom príklade porovnaním počtu kombinácií 5 prvkov o 2 a podľa (5 2) = 3:
Identita symetrie má zrejmý kombinatorický význam, pretože pri určovaní počtu možností výberu m prvkov z n prvkov súčasne stanovuje počet kombinácií zo zostávajúcich (nm) nevybraných prvkov. Uvedená symetria sa okamžite získa vzájomným nahradením m za (nm) vo faktoriálnom vzorci pre počet kombinácií:
Čísla a kombinované identity sú široko používané v rôznych oblastiach modernej výpočtovej matematiky. Ich najobľúbenejšia aplikácia je však spojená s Newtonovým binomickým a Pascalovým trojuholníkom.
BINOMIÁLNA VETA
Na vykonávanie rôznych matematických transformácií a výpočtov je dôležité vedieť znázorniť akúkoľvek prirodzenú mocninu algebraického binomu (binómu) vo forme polynómu. Pre malé stupne možno požadovaný polynóm ľahko získať priamym vynásobením binómov. Z kurzu elementárnej matematiky sú známe najmä tieto vzorce pre druhú a druhú mocninu súčtu dvoch členov:
Vo všeobecnom prípade, pre ľubovoľný stupeň n binomu, požadované zobrazenie vo forme polynómu poskytuje Newtonova binomická veta, ktorá deklaruje, že platí nasledujúca rovnosť:
Táto rovnosť sa zvyčajne nazýva Newtonova binoma. Polynóm na pravej strane je súčtom súčinov n členov X a Y binomu na ľavej strane a koeficienty pred nimi sa nazývajú binomické a rovnajú sa počtu získaných kombinácií s indexmi. z ich právomocí. Vzhľadom na mimoriadnu popularitu Newtonovho binomického vzorca v kombinatorickej analýze sa pojmy binomický koeficient a počet kombinácií zvyčajne považujú za synonymá.
Je zrejmé, že vzorec súčtu štvorca a kocky sú špeciálnymi prípadmi binomickej vety pre n=2 a n=3. Na zvládnutie vyšších mocnín (n>3) by sa mal použiť Newtonov binomický vzorec. Jeho použitie pre binomické číslo štvrtého stupňa (n=4) je demonštrované na nasledujúcom príklade:
Treba poznamenať, že binomický vzorec poznali ešte pred Newtonom stredovekí matematici arabského východu a západná Európa. Preto jeho zaužívaný názov nie je historicky správny. Newtonovou zásluhou je, že zovšeobecnil tento vzorec na prípad ľubovoľného reálneho exponentu r, ktorý môže nadobúdať akékoľvek kladné alebo záporné racionálne a iracionálne hodnoty. Vo všeobecnom prípade má takýto Newtonov binomický vzorec na pravej strane nekonečný súčet a je zvykom ho písať takto:
Napríklad s kladnou zlomkovou hodnotou exponentu r = 1/2, berúc do úvahy hodnoty binomických koeficientov, sa získa nasledujúca expanzia:
Vo všeobecnom prípade je Newtonov binomický vzorec pre akýkoľvek exponent konkrétnou verziou Maclaurinovho vzorca, ktorý udáva rozšírenie ľubovoľnej funkcie v mocninnom rade. Newton ukázal, že pre |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0. Ak teraz dáme Z=X/Y a vynásobíme ľavú a pravú stranu Yn, dostaneme variant Newtonovho binomického vzorca diskutovaného vyššie.
Napriek svojej univerzálnosti si binomická veta zachováva svoj kombinatorický význam iba pre celočíselné nezáporné mocniny binomiky. V tomto prípade sa môže použiť na preukázanie niekoľkých užitočných identít pre binomické koeficienty. Vyššie boli zvážené najmä súčtové vzorce pre počty kombinácií podľa nižšieho indexu a podľa oboch indexov. Chýbajúcu súčtovú identitu horného indexu možno ľahko získať z Newtonovho binomického vzorca nastavením X = Y = 1 alebo Z = 1:
Ďalšia užitočná identita stanovuje rovnosť súčtov binomických koeficientov s párnymi a nepárnymi číslami. Okamžite sa získa z Newtonovho binomického vzorca, ak X = 1 a Y = 1 alebo Z = 1:
Nakoniec, z oboch uvažovaných identít sa získa identita súčtu binomických koeficientov len s párnymi alebo len nepárnymi číslami:
Na základe uvažovaných identít a rekurzívneho pravidla na odstránenie indexov spod znamienka počtu kombinácií možno získať množstvo zaujímavých vzťahov. Napríklad, ak vo vzorci súčtu pre horný index nahradíme n všade (n1) a odstránime indexy v každom člene, dostaneme nasledujúci vzťah:
Podobnou technikou vo vzorci pre súčet binomických koeficientov s párnymi a nepárnymi číslami možno dokázať platnosť napríklad nasledujúceho vzťahu:
Ďalšia užitočná identita uľahčuje výpočet súčtu súčinov symetricky umiestnených binomických koeficientov dvoch binomických čísel ľubovoľných stupňov n a k pomocou nasledujúceho Cauchyho vzorca:
Platnosť tohto vzorca vyplýva z nevyhnutnej rovnosti koeficientov pre ľubovoľný stupeň m premennej Z na ľavej a pravej strane nasledujúceho vzťahu identity:
V konkrétnom prípade, keď n=k=m, berúc do úvahy identitu symetrie, získame populárnejší vzorec pre súčet druhých mocnín binomických koeficientov:
Mnoho ďalších užitočných identít pre binomické koeficienty možno nájsť v rozsiahlej literatúre o kombinatorickej analýze. Ich najznámejšia praktická aplikácia však súvisí s Pascalovým trojuholníkom.
PASCALOV TROJUHOLNÍK
Pascalov aritmetický trojuholník tvorí nekonečnú číselnú tabuľku zloženú z binomických koeficientov. Jeho riadky sú usporiadané podľa binomických mocnín zhora nadol. V každom riadku sú binomické koeficienty usporiadané vo vzostupnom poradí podľa horných indexov zodpovedajúcich počtov kombinácií zľava doprava. Pascalov trojuholník sa zvyčajne píše buď v rovnoramennom alebo v obdĺžnikovom tvare.
Vizuálnejší a bežnejší je rovnoramenný formát, kde binomické koeficienty usporiadané do šachovnicového vzoru tvoria nekonečný rovnoramenný trojuholník. Jeho počiatočný fragment pre dvojčleny do 4. stupňa (n=4) je takýto:
Vo všeobecnosti Pascalov rovnoramenný trojuholník poskytuje vhodné geometrické pravidlo na určovanie binomických koeficientov, ktoré je založené na sčítacích identitách a symetrii kombinačných čísel. Najmä podľa identity sčítania je každý binomický koeficient súčtom dvoch koeficientov predchádzajúceho riadka, ktoré sú mu najbližšie. Podľa identity symetrie je Pascalov rovnoramenný trojuholník symetrický vzhľadom na jeho stred. Každý z jeho riadkov je teda číselným palindrómom binomických koeficientov. Tieto algebraické a geometrické vlastnosti uľahčujú rozšírenie Pascalovho rovnoramenného trojuholníka a konzistentné nájdenie hodnôt binomických koeficientov ľubovoľných stupňov.
Na štúdium rôznych vlastností Pascalovho trojuholníka je však vhodnejšie použiť formálne prísnejší obdĺžnikový formát. V tomto formáte je to dané dolno-trojuholníkovou maticou binomických koeficientov, kde tvoria nekonečný pravouhlý trojuholník. Počiatočný fragment správny trojuholník Pascal pre dvojčleny do 9. stupňa (n=9) má nasledujúci tvar:
Geometricky sa takýto obdĺžnikový stôl získa horizontálnou deformáciou rovnoramenný trojuholník Pascal. V dôsledku toho sa číselný rad rovnobežný so stranami Pascalovho rovnoramenného trojuholníka zmení na vertikály a uhlopriečky Pascalovho pravouhlého trojuholníka a horizontály oboch trojuholníkov sa zhodujú. Zároveň ostávajú v platnosti pravidlá sčítania a symetrie binomických koeficientov, hoci Pascalov pravouhlý trojuholník stráca vizuálnu symetriu, ktorá je vlastná jeho rovnoramennému náprotivku. Ako kompenzácia za to je vhodnejšie formálne analyzovať rôzne numerické vlastnosti binomických koeficientov pre horizontály, vertikály a uhlopriečky Pascalovho pravouhlého trojuholníka.
Na začiatku analýzy vrstevníc Pascalovho pravouhlého trojuholníka je ľahké vidieť, že súčet prvkov ľubovoľného riadku s číslom n sa rovná 2 n v súlade so sumačným vzorcom pre dvojčlen podľa horného indexu. Z toho vyplýva, že súčet prvkov nad ktoroukoľvek z horizontál s číslom n sa rovná (2 n 1). Tento výsledok je celkom zrejmý, ak je hodnota súčtu prvkov každej horizontály zapísaná v binárnom číselnom systéme. Napríklad pre n=4 možno takéto sčítanie zapísať takto:
Tu je pár ďalších zaujímavé vlastnosti vrstevnice, ktoré sú tiež spojené s mocninou dvojky. Ukazuje sa, že ak je horizontálne číslo mocninou dvoch (n=2 k), potom všetky jeho vnútorné prvky (okrem extrémnych jednotiek) sú párne čísla. Naopak, všetky čísla vodorovnej čiary budú nepárne, ak jej počet na jednotku menší stupeň dvojky (n=2k1). Platnosť týchto vlastností je možné overiť kontrolou parity vnútorných binomických koeficientov, napríklad v horizontálach n=4 an=3 alebo n=8 a n=7.
Nech je teraz číslo riadku Pascalovho pravouhlého trojuholníka prvočíslo p. Potom sú všetky jeho vnútorné binomické koeficienty deliteľné p. Táto vlastnosť sa dá ľahko skontrolovať na malé hodnoty jednoduchých čísel horizontál. Napríklad všetky vnútorné binomické koeficienty piatej horizontály (5, 10 a 5) sú zjavne deliteľné číslom 5. Aby sme dokázali platnosť tohto výsledku pre ľubovoľné prvočíslo horizontály p, musíme napísať multiplikatívny vzorec jeho binomického bodu. koeficienty takto:
Keďže p je prvočíslo, a teda nie je deliteľné m!, súčin ostatných faktorov čitateľa tohto vzorca musí byť deliteľný m!, aby bola zaručená celočíselná hodnota binomického koeficientu. Z toho vyplýva, že vzťah hranaté zátvorky je prirodzené číslo N a požadovaný výsledok je zrejmý:
Pomocou tohto výsledku sa dá zistiť, že čísla všetkých obrysov Pascalovho trojuholníka, ktorých vnútorné prvky sú deliteľné daným prvočíslom p, sú mocninou p , čiže majú tvar n=p k . Konkrétne, ak p=3, potom prvočíslo p rozdeľuje nielen všetky vnútorné prvky radu 3, ako bolo stanovené vyššie, ale napríklad aj 9. horizontálu (9, 36, 84 a 126). Na druhej strane v Pascalovom trojuholníku nie je možné nájsť horizontálu, ktorej všetky vnútorné prvky sú deliteľné zloženým číslom. V opačnom prípade musí byť počet takejto horizontály súčasne stupňom prvočíselných deliteľov zložené číslo, na ktorú sa delia všetky jej vnútorné prvky, čo je však z pochopiteľných dôvodov nemožné.
Uvažované úvahy nám umožňujú formulovať nasledovné spoločný znak deliteľnosť horizontálnych prvkov Pascalovho trojuholníka. najväčší spoločný deliteľ(GCD) všetky vnútorné prvky ktorákoľvek horizontála Pascalovho trojuholníka s číslom n sa rovná prvočíslo p ak n=pk alebo 1 inak:
GCD(Cmn) = ( ) pre ľubovoľnú 0< m < n .
Na záver analýzy horizontál stojí za úvahu ešte jedna zvláštna vlastnosť, ktorú má rad binomických koeficientov, ktoré ich tvoria. Ak sa binomické koeficienty akejkoľvek horizontály s číslom n vynásobia postupnými mocninami čísla 10 a potom sa všetky tieto produkty spočítajú, získa sa 11 n. Formálnym zdôvodnením tohto výsledku je nahradenie hodnôt X=10 a Y=1 (alebo Z=1) do Newtonovho binomického vzorca. Nasledujúci číselný príklad ilustruje implementáciu tejto vlastnosti pre n=5:
Analýzu vlastností vertikál Pascalovho pravouhlého trojuholníka možno začať štúdiom individuálnych charakteristík ich základné prvky. Formálne je každá vertikála m tvorená nasledujúcou nekonečnou postupnosťou binomických koeficientov s konštantným horným indexom (m) a prírastkom dolného indexu:
Je zrejmé, že keď m=0, získa sa postupnosť jednotiek a keď m=1, vytvorí sa séria prirodzených čísel. Pre m=2 je vertikála tvorená trojuholníkovými číslami. Každé trojuholníkové číslo môže byť znázornené v rovine ako rovnostranný trojuholník, ktorý je vyplnený ľubovoľnými objektmi (jadrami) usporiadanými do šachovnicového vzoru. V tomto prípade hodnota každého trojuholníkového čísla T k určuje počet reprezentujúcich jadier a index ukazuje, koľko radov jadier je potrebných na jeho znázornenie. Napríklad 4 počiatočné trojuholníkové čísla predstavujú nasledujúce konfigurácie zo zodpovedajúceho počtu znakov jadra „@“:
Treba poznamenať, že podobným spôsobom je možné zaviesť do úvahy štvorcové čísla Sk, ktoré sa získajú umocnením prirodzených čísel a vo všeobecnosti mnohouholníkové obrazné čísla tvorené pravidelným plnením. pravidelné polygóny. Najmä 4 počiatočné štvorcové čísla možno znázorniť nasledovne:
Keď sa vrátime k analýze vertikál Pascalovho trojuholníka, môžeme si všimnúť, že nasledujúca vertikála v m=3 je vyplnená tetraedrickými (pyramídovými) číslami. Každé takéto číslo Pk udáva počet jadier, ktoré môžu byť usporiadané do tvaru štvorstenu, a index určuje, koľko horizontálnych trojuholníkových vrstiev z radov jadier je potrebných na jeho zobrazenie v trojrozmerný priestor. V tomto prípade by všetky horizontálne vrstvy mali byť reprezentované ako po sebe idúce trojuholníkové čísla. Prvky ďalších vertikál Pascalovho trojuholníka pre m>3 tvoria rady hypertetrahedálnych čísel, ktoré nemajú jasnú geometrickú interpretáciu v rovine alebo v trojrozmernom priestore, ale formálne zodpovedajú viacrozmerným analógom trojuholníkových a štvorstenných čísel.
Vertikálne číselné rady Pascalovho trojuholníka síce majú uvažované jednotlivé kučeravé znaky, ale pre nich je možné vypočítať čiastočné súčty hodnôt počiatočných prvkov rovnakým spôsobom pomocou vzorca na sčítanie čísel kombinácií podľa dolného indexu. . V Pascalovom trojuholníku má tento vzorec nasledujúcu geometrickú interpretáciu. Súčet hodnôt n horných binomických koeficientov ktorejkoľvek vertikály sa rovná hodnote prvku ďalšej vertikály, ktorá sa nachádza o jeden riadok nižšie. Tento výsledok je tiež v súlade s geometrickou štruktúrou trojuholníkových, štvorstenných a hypertetrahedálnych čísel, pretože reprezentácia každého takéhoto čísla pozostáva z vrstiev jadra, ktoré zobrazujú čísla nižšieho rádu. najmä n-tý trojuholníkovýčíslo Tn možno získať sčítaním všetkých prirodzených čísel reprezentujúcich jeho lineárne vrstvy:
Podobne je ľahké nájsť štvorstenné číslo Pn výpočtom nasledujúceho súčtu prvých n trojuholníkových čísel, ktoré tvoria jeho horizontálne jadrové vrstvy:
Okrem horizontál a vertikál v Pascalovom pravouhlom trojuholníku možno sledovať diagonálne rady prvkov, ktorých štúdium vlastností je tiež mimoriadne zaujímavé. V tomto prípade sa zvyčajne rozlišujú klesajúce a stúpajúce uhlopriečky. Zostupné uhlopriečky sú rovnobežné s preponou Pascalovho pravouhlého trojuholníka. Sú tvorené sériou binomických koeficientov s prírastkom oboch indexov. Vzhľadom na identitu symetrie sa klesajúce uhlopriečky zhodujú v hodnotách svojich prvkov so zodpovedajúcimi vertikálnymi radmi Pascalovho trojuholníka, a preto opakujú všetky svoje vlastnosti uvedené vyššie. Uvedenú korešpondenciu možno vysledovať zhodou hodnôt prvkov klesajúcej uhlopriečky a vertikály s ľubovoľným číslom n, ak sa neberú do úvahy vertikálne nuly:
Vzostupné diagonály tvoria číselné rady geometricky kolmé na preponu Pascalovho pravouhlého trojuholníka. Sú vyplnené binomickými koeficientmi s prírastkom dolného indexu a prírastkom horného indexu. Najmä 7 horných vzostupných uhlopriečok tvorí nasledujúcu číselnú postupnosť s výnimkou koncových núl:
Vo všeobecnom prípade sú nasledujúce binomické koeficienty na vzostupnej diagonále s číslom n, pričom súčet indexov každého z nich sa rovná (n1):
Na základe sčítacej identity pre kombinačné čísla sa každý diagonálny prvok rovná súčtu dvoch prvkov zodpovedajúcich indexom z dvoch predchádzajúcich vzostupných diagonál. To umožňuje zostaviť každú nasledujúcu vzostupnú uhlopriečku párovým sčítaním susedných horizontálnych prvkov z dvoch predchádzajúcich uhlopriečok, čím sa Pascalov trojuholník nekonečne rozširuje pozdĺž uhlopriečky. Nasledujúci fragment Pascalovho trojuholníka ilustruje konštrukciu vzostupnej uhlopriečky s číslom 8 pozdĺž uhlopriečok s číslami 6 a 7:
Pri tomto spôsobe konštrukcie sa súčet prvkov ktorejkoľvek vzostupnej uhlopriečky, počnúc od 3., bude rovnať súčtu prvkov dvoch predchádzajúcich vzostupných uhlopriečok a prvé 2 uhlopriečky pozostávajú iba z jedného prvku, hodnoty z toho je 1. Výsledky zodpovedajúcich výpočtov tvoria nasledujúci číselný rad, podľa ktorého je možné overiť platnosť uvažovanej vlastnosti vzostupných uhlopriečok Pascalovho pravouhlého trojuholníka:
Pri analýze týchto čísel môžete vidieť, že podľa podobného zákona vzniká známa postupnosť Fibonacciho čísel, kde každé nasledujúce číslo sa rovná súčtu dvoch predchádzajúcich a prvé dve čísla sa rovnajú 1. :
Z toho možno vyvodiť nasledujúci dôležitý záver: diagonálne súčty prvkov Pascalovho trojuholníka tvoria Fibonacciho postupnosť. Táto vlastnosť vám umožňuje nastaviť ďalšie zaujímavá vlastnosť Pascalov trojuholník. Rozšírením Fibonacciho vzorca rekurzívne je ľahké dokázať, že súčet prvých n Fibonacciho čísel sa rovná (F n+2 1).
Preto sa aj súčet binomických koeficientov, ktoré vypĺňajú horných n uhlopriečok, rovná (F n+2 1). Z toho vyplýva, že súčet prvých n uhlopriečok Pascalovho trojuholníka je o 1 menší ako súčet binomických koeficientov, ktoré stoja na jeho uhlopriečke s číslom (n + 2).
Na záver treba poznamenať, že uvažované vlastnosti horizontál, vertikál a uhlopriečok Pascalovho trojuholníka ani zďaleka nevyčerpávajú obrovskú paletu možností, ktoré spájajú rôzne matematické aspekty, ktoré na prvý pohľad nemajú nič spoločné. Takéto nezvyčajné vlastnosti umožňujú považovať Pascalov trojuholník za jeden z najpokročilejších číselných systémov, ktorého všetky možnosti nemožno vymenovať a je ťažké ho preceňovať.
Algoritmus na výpočet počtu kombinácií pomocou Pascalovho trojuholníka je uvedený nižšie:
Súkromná funkcia SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Ďalší Pre i = 2 To n Pre j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Ďalší Ďalší SochTT = TT (n, k) Koncová funkcia
Ak potrebujete vypočítať počet kombinácií mnohokrát, môže byť pohodlnejšie zostaviť Pascalov trojuholník raz a potom získať údaje z poľa.
Dim TT () Ako Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j As Integer ReDim Zachovať TT (koniec, koniec) Pre i = začiatok Do konca TT (0, i) = 1 TT (i, i) = 1 Ďalší Ak koniec< 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
Najprv musíte zavolať procedúru CreateTT. Potom môžete získať počet kombinácií pomocou funkcie SochTT. Keď už trojuholník nepotrebujete, zavolajte na TerminateTT. Vo vyššie uvedenom kóde pri volaní funkcie SochTT, ak trojuholník ešte nebol dokončený požadovaná úroveň, potom sa dokončí pomocou postupu BuildTT. Funkcia potom získa požadovaný prvok poľa TT a vráti ho.
Dim X () As Integer Dim Counter () As Integer Dim K As Integer Dim N As 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 Next 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 Then ReDim Out (K) X1 = X For i = 1 To K - 1 n1 = 0 Pre j = 1 až N Ak X1(j)<>0 Potom n1 = n1 + 1 Ak n1 = Counter(i) Then Out(i) = X1(j) X1(j) = 0 Exit For End If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Nasledujúci txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
Vyčíslenie kombinácií prirodzených čísel
Na vyriešenie mnohých praktických problémov je potrebné vymenovať všetky kombinácie pevnej mohutnosti, ktoré možno získať z prvkov danej konečnej množiny, a nielen určiť ich počet. Vzhľadom na vždy existujúcu možnosť celočíselného číslovania prvkov akejkoľvek konečnej množiny je vo väčšine prípadov prípustné obmedziť sa na použitie algoritmov na počítanie kombinácií prirodzených čísel. Najprirodzenejším a najjednoduchším z nich je algoritmus na vypisovanie kombinácií prirodzených čísel lexigrafický poriadok.
Pre formálny popis tohto algoritmu je vhodné predpokladať, že hlavná množina, ktorej všetky kombinácie m prvkov musia byť uvedené, tvoria po sebe idúce prirodzené čísla od 1 do n. Potom ľubovoľná kombinácia m V dôsledku usporiadania sa hodnota v každej polohe takéhoto vektora kombinácií prirodzene ukazuje ako obmedzená hodnota zhora a zdola takto: Lexigrafický algoritmus sekvenčne generuje také vektory kombinácií, počnúc od lexigraficky najmenšieho vektora, kde všetky pozície obsahujú nasledujúce minimálne možné hodnoty prvkov rovné ich indexom: Každý ďalší kombinovaný vektor sa vytvorí z aktuálneho vektora po zobrazení jeho prvkov zľava doprava, aby sa našiel prvok úplne vpravo, ktorý ešte nedosiahol svoju limitnú hodnotu: Hodnota takéhoto prvku by sa mala zvýšiť o 1. Každému prvku napravo od neho by mala byť priradená najmenšia možná hodnota, ktorá je o 1 väčšia ako sused naľavo. Po týchto zmenách bude mať nasledujúci vektor kombinácií nasledujúce elementárne zloženie: Nasledujúci kombinovaný vektor bude teda lexigraficky väčší ako predchádzajúci, pretože hodnoty ich počiatočných prvkov (j1) majú rovnakú hodnotu a hodnota prvku na pozícii j je o 1 väčšia ako hodnota predchádzajúceho prvku. . Zadaný vzťah rastúceho lexigrafického poriadku je zaručene splnený pri všetkých iteráciách algoritmu. V dôsledku toho sa vytvára rastúca lexigrafická postupnosť, ktorú dopĺňa lexigraficky najväčší kombinačný vektor, kde prvky na všetkých pozíciách majú nasledujúce maximálne hodnoty: Uvažovaný lexigrafický algoritmus ilustruje nasledujúci príklad, kde je potrebné uviesť vo vzostupnom lexigrafickom poradí všetkých 15 kombinácií n=6 prvých prirodzených čísel s m=4 číslami, teda všetkých možných 4-prvkových podmnožín hlavnej generujúcej množiny ( 1, 2, 3, 4, 5, 6) zo 6 prvkov. Výsledky výpočtu sú uvedené v nasledujúcej tabuľke: V tomto príklade sú najväčšie prípustné hodnoty čísel na pozíciách kombinovaných vektorov 3, 4, 5 a 6. Pre uľahčenie interpretácie výsledkov v každom kombinačnom vektore je prvok úplne vpravo, ktorý nemá ešte dosiahol svoju maximálnu hodnotu, je podčiarknuté. Číselné indexy kombinačných vektorov určujú ich počty v lexigrafickom poradí. Vo všeobecnosti možno lexigrafické číslo N akejkoľvek kombinácie n prvkov podľa m vypočítať pomocou nasledujúceho vzorca, kde sa z kozmetických dôvodov na označenie počtu kombinácií používa Appellova symbolika: Najmä nasledujúce výpočty používajúce tento vzorec pre kombinačné číslo (1, 3, 4, 6) n=6 prvkov podľa m=4 v lexigrafickom poradí poskytnú výsledok N=8, ktorý zodpovedá príkladu diskutovanému vyššie: Vo všeobecnom prípade pomocou identity pre súčet čísel kombinácií pre oba indexy možno ukázať, že číslo lexigraficky najmenšej kombinácie (1, ... i, ... m) pri jej výpočte pomocou tohto vzorec bude vždy rovný 1: Je tiež zrejmé, že počet lexigraficky najväčšej kombinácie (m, ... nm+i, ... n) pri jej výpočte podľa tohto vzorca sa bude rovnať počtu kombinácií n prvkov na m: Vzorec na výpočet lexigrafických čísel kombinácií možno použiť na riešenie inverznej úlohy, kde je potrebné určiť vektor kombinácie podľa jeho čísla v lexigrafickom poradí. Na vyriešenie takéhoto inverzného problému musí byť napísaný ako rovnica, kde sú všetky neznáme hodnoty prvkov vektora požadovanej kombinácie (C 1 , ... C i , ... C m) sústredené v počet kombinácií jeho pravej strany a známy rozdiel L počtu kombinácií sa zapíše na ľavú stranu n prvkov m a číslom želanej kombinácie N: Riešenie tejto rovnice poskytuje nasledujúci „chamtivý“ algoritmus, pri ktorého iteráciách sa postupne vyberajú hodnoty prvkov vektora požadovanej kombinácie. Pri počiatočnej iterácii sa vyberie minimálna možná (v rámci svojich obmedzení) hodnota C 1, v ktorej prvý člen na pravej strane bude mať maximálnu hodnotu nepresahujúcu L: Teraz by sa mala ľavá strana L znížiť o prvý počet kombinácií na pravej strane so zvolenou hodnotou C 1 a hodnota C 2 by sa mala určiť rovnakým spôsobom v druhej iterácii: Podobne by sa mali vykonať všetky nasledujúce iterácie, aby sa vybrali hodnoty všetkých ostatných prvkov C i požadovanej kombinácie až po posledný prvok C m: Zo zrejmých dôvodov možno hodnotu posledného prvku C m určiť na základe rovnosti jeho počtu kombinácií so zostatkovou hodnotou ľavej strany L: Treba poznamenať, že hodnotu posledného prvku kombinácie C m možno nájsť ešte jednoduchšie, bez vymenovania jeho možných hodnôt: Implementáciu iterácií uvažovaného algoritmu ilustruje nasledujúci príklad, kde je potrebné určiť kombinácie s číslom N=8 v lexigrafickom poradí, ak n=6 a m=4: Algoritmickú schopnosť určiť kombináciu podľa daného čísla v lexigrafickom poradí možno využiť v rôznych smeroch. Najmä pri uvádzaní kombinácií v lexigrafickom poradí je potrebné poskytnúť návrat k akejkoľvek kombinácii, ktorá bola získaná skôr, stačí poznať iba jej číslo. Okrem toho je možné generovať kombinácie v akomkoľvek poradí, ktoré reguluje ľubovoľne danú postupnosť ich lexigrafických čísel. Teraz uvádzame algoritmus na generovanie kombinácií v lexikografickom poradí: 2 pre i:= 1 až k do A[i] := i; 5 begin write(A, …, A[k]); 6 ak A[k] = n, potom p:= p 1 inak p:= k; 8 pre i:= k až po p do A[i] := A[p] + i p + 1 KOMBINÁCIE S OPAKOVANÍM PRVKOV Na rozdiel od klasickej kombinácie, kde sú všetky prvky odlišné, kombinácia s opakovaniami tvorí neusporiadaný výber prvkov z konečnej množiny, kde sa ľubovoľný prvok môže vyskytovať neobmedzene často a nemusí byť nutne prítomný v jedinej kópii. Počet opakovaní prvkov je zároveň zvyčajne obmedzený len dĺžkou kombinácie a kombinácie, ktoré sa líšia aspoň jedným prvkom, sa považujú za odlišné. Napríklad výberom 4 voliteľne odlišných čísel z množiny 1, 2 a 3 môžete vytvoriť nasledujúcich 15 kombinácií s opakovaním: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Vo všeobecnom prípade môžu byť kombinácie s opakovaniami tvorené výberom n prvkov ľubovoľného typu. Vždy ich však možno spájať s po sebe nasledujúcimi prirodzenými číslami od 1 do n. Potom je možné ľubovoľnú kombináciu m voliteľne rôznych čísel v tomto rozsahu zapísať vo vektorovej forme a usporiadať ich v neklesajúcom poradí zľava doprava: Prirodzene, pri tejto forme písania môžu byť akékoľvek susedné prvky rovnaké kvôli možnosti neobmedzeného opakovania. Avšak každý kombinačný vektor s opakovaniami n prvkov podľa m môže byť spojený s kombinovaným vektorom (n + m − 1) prvkov podľa m, ktorý je skonštruovaný takto: Je zrejmé, že pre akékoľvek hodnoty prvkov vektora f sú prvky vektora C zaručene odlišné a prísne usporiadané vo vzostupnom poradí ich hodnôt v rozsahu od 1 do (n+m1) : Prítomnosť korešpondencie jedna ku jednej medzi prvkami kombinačných vektorov f a C nám umožňuje navrhnúť nasledujúcu jednoduchú metódu na systematické počítanie kombinácií s opakovaniami n prvkov na m. Je len potrebné uviesť napríklad v lexigrafickom poradí všetky C kombinácie prvkov (n + m1) podľa m, pričom prvky každého z nich sa postupne prevedú na zodpovedajúce prvky kombinácií s opakovaniami f podľa nasledujúceho vzorca: Výsledkom je vytvorenie sekvencie kombinačných vektorov s opakovaniami prvkov, ktoré sú usporiadané v poradí vygenerovanom sčítaním zodpovedajúcich kombinácií bez opakovaní prvkov. Najmä na získanie vyššie uvedenej postupnosti kombinácií 3 číslic 1, 2 a 3 s opakovaniami 4 číslic je potrebné uviesť v lexigrafickom poradí všetky kombinácie bez opakovania 6 číslic 1,2,3,4, 5 a 6 na 4 číslice, pričom ich prevediete určeným spôsobom. Nasledujúci príklad ukazuje takúto transformáciu kombinácie (1,3,4,6) s lexigrafickým číslom 8: Uvažovaná zhoda jedna ku jednej medzi kombináciami s opakovaniami a bez opakovaní prvkov znamená, že ich súbory sú ekvivalentné. Preto sa vo všeobecnom prípade počet kombinácií s opakovaniami n prvkov na m rovná počtu kombinácií bez opakovaní z (n + m1) prvkov na m. Použitím rovnakej symboliky na označenie počtu kombinácií s opakovaniami f a bez opakovaní C možno túto rovnosť zapísať takto: Je ľahké skontrolovať, že pre vyššie uvedený príklad, kde n=3 a m=4, bude počet kombinácií s opakovaním 15, čo sa zhoduje s výsledkom ich priameho vyčíslenia: Treba poznamenať, že na rozdiel od klasickej verzie, hodnoty kombinačných parametrov s opakovaniami n a m spolu priamo nesúvisia, preto f(n,m)>0 pre akúkoľvek kombináciu ich kladných hodnôt. Zodpovedajúce okrajové podmienky sú určené z rovnosti medzi hodnotami (n+m1) a (n1) alebo (n+m1) a m: Malo by byť tiež celkom zrejmé, že ak sa m rovná 1, potom nie je možné žiadne opakovanie prvkov, a preto pre akúkoľvek kladnú hodnotu n>0 bude platiť nasledujúca rovnosť: Navyše na počty kombinácií s opakovaniami pre ľubovoľné kladné hodnoty n a m platí nasledujúce opakovanie, ktoré je podobné sčítacej identite pre kombinačné čísla bez opakovania prvkov: V skutočnosti sa zmení na špecifikovanú identitu sčítania s formálnym nahradením zodpovedajúcich počtov kombinácií bez opakovaní v ľavej a pravej časti: Uvažovaný rekurentný vzťah je možné využiť na efektívne určenie počtu kombinácií s opakovaniami, kedy je dôležité eliminovať prácne operácie výpočtu faktoriálnych súčinov a nahradiť ich jednoduchšími operáciami sčítania. Zároveň na výpočet hodnoty f(n,m) stačí použiť tento rekurentný vzťah, kým nedostanete súčet členov tvaru f(1,m) a f(i,1), kde i nadobúda hodnoty v rozsahu od n do 1. Podľa definície sa tieto pojmy rovnajú 1 a i. Nasledujúci príklad ilustruje použitie tejto transformačnej techniky pre prípad n=3 a m=4: Vyčíslenie binárnych kombinácií Pri implementácii kombinácií v hardvéri alebo pri programovaní v jazyku symbolických inštrukcií je dôležité vedieť spracovať kombinačné záznamy v binárnom formáte. V tomto prípade by akákoľvek kombinácia n prvkov podľa m mala byť špecifikovaná vo forme n-bitového binárneho čísla (B n ,…B j ,…B 1), kde m jednotlivých číslic označuje prvky kombinácie a zostávajúce (nm) číslice majú nulové hodnoty. Je zrejmé, že pri tejto forme zápisu sa musia rôzne kombinácie líšiť v usporiadaní jednotiek a existuje len C (n, m) spôsobov, ako usporiadať m jednotiek alebo (nm) núl v n-bitovej binárnej množine. Napríklad nasledujúca tabuľka uvádza všetkých 6 takýchto binárnych kombinácií, ktoré poskytujú 4-bitové binárne čísla pre všetky kombinácie 4 prvkov ľubovoľnej množiny (E 1 , E 2 , E 3 , E 4 ) po 2: Vo všeobecnom prípade je úloha enumerácie takýchto binárnych kombinácií redukovaná na systematické enumerovanie všetkých n-bitových binárnych množín s rôznym usporiadaním m jednoduchých a (nm) nulových bitov. V najjednoduchšej forme je takýto zoznam implementovaný rôzne metódy transpozície susedných číslic s posunom (algoritmy transpositive-shift). Ide o iteračné algoritmy a ich názvy odrážajú povahu operácií vykonávaných v každom kroku. Iteračné procedúry Algoritmy transpozitívneho posunu tvoria sekvencie binárnych kombinácií, ktoré začínajú binárnou množinou, kde sú všetky jednotky sústredené na nižších čísliciach (vpravo) a končia, keď sú všetky na vyšších číslicách (vľavo): Tieto sekvencie sa zhodujú v počiatočných a konečných kombináciách a líšia sa v poradí vymenovania medziľahlých binárnych množín. Vo všetkých prípadoch sa však každá ďalšia binárna kombinácia vytvorí podľa predchádzajúcej v dôsledku vykonania zodpovedajúcich operácií transpozície a posunu. Zároveň sa rôzne algoritmy transpozitívneho posunu líšia v spôsobe výberu dvojice číslic na transpozíciu a skupiny číslic na posun. Táto špecifickosť je zvažovaná nižšie pre transpozičné algoritmy s ľavým a pravým posunom. V transpozičnom algoritme s posunom doľava v každom kroku sa ďalšia binárna kombinácia získa z aktuálnej tak, že sa najľavejší pár bitov 01 nahradí 10 (transpozícia) a posunie sa skupina bitov vedúcich jednotiek, ak existuje, blízko k pár 10 získaný po transpozícii (posune). Ak súčasne v aktuálnej binárnej kombinácii nie sú jedničky na najvyšších čísliciach, posun sa nevykoná, aj keď sa vedúca jednotka získa po transpozícii pomocou tento krok. Posun sa nevykoná ani vtedy, keď v bitoch vyššieho rádu pred párom 10s získaným po transpozícii nie sú žiadne nuly. Uvažované akcie ilustruje nasledujúci príklad vykonania dvoch po sebe nasledujúcich iterácií tento algoritmus, kde v jednej iterácii (15) sa vykoná iba transpozícia (T") a v druhej iterácii (16) sa transpozícia doplní o posun (T"+S"): V algoritme transpozície posunu doprava sa v každom kroku vykonávajú koncepčne podobné akcie. Iba transpozícia zaistí, že číslice 01 úplne vpravo sú nahradené 10 (namiesto tých úplne vľavo) a potom sa všetky jednotky napravo od nej posunú na nižšie číslice. Rovnako ako predtým sa posun vykonáva iba vtedy, ak existujú jednotky, ktoré sa dajú posunúť doprava. Uvažované akcie ilustruje nasledujúci príklad vykonania dvoch po sebe nasledujúcich iterácií tohto algoritmu, kde v jednej iterácii (3) sa vykoná iba transpozícia (T) a v druhej iterácii (4) sa transpozícia doplní o posun (T"+S"): Treba poznamenať, že iterácie oboch algoritmov možno zapísať v aditívnej forme, ak sa binárne kombinácie interpretujú ako celé čísla v číselnom systéme so základom 2. Najmä pre algoritmus transpozície s posunom doprava každá ďalšia binárna kombinácia (B" n ,…B" j, …B" 1) možno vždy získať z aktuálnej kombinácie (B n,…Bj,…B 1) vykonaním operácií sčítania celých čísel pomocou nasledujúceho aditívneho vzorca: V tomto aditívnom vzorci exponenty dvoch f a t označujú počet núl aktuálnej binárnej kombinácie a počet jednotiek v rade naľavo od nich. Napríklad pre 4. binárnu kombináciu (001110) n = 6 bitov je f = 1 a t = 3. Preto výpočet ďalšej binárnej kombinácie pomocou aditívneho vzorca v iterácii 5 poskytne nasledujúci výsledok, ktorý je ekvivalentný vykonaniu operácií transpozície a posunu: Pre komparatívna analýza z uvažovaných transpozičných algoritmov s ľavým a pravým posunom je vhodné porovnať sekvencie binárnych kombinácií, ktoré generujú pri svojich iteráciách. Nasledujúca tabuľka ukazuje dve takéto sekvencie binárnych kombinácií 4 prvkov po 2, ktoré sa získajú ľavým (TSL) a pravým (TSR) algoritmom posunu, v tomto poradí: Porovnaním týchto 2 sekvencií môžete vidieť, že sú spätne zrkadlové. To znamená, že akékoľvek dve binárne kombinácie, ktoré sa v nich nachádzajú v rovnakej vzdialenosti od vzájomne opačných koncov ich sekvencií, sú vzájomným zrkadlovým obrazom, to znamená, že sa zhodujú pri zmene na spätné indexovanie bitov v ktorejkoľvek z nich. Napríklad druhý binárny obrazec od začiatku sekvencie TSL (0101) je zrkadlovým obrazom binárneho obrazca (1010), ktorý je druhý od konca sekvencie TSR. Vo všeobecnom prípade je každá binárna kombinácia s číslom i jednej postupnosti zrkadlovým obrazom binárnej kombinácie s číslom (ni + 1) inej postupnosti. Takýto pomer týchto sekvencií je dôsledkom symetrickej povahy operácií transpozície a posunu v dvoch uvažovaných algoritmoch na vyčíslenie binárnych kombinácií. Treba si uvedomiť, že binárny formát je možné použiť aj na zápis kombinácií s opakovaním prvkov. Aby ste to dosiahli, musíte vytvoriť vzájomnú korešpondenciu medzi kombináciami s opakovaniami a binárnymi kombináciami, ktoré sú zostavené nasledovne. Nech existuje ľubovoľná kombinácia s opakovaniami, ktorá sa získa výberom m voliteľne rôznych prvkov z n prvkov generujúcej množiny. Ak chcete vytvoriť požadovanú korešpondenciu, musíte najskôr pripojiť ku kombinácii všetky prvky generujúcej množiny (mačka) a potom zoradiť výsledné zreťazenie (zoradiť) tak, aby boli všetky identické prvky blízko. Výsledkom je postupnosť (n+m) prvkov, kde n skupín identických prvkov. Medzi prvkami budú len (n+m1) medzery, medzi ktorými bude (n1) medzier medzi skupinami identických prvkov a m medzier medzi prvkami v rámci skupín. Kvôli prehľadnosti môžete v určených intervaloch umiestniť znaky "|" a zodpovedajúcim spôsobom. Ak teraz namapujeme 1 na medzery medzi skupinami (|) a 0 na všetky ostatné medzery (), dostaneme binárnu kombináciu. Tvorí ho binárna množina (n+m1) číslic, kde (n1) sú jednotky a m nula číslic, ktorých umiestnenie jednoznačne zodpovedá pôvodnej kombinácii s opakovaniami prvkov n až m. Uvažovaná transformačná technika je ilustrovaná nasledujúcim príkladom konštrukcie binárnej kombinácie (1001101) kombináciou s opakovaniami (BBD), ktorej prvky sú vybrané z generujúcej množiny prvých piatich latinských písmen: Vo všeobecnosti počet takýchto binárnych množín určuje počet spôsobov usporiadania (n1) jednotiek (alebo m núl) v (n+m1) binárnych čísliciach. Táto hodnota sa zjavne rovná počtu kombinácií od (n+m1) po (n1) alebo nad m, teda C(n+m1,n1) alebo C(n+m1,m), čo sa rovná počet kombinácií s opakovaniami f( n,m) n prvkov podľa m. Ak teda existuje zhoda jedna ku jednej medzi kombináciami s opakovaniami a binárnymi kombináciami, je legitímne zredukovať počet kombinácií s opakovaniami na výpočet binárnych kombinácií, napríklad pomocou transpozičných algoritmov s posunom doľava alebo doprava. Potom už stačí len obnoviť požadované kombinácie opakovaním zo získaných binárnych kombinácií. Vždy sa to dá dosiahnuť použitím nasledujúcej obnovovacej techniky. Hlavná množina, z ktorej prvkov sa tvoria kombinácie s opakovaniami m prípadne rôznych prvkov, nech je usporiadaná ľubovoľne tak, aby každý jej prvok mal určité poradové číslo od 1 do n. Nech je implementované aj počítanie binárnych kombinácií (n+m1) binárnych číslic, kde (n1) sú jednoduché a m nula číslic. Každá výsledná binárna kombinácia môže byť vľavo doplnená fiktívnou jednotkovou číslicou a všetky jednotkové číslice môžu byť očíslované zľava doprava celými číslami od 1 do n. Potom sa počet núl stojacich v rade za každou i-tou jednotkou binárnej kombinácie bude rovnať počtu výskytov i-tého prvku hlavnej množiny v zodpovedajúcej kombinácii s opakovaniami. Uvažovanú techniku ilustruje nasledujúci príklad, kde binárna kombinácia (1001101) obnovuje kombináciu s opakovaniami BBD, ktorých prvky sú vybrané z generujúcej množiny prvých piatich latinských písmen napísaných v abecedné poradie a podčiarknutie označuje prvky, ktoré v tejto kombinácii chýbajú: Vykonávanie podobných akcií v podmienkach tento príklad, môžete uviesť všetkých 35 binárnych kombinácií, ktoré tvoria 7-miestne binárne množiny, kde sú 4 jednotky a 3 nuly, a obnoviť zodpovedajúce kombinácie s opakovaním 5 prvkov po 3. Na uľahčenie orientácie v materiáli pridám obsah tejto témy: V tejto téme zvážime základné pojmy kombinatoriky: permutácie, kombinácie a umiestnenia. Poďme zistiť ich podstatu a vzorce, podľa ktorých môžete nájsť ich počet. Na začiatok potrebujeme nejaké základné informácie. Začnime s takým základným matematickým pojmom, akým je množina. Pojem množina bol podrobne popísaný v téme "Pojem množiny. Metódy špecifikácie množín" . vysoko krátky príbeh o súpravách: ukázať skryť Stručne povedané, súbor je zbierka predmetov. Sady sú napísané v zložených zátvorkách. Na poradí, v akom sú prvky napísané, nezáleží; opakovanie prvkov nie je povolené. Napríklad množina číslic čísla 11115555999 bude: $\(1,5,9 \)$. Súbor spoluhláskových písmen v slove "tigrie mláďa" je nasledovný: $\(t, r, r, n, k\)$. Zápis $5\in A$ znamená, že prvok 5 patrí do množiny $A=\(1,5,9 \)$. Počet prvkov v konečnej množine sa nazýva moc tejto množiny a sú označené $|A|$. Napríklad pre množinu $A=\(1,5,9 \)$ obsahujúcu 3 prvky máme: $|A|=3$. Uvažujme nejakú neprázdnu konečnú množinu $U$, ktorej mohutnosť sa rovná $n$, $|U|=n$ (to znamená, že množina $U$ má $n$ prvkov). Predstavme si taký koncept ako vzorka(niektorí autori to nazývajú tuple). Vzorkou veľkosti $k$ z $n$ prvkov (skrátene $(n,k)$-selection) rozumieme množinu prvkov $(a_1, a_2,\ldots, a_k)$, kde $a_i\in U $. O výbere sa hovorí, že je usporiadaný, ak je v ňom uvedené poradie prvkov. Dve usporiadané vzorky, ktoré sa líšia iba poradím prvkov, sú odlišné. Ak poradie prvkov vzorky nie je významné, potom sa vzorka nazýva neusporiadaná. Všimnite si, že definícia výberu nehovorí nič o opakovaniach položiek. Na rozdiel od prvkov množiny sa prvky výberu môžu opakovať. Uvažujme napríklad množinu $U=\(a,b,c,d,e\)$. Množina $U$ obsahuje 5 prvkov, t.j. $|U|=5 $. Vzorka bez opakovaní môže byť: $(a,b,c)$. Táto vzorka obsahuje 3 prvky, t.j. veľkosť tejto vzorky je 3. Inými slovami, toto je $(5,3)$-vzorka. Vzorka s opakovaniami môže byť: $(a,a,a,a,a,c,c,d)$. Obsahuje 8 prvkov, t.j. jeho objem je 8. Inými slovami, toto je $(5,8)$-vzorka. Zvážte dve ďalšie $(5,3)$-vzorky: $(a,b,b)$ a $(b,a,b)$. Ak predpokladáme, že naše vzorky sú neusporiadané, tak vzorka $(a,b,b)$ sa rovná vzorke $(b,a,b)$, t.j. $(a,b,b)=(b,a,b)$. Ak predpokladáme, že naše vzorky sú objednané, potom $(a,b,b)\neq(b,a,b)$. Pozrime sa na iný príklad, trochu menej abstraktný :) Predpokladajme, že v košíku je šesť cukríkov a všetky sú iné. Ak je prvému cukríku priradené číslo 1, druhému cukríku číslo 2 atď., potom je možné k cukríkom v košíku priradiť nasledujúcu sadu: $U=\(1,2,3,4,5 ,6\)$. Predstavte si, že náhodne vložíme ruku do košíka, aby sme vytiahli tri sladkosti. Vytiahnuté sladkosti - toto je ukážka. Keďže zo 6 vyťahujeme 3 cukríky, dostaneme (6,3)-vzorku. Poradie vloženia cukríkov do dlane je úplne irelevantné, preto je táto vzorka neusporiadaná. No a keďže všetky cukríky sú iné, ukážka je bez opakovania. Takže v tejto situácii hovoríme o neusporiadanom (6,3)-výbere bez opakovaní. Teraz poďme z druhej strany. Predstavme si, že sme v továrni na cukrovinky a táto továreň vyrába štyri druhy cukroviniek. Množina $U$ je v tejto situácii nasledovná: $U=\(1,2,3,4 \)$ (každá číslica je zodpovedná za svoj vlastný druh sladkosti). Teraz si predstavte, že všetky sladkosti sú nasypané do jedného žľabu, v blízkosti ktorého stojíme. A nahradením dlaní vyberieme z tohto prúdu 20 sladkostí. Cukríky v hrsti - toto je ukážka. Hrá rolu poradie cukríkov v hrsti? Prirodzene nie, takže vzorka nie je usporiadaná. Existujú iba 4 druhy sladkostí a vyberáme dvadsať kusov zo všeobecného toku - opakovania odrôd sú nevyhnutné. Zároveň sa vzorky môžu veľmi líšiť: dokonca môžeme mať všetky cukríky rovnakej odrody. Následne v tejto situácii máme do činenia s neusporiadaným (4.20)-výberom s opakovaniami. Pozrime sa na niekoľko ďalších príkladov. Na kocky nech je napísaných 7 rôznych písmen: k, o, n, f, e, t, a. Tieto písmená tvoria množinu $U=\(k,o,n,f,e,t,a\)$. Predpokladajme, že z týchto kociek chceme vytvoriť „slová“ z 5 písmen. Písmená týchto slov (napríklad „confé“, „tenko“ atď.) tvoria (7,5)-výbery: $(k,o,n,f,e)$, $(t,e,n ,k ,o)$ atď. Je zrejmé, že poradie písmen v takejto vzorke je dôležité. Napríklad slová „nokft“ a „kfton“ sú odlišné (hoci pozostávajú z rovnakých písmen), pretože nemajú rovnaké poradie písmen. V takýchto „slovách“ sa písmená neopakujú, pretože kociek je iba sedem. Takže množina písmen každého slova je usporiadaná (7,5) vzorka bez opakovaní. Ďalší príklad: zo štyroch číslic 1, 5, 7, 8 vytvoríme všetky druhy osemciferných čísel. Napríklad 11111111, 15518877, 88881111 atď. Množina $U$ je nasledovná: $U=\(1,5,7,8\)$. Číslice každého zostaveného čísla tvoria (4,8)-vzorku. Dôležité je poradie číslic v čísle, t.j. vzorka je objednaná. Opakovania sú povolené, takže tu máme čo do činenia s usporiadaným (4,8)-výberom s opakovaniami. Alokácia bez opakovaní $n$ prvkov podľa $k$ - usporiadaný $(n,k)$-výber bez opakovaní. Keďže prvky v uvažovanej vzorke sa nedajú opakovať, nemôžeme vo vzorke vybrať viac prvkov, ako je v pôvodnom súbore. Preto pre takéto vzorky platí nasledujúca nerovnosť: $n≥ k$. Počet umiestnení bez opakovania $n$ prvkov pomocou $k$ je určený nasledujúcim vzorcom: \begin(rovnica)A_(n)^(k)=\frac(n{(n-k)!}
\end{equation}
!} Čo znamená znak „!“?: ukázať skryť Nahráva sa "n!" (čítaj "en faktoriál") označuje súčin všetkých čísel od 1 do n, t.j. $$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$ Podľa definície sa predpokladá, že $0!=1!=1$. Napríklad, nájdime 5!: $$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$ Príklad č. 1 Abeceda pozostáva zo sady znakov $E=\(+,*,0,1,f\)$. Určme počet takých trojznakových slov v tejto abecede, ktoré neobsahujú opakované písmená. Trojmiestnymi slovami rozumieme výrazy ako „+*0“ alebo „0f1“. Množina $E$ má päť prvkov, takže písmená trojznakových slov tvoria (5,3)-výbery. Prvá otázka znie: sú tieto vzorky objednané alebo nie? Predpokladá sa, že slová, ktoré sa líšia iba poradím písmen, sú odlišné, takže poradie prvkov vo vzorke je dôležité. Vzorka je teda objednaná. Druhá otázka: sú opakovania povolené alebo nie? Odpoveď na túto otázku je daná podmienkou: slová by nemali obsahovať opakované písmená. Zhrnutie: písmená každého slova, ktoré spĺňa podmienku úlohy, tvoria usporiadanú (5,3)-vzorku bez opakovaní. Inými slovami, písmená každého slova tvoria usporiadanie bez opakovania 5 prvkov z 3. Tu sú príklady takýchto usporiadaní: $$ (+,*,f), \; (*,+,f), \; (1,+,0) $$ Zaujíma nás aj celkový počet týchto umiestnení. Podľa vzorca (1) bude počet umiestnení bez opakovania 5 prvkov po 3 nasledujúci: $$ A_(5)^(3)=\frac(5{(5-3)!}=\frac{5!}{2!}=60.
$$
!} Tie. môžete vytvoriť 60 trojznakových slov, ktorých písmená sa nebudú opakovať. Odpoveď: 60. Umiestnenie s opakovaniami $n$ prvkov nad $k$ je usporiadaný $(n,k)$-výber s opakovaniami. Počet umiestnení s opakovaniami $n$ prvkov po $k$ je určený nasledujúcim vzorcom: \začiatok(rovnica)\bar(A)_(n)^(k)=n^k \end(rovnica) Príklad č. 2 Koľko päťciferných čísel možno vytvoriť z množiny číslic $\(5,7,2\)$? Z tejto sady čísel môžete vytvoriť päťciferné čísla 55555, 75222 atď. Číslice každého takéhoto čísla tvoria (3,5)-vzorku: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Položme si otázku: aké sú tieto vzorky? Po prvé, číslice v číslach sa môžu opakovať, takže máme čo do činenia s ukážkami s opakovaniami. Po druhé, poradie čísel v čísle je dôležité. Napríklad 27755 a 77255 - rôzne čísla. Preto sa zaoberáme usporiadanými (3,5)-výbermi s opakovaniami. Celkový počet takýchto vzoriek (t. j. celkový počet požadovaných päťciferných čísel) možno zistiť pomocou vzorca (2): $$ \bar(A)_(3)^(5)=3^5=243. $$ Z daných číslic teda možno zostaviť 243 päťciferných čísel. Odpoveď: 243. Permutácia bez opakovaní $n$ prvkov je usporiadaný $(n,n)$-výber bez opakovaní. V skutočnosti je to permutácia bez opakovaní špeciálny prípad umiestnenie bez opakovaní, kedy sa veľkosť vzorky rovná výkonu pôvodnej zostavy. Počet permutácií bez opakovaní $n$ prvkov je určený nasledujúcim vzorcom: \begin(rovnica)P_(n)=n! \end(rovnica) Mimochodom, tento vzorec sa dá ľahko získať, ak vezmeme do úvahy, že $P_n=A_(n)^(n)$. Potom dostaneme: $$ P_n=A_(n)^(n)=\frac(n{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n!
$$
!} Príklad č. 3 V mrazničke je päť porcií zmrzliny z rôzne firmy. Koľkými spôsobmi si môžete vybrať poradie, v akom sa jedia? Číslo 1 nech zodpovedá prvej zmrzline, číslo 2 druhej atď. Dostaneme množinu $U=\(1,2,3,4,5\)$, ktorá bude reprezentovať obsah mrazničky. Objednávka jedla môže byť $(2,1,3,5,4)$ alebo $(5,4,3,1,2)$. Každá takáto kolekcia je (5,5)-vzorkou. Bude to usporiadané a bez opakovania. Inými slovami, každá takáto vzorka je permutáciou 5 prvkov pôvodnej sady. Podľa vzorca (3) je celkový počet týchto permutácií: $$ P_5=5!=120. $$ Ide teda o 120 objednávok stravovacieho poriadku. Odpoveď: 120. Permutácia s opakovaniami je usporiadaný $(n,k)$-výber s opakovaniami, v ktorom sa prvok $a_1$ opakuje $k_1$-krát, $a_2$ sa opakuje $k_2$-krát atď., až do posledného prvku $a_r$, čo sa opakuje $ k_r$ krát. Navyše $k_1+k_2+\ldots+k_r=k$. Celkový počet permutácií s opakovaniami je daný: \begin(rovnica)P_(k)(k_1,k_2,\ldots,k_r)=\frac(k{k_1!\cdot k_2!\cdot \ldots \cdot k_r!}
\end{equation}
!} Príklad č. 4 Slová sa tvoria na základe abecedy $U=\(a,b,d\)$. Koľko rôznych slov so siedmimi znakmi možno zložiť, ak sa písmeno "a" musí v týchto slovách zopakovať 2-krát; písmeno "b" - 1 krát a písmeno "d" - 4 krát? Tu sú príklady hľadaných slov: "aabdddd", "daddabd" atď. Písmená každého slova tvoria (3,7)-vzorku s opakovaniami: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d )$ atď. Každý takýto výber pozostáva z dvoch prvkov „a“, jedného prvku „b“ a štyri prvky"d". Inými slovami, $k_1=2$, $k_2=1$, $k_3=4$. Celkový počet opakovaní všetkých znakov sa samozrejme rovná veľkosti vzorky, t.j. $k=k_1+k_2+k_3=7$. Nahradením týchto údajov do vzorca (4) dostaneme: $$ P_7(2,1,4)=\frac(7{2!\cdot 1!\cdot 4!}=105.
$$
!} Celkový počet hľadaných slov je teda 105. Odpoveď: 105. Kombinácia bez opakovaní $n$ prvkov pomocou $k$ je neusporiadaný $(n,k)$-výber bez opakovaní. Celkový počet kombinácií bez opakovania $n$ prvkov pomocou $k$ je určený vzorcom: \begin(rovnica)C_(n)^(k)=\frac(n{(n-k)!\cdot k!}
\end{equation}
!} Príklad č. 5 Košík obsahuje kartičky, na ktorých sú napísané celé čísla od 1 do 10. Z košíka sa vyberú 4 kartičky a čísla na nich napísané sa sčítajú. Koľko rôznych sád kariet je možné vytiahnuť z košíka? Takže v tomto probléme je počiatočná množina nasledovná: $U=\(1,2,3,4,5,6,7,8,9,10\)$. Z tejto sady vyberieme štyri prvky (t.j. štyri karty z košíka). Čísla vytiahnutých prvkov tvoria (10,4)-vzorku. Opakovania v tejto vzorke nie sú povolené, pretože čísla všetkých kariet sú odlišné. Otázka znie: záleží na poradí, v akom sa karty vyberú, alebo nie? To znamená, že sú napríklad vzorky $(1,2,7,10)$ a $(10,2,1,7)$ rovnaké alebo nie? Tu sa musíte obrátiť na stav problému. Karty sa vyberú, aby sa potom našiel súčet prvkov. A to znamená, že poradie kariet nie je dôležité, pretože suma sa nezmení zmenou miesta podmienok. Napríklad vzorka $(1,2,7,10)$ a vzorka $(10,2,1,7)$ sa budú zhodovať s rovnakým číslom $1+2+7+10=10+2+1+7 = 20 $. Záver: z podmienky problému vyplýva, že máme do činenia s neusporiadanými vzorkami. Tie. musíme nájsť celkový počet neusporiadaných (10,4) vzoriek bez opakovaní. Inými slovami, musíme nájsť počet kombinácií 10 prvkov po 4. Používame na to vzorec (5): $$ C_(10)^(4)=\frac(10{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210.
$$
!} Celkový počet požadovaných sád je teda 210. Odpoveď: 210. Kombinácia s opakovaniami $n$ prvkov nad $k$ je neusporiadaný $(n,k)$-výber s opakovaniami. Celkový počet kombinácií s opakovaniami $n$ prvkov nad $k$ je určený vzorcom: \begin(rovnica)\bar(C)_(n)^(k)=\frac((n+k-1){(n-1)!\cdot k!}
\end{equation}
!} Príklad č. 6 Predstavte si, že sme v továrni na cukríky – hneď vedľa dopravníka, po ktorom sa pohybujú štyri druhy cukríkov. Vložíme ruky do tohto prúdu a vytiahneme ich dvadsať. Koľko rôznych „cukríkových kombinácií“ môže byť v hrsti? Ak predpokladáme, že číslo 1 zodpovedá prvému zoradeniu, číslo 2 zodpovedá druhému zoradeniu atď., potom počiatočná množina v našom probléme je nasledovná: $U=\(1,2,3,4\ )$. Z tejto sady vyberieme 20 prvkov (t. j. tých istých 20 cukríkov z dopravníka). Hrsť sladkostí tvorí (4,20)-vzorku. Prirodzene, dôjde k opakovaniu odrôd. Otázkou je, či hrá rolu poradie prvkov vo výbere alebo nie? Z podmienok úlohy vyplýva, že na poradí prvkov nezáleží. Je nám úplne jedno, či hrsť obsahuje najskôr 15 lízaniek a potom 4 čokoládky, alebo najskôr 4 čokoládky a až potom 15 lízaniek. Takže máme čo do činenia s neusporiadanou (4,20) vzorkou s opakovaniami. Na zistenie celkového počtu týchto vzoriek používame vzorec (6): $$ \bar(C)_(4)^(20)=\frac((4+20-1){(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771.
$$
!} Celkový počet požadovaných kombinácií je teda 1771.Úvod. Sady a výbery.
Alokácie bez opakovania $n$ prvkov o $k$
Alokácie s opakovaním $n$ prvkov po $k$
Permutácie bez opakovaní $n$ prvkov
Permutácie s opakovaniami
Kombinácie bez opakovania $n$ prvkov o $k$
Kombinácie s opakovaním $n$ prvkov o $k$
