Na prvním místě v řadě může být kterýkoli z N prvků, existuje tedy N možností. Na druhém místě - jakýkoli, kromě toho, který již byl použit pro první místo. Proto pro každou z N již nalezených možností existuje (N - 1) možností druhého místa a celkový počet kombinací se stane N*(N - 1).
Totéž lze opakovat pro zbývající prvky série. Pro úplně poslední místo zbývá jediná možnost – poslední zbývající prvek. Pro předposlední jsou dvě možnosti a tak dále.
Proto jsou pro řadu N neopakujících se prvků možné permutace rovny součinu všech celých čísel od 1 do N. Tento součin se nazývá N a N! (čti „faktoriálně“).
V předchozím případě se počet možných prvků a počet míst v řadě shodoval a jejich počet byl roven N. Je však možná situace, kdy v řadě méně míst než jsou možné prvky. Jinými slovy, počet prvků ve vzorku se rovná určitému počtu M a M< N. В этом случае задача определения возможных комбинаций может иметь два различных варианта.
Nejprve možná budete muset spočítat celkový počet možné způsoby, kterou lze použít k seřazení M prvků z N. Takové způsoby umístění.
Za druhé, výzkumníka může zajímat počet způsobů, jakými lze M prvků vybrat z N. V tomto případě již není důležité pořadí prvků, ale libovolné dvě možnosti se od sebe musí lišit alespoň o jeden prvek. . Takové metody se nazývají kombinace.
Chcete-li zjistit počet umístění M prvků z N, můžete se uchýlit ke stejné metodě uvažování jako v případě permutací. Stále může být na prvním místě N prvků, na druhém N - 1 a tak dále. Ale na posledním místě množství možné možnosti se nerovná jedné, ale (N - M + 1), protože po dokončení umístění stále zůstanou (N - M) nevyužité prvky.
Počet umístění M prvků z N je tedy roven součinu všech celých čísel od (N - M + 1) do N, neboli, což je stejné, podílu N!/(N - M)!.
Je zřejmé, že počet kombinací M prvků z N bude menší než počet umístění. Pro každou možnou kombinaci existuje M! možná umístění v závislosti na pořadí prvků této kombinace. Pro zjištění této veličiny je tedy potřeba vydělit počet umístění M prvků z N číslem N!. Jinými slovy, počet kombinací M prvků z N se rovná N!/(M!*(N - M)!).
Prameny:
- počet kombinací
Faktorový přirozené číslo je součinem všech předchozích přirozená čísla včetně samotného čísla. Faktorový nula se rovná jedné. Zdá se, že výpočet faktoriálu čísla je velmi jednoduchý – stačí vynásobit všechna přirozená čísla nepřesahující zadané. Hodnota faktoriálu však roste tak rychle, že některé kalkulačky si s tímto úkolem neporadí.
Budete potřebovat
- kalkulačka, počítač
Instrukce
Chcete-li vypočítat faktoriál přirozeného čísla, vynásobte všechny , nepřekračujte danou hodnotu. Každé číslo se počítá pouze jednou. Ve formě vzorce to lze zapsat takto: n! = 1*2*3*4*5*…*(n-2)*(n-1)*n, kde n je přirozené číslo, jehož faktoriál je třeba vypočítat.
0! je brána jako rovna jedné (0!=1 Jak argument roste, hodnota faktoriálu roste velmi rychle, takže obvyklý (účetní) faktor, již pro faktoriál 15, může dát chybu místo a). výsledek.
Chcete-li vypočítat faktoriál velkého přirozeného čísla, vezměte si inženýrskou kalkulačku. To znamená, že taková kalkulačka na klávesnici má symboly matematických funkcí (cos, sin, √). Zadejte původní číslo do kalkulačky a poté klikněte na tlačítko faktoriálu. Obvykle tlačítko jako "n!" nebo podobné (místo „n“ může být „N“ nebo „x“, ale Vykřičník"!" v každém případě musí být přítomno faktoriální označení).
Pro velké hodnoty argumentu se výsledky výpočtu začnou zobrazovat v „exponenciální“ (exponenciální) podobě. Takže například faktoriál 50 by byl reprezentován ve tvaru: 3,0414093201713378043612608166065e+64 (nebo podobný). Chcete-li získat výsledek výpočtů v obvyklé podobě, přidejte k číslu zobrazenému před symbolem „e“ tolik nul, kolik je uvedeno za „e+“ (pokud je samozřejmě dostatek místa).
V tomto článku budeme hovořit o speciálním odvětví matematiky zvané kombinatorika. Vzorce, pravidla, příklady řešení problémů – to vše zde najdete po přečtení článku až do konce.
Co je tedy tato sekce? Kombinatorika se zabývá problematikou počítání libovolných předmětů. Ale v v tomto případě předměty nejsou švestky, hrušky nebo jablka, ale něco jiného. Kombinatorika nám pomáhá najít pravděpodobnost události. Například při hraní karet – jaká je pravděpodobnost, že má soupeř trumf? Nebo tento příklad: jaká je pravděpodobnost, že z pytlíku dvaceti kuliček dostanete bílou? Právě pro tento druh problémů potřebujeme znát alespoň základy tohoto odvětví matematiky.
Kombinatorické konfigurace
Vzhledem k problematice základních pojmů a vzorců kombinatoriky si nelze nevšímat kombinatorických konfigurací. Používají se nejen k formulaci, ale i k řešení různé příklady takové modely jsou:
- ubytování;
- přeskupení;
- kombinace;
- složení čísel;
- rozdělení čísla.
O prvních třech si povíme podrobněji později, ale v této části se budeme věnovat kompozici a rozdělení. Když mluví o složení určitého čísla (například a), myslí tím znázornění čísla a jako uspořádaného součtu určitých kladných čísel. A oddíl je neuspořádaný součet.
Sekce
Než přejdeme přímo ke kombinatorikovým vzorcům a zvažování problémů, stojí za to věnovat pozornost skutečnosti, že kombinatorika, stejně jako ostatní odvětví matematiky, má své vlastní podsekce. Tyto zahrnují:
- výčtový;
- strukturální;
- extrémní;
- Ramseyho teorie;
- pravděpodobnostní;
- topologické;
- nekonečná.
V prvním případě mluvíme o tom o kalkulativní kombinatorice problémy uvažují výčet nebo počítání různých konfigurací, které jsou tvořeny prvky množin. Na tyto sestavy jsou zpravidla uvalena určitá omezení (rozlišitelnost, nerozlišitelnost, možnost opakování atd.). A počet těchto konfigurací se vypočítá pomocí pravidel sčítání nebo násobení, o kterých si povíme trochu později. Strukturní kombinatorika zahrnuje teorie grafů a matroidů. Příkladem extremálního kombinatorického problému je, jaký je největší rozměr grafu, který splňuje následující vlastnosti... Ve čtvrtém odstavci jsme zmínili Ramseyho teorii, která studuje přítomnost pravidelných struktur v náhodných konfiguracích. Pravděpodobnostní kombinatorika je schopna odpovědět na otázku - jaká je pravděpodobnost, že daná sada existuje určitá vlastnost. Jak asi tušíte, topologická kombinatorika používá metody v topologii. A konečně sedmý bod – nekonečná kombinatorika studuje aplikaci kombinatorikových metod na nekonečné množiny.
Pravidlo sčítání
Mezi kombinatorickými vzorci se dají najít docela jednoduché vzorce, se kterými se známe už poměrně dlouho. Příkladem je pravidlo součtu. Předpokládejme, že jsou nám dány dvě akce (C a E), pokud se vzájemně vylučují, akci C lze provést několika způsoby (například a) a akci E lze provést b-způsoby, pak kterýkoli z nich ( C nebo E) lze provést způsoby a + b .
Teoreticky je to docela obtížné pochopit, pokusíme se to sdělit na jednoduchém příkladu. Vezměme si průměrný počet žáků v jedné třídě – řekněme, že je to dvacet pět. Mezi nimi je patnáct dívek a deset chlapců. Každý den je do každé třídy přidělen jeden člověk ve službě. Kolika způsoby je dnes možné jmenovat dozorce třídy? Řešení problému je celkem jednoduché, uchýlíme se k pravidlu sčítání. Text problému neříká, že ve službě mohou být pouze chlapci nebo pouze dívky. Proto to mohla být kterákoli z patnácti dívek nebo kterýkoli z deseti chlapců. Aplikací součtového pravidla dostaneme celkem jednoduchý příklad, který hravě zvládne i školák primární třídy: 15 + 10. Po započítání dostaneme odpověď: dvacet pět. To znamená, že pro dnešek existuje pouze dvacet pět způsobů, jak přidělit službu.
Pravidlo násobení
Mezi základní vzorce kombinatoriky patří také pravidlo násobení. Začněme teorií. Řekněme, že potřebujeme provést několik akcí (a): první akce se provede 1 způsoby, druhá - 2 způsoby, třetí - 3 způsoby a tak dále až do poslední a-akce, provedená 3 způsoby. Pak lze všechny tyto akce (kterých máme celkem) provést N způsoby. Jak vypočítat neznámé N? K tomu nám pomůže vzorec: N = c1 * c2 * c3 *…* ca.
Teoreticky opět není nic jasné, pojďme k úvahám jednoduchý příklad použít pravidlo násobení. Vezměme stejnou třídu dvaceti pěti lidí, ve které je patnáct dívek a deset chlapců. Tentokrát musíme vybrat dva lidi ve službě. Mohou to být buď jen chlapci nebo dívky, nebo chlapec a dívka. Přejděme k elementárnímu řešení problému. Vybíráme prvního ve službě, jak jsme se rozhodli v posledním odstavci, dostáváme dvacet pět možných možností. Druhá osoba ve službě může být kterákoli ze zbývajících osob. Měli jsme pětadvacet studentů, vybrali jsme jednoho, což znamená, že druhým člověkem ve službě mohl být kterýkoli ze zbývajících čtyřiadvaceti lidí. Nakonec použijeme pravidlo násobení a zjistíme, že dva důstojníci ve službě mohou být zvoleni šesti sty způsoby. My dané číslo získaná vynásobením dvaceti pěti a dvaceti čtyřmi.
Přeskupení
Nyní se podíváme na další kombinatorický vzorec. V této části článku budeme hovořit o permutacích. Navrhujeme okamžitě zvážit problém pomocí příkladu. Vezměme kulečníkové koule, máme jich n-té číslo. Musíme spočítat, kolik je možností seřadit je za sebou, tedy vytvořit uspořádanou sadu.
Začneme, když nemáme koule, tak máme i nulové možnosti umístění. A pokud máme jednu kouli, pak je uspořádání také stejné (matematicky to lze zapsat takto: P1 = 1). Dva míčky lze umístit do dvou různé způsoby: 1.2 a 2.1. Proto P2 = 2. Tři kuličky mohou být uspořádány šesti způsoby (P3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. Co když takových koulí nejsou tři, ale deset nebo patnáct? Vyjmenovat všechny možné možnosti by trvalo velmi dlouho, pak nám přichází na pomoc kombinatorika. Permutační vzorec nám pomůže najít odpověď na otázku, která nás zajímá. Pn = n*P (n-1). Pokusíme-li se vzorec zjednodušit, dostaneme: Pn = n* (n - 1) *…* 2 * 1. A to je součin prvních přirozených čísel. Toto číslo se nazývá faktoriál a označuje se jako n!
Zvažme problém. Každé ráno poradce seřadí svůj tým (dvacet lidí). V týmu jsou tři nejlepší přítel- Kosťa, Sasha a Lesha. Jaká je pravděpodobnost, že budou stát vedle sebe? Abyste našli odpověď na otázku, musíte vydělit pravděpodobnost „dobrého“ výsledku celkovým počtem výsledků. Celkový počet permutací je 20! = 2,5 kvintilionů. Jak spočítat počet „dobrých“ výsledků? Předpokládejme, že Kosťa, Sasha a Lesha jsou jeden superman. Pak už máme jen osmnáct předmětů. Počet permutací je v tomto případě 18 = 6,5 kvadrilionu. S tím vším se Kosťa, Sasha a Lesha mohou mezi sebou libovolně pohybovat ve své nedělitelné trojici, a to ještě 3! = 6 možností. To znamená, že máme celkem 18 „dobrých“ uspořádání! *3! Vše, co musíme udělat, je najít požadovanou pravděpodobnost: (18! * 3!) / 20! Což se rovná přibližně 0,016. Pokud se převede na procenta, vyjde to jen na 1,6 %.
Ubytování
Nyní se podíváme na další velmi důležitý a nezbytný kombinatorický vzorec. Ubytování je naše další otázka, které vás zveme ke zvážení v této části článku. Jedeme pro komplikace. Předpokládejme, že chceme uvažovat možné permutace nikoli z celé množiny (n), ale z menší (m). To znamená, že uvažujeme permutace n položek m.
Základní vzorce kombinatoriky by se měly nejen naučit nazpaměť, ale také jim porozumět. I když jsou složitější, protože nemáme jeden parametr, ale dva. Předpokládejme, že m = 1, pak A = 1, m = 2, pak A = n * (n - 1). Pokud vzorec dále zjednodušíme a přejdeme na zápis pomocí faktoriálů, dostaneme zcela lakonický vzorec: A = n! / (n - m)!
Kombinace
Zopakovali jsme si téměř všechny základní kombinatorické vzorce s příklady. Nyní přejděme k závěrečné fázi zvažování základního kurzu kombinatoriky – poznávání kombinací. Nyní vybereme m položek z n, které máme, a vybereme vše všemi možnými způsoby. Jak se to tedy liší od umístění? Na objednávku nebudeme brát zřetel. Tato neuspořádaná sada bude kombinací.
Okamžitě zavedeme zápis: C. Z n vyjmeme umístění m kuliček. Přestáváme dbát na pořádek a končíme u opakujících se kombinací. Abychom získali počet kombinací, musíme počet umístění vydělit m! (m faktoriál). To znamená, C = A / m! Existuje tedy jen několik způsobů, jak vybrat z n kuliček, což se přibližně rovná počtu způsobů, jak vybrat téměř všechny. Existuje na to logický výraz: vybrat si trochu je totéž, jako vyhodit skoro všechno. Na tomto místě je také důležité zmínit, že maximálního počtu kombinací lze dosáhnout při pokusu o výběr poloviny položek.
Jak vybrat vzorec k vyřešení problému?
Podrobně jsme prozkoumali základní vzorce kombinatoriky: umístění, permutace a kombinace. Nyní je naším úkolem výběr usnadnit požadovaný vzorec vyřešit kombinatorický problém. Můžete použít následující poměrně jednoduché schéma:
- Zeptejte se sami sebe: bere se v textu problému v úvahu pořadí, ve kterém jsou prvky umístěny?
- Pokud je odpověď ne, použijte kombinační vzorec (C = n! / (m! * (n - m)!)).
- Pokud je odpověď ne, pak je třeba odpovědět na další otázku: jsou všechny prvky zahrnuty v kombinaci?
- Pokud je odpověď ano, použijte permutační vzorec (P = n!).
- Pokud je odpověď ne, použijte vzorec pro umístění (A = n! / (n - m)!).
Příklad
Podívali jsme se na prvky kombinatoriky, vzorce a některé další problémy. Nyní přejděme ke skutečnému problému. Představte si, že máte před sebou kiwi, pomeranč a banán.
Otázka první: kolika způsoby je lze přeskupit? K tomu použijeme permutační vzorec: P = 3! = 6 způsobů.
Otázka druhá: na kolik způsobů si můžete vybrat jedno ovoce? To je zřejmé, máme jen tři možnosti – vybrat si kiwi, pomeranč nebo banán, ale použijme kombinační vzorec: C = 3! / (2! * 1!) = 3.
Otázka třetí: kolika způsoby si můžete vybrat dva druhy ovoce? Jaké máme vůbec možnosti? Kiwi a pomeranč; kiwi a banán; pomeranč a banán. To znamená, že existují tři možnosti, ale to lze snadno zkontrolovat pomocí kombinačního vzorce: C = 3! / (1! * 2!) = 3
Otázka čtvrtá: Kolika způsoby si můžete vybrat tři druhy ovoce? Jak vidíte, existuje pouze jeden způsob, jak vybrat tři druhy ovoce: vezměte si kiwi, pomeranč a banán. C = 3! / (0! * 3!) = 1.
Otázka pět: na kolik způsobů si můžete vybrat alespoň jedno ovoce? Tato podmínka znamená, že můžeme vzít jeden, dva nebo všechny tři plody. Proto sečteme C1 + C2 + C3 = 3 + 3 + 1 = 7. To znamená, že máme sedm způsobů, jak vzít alespoň jedno ovoce ze stolu.
Je třeba poznamenat, že kombinatorika je samostatnou větví vyšší matematiky (a není součástí terveru) a o této disciplíně byly napsány závažné učebnice, jejichž obsah občas není o nic jednodušší než abstraktní algebra. Malá porce teoretických znalostí nám však bude stačit a v tomto článku se pokusím přístupnou formou rozebrat základy tématu s typickými kombinatorickými problémy. A mnozí z vás mi pomohou ;-)
Co budeme dělat? V užším smyslu je kombinatorika výpočet různých kombinací, které lze z určité množiny vytvořit oddělený objektů. Předměty jsou chápány jako jakékoli izolované předměty nebo živé bytosti - lidé, zvířata, houby, rostliny, hmyz atd. Kombinatoriku přitom vůbec nezajímá, že sestavu tvoří talíř krupicové kaše, páječka a bažinná žába. Zásadně důležité je, že tyto objekty lze vyčíslit – jsou tři (diskrétnost) a důležité je, že žádný z nich není stejný.
Řešili jsme toho hodně, teď o kombinacích. Nejčastějšími typy kombinací jsou permutace objektů, jejich výběr z množiny (kombinace) a distribuce (umístění). Podívejme se, jak se to děje právě teď:
Permutace, kombinace a umístění bez opakování
Nebojte se nejasných termínů, zvláště když některé z nich opravdu nejsou moc dobré. Začněme koncem nadpisu – co dělá “ žádné opakování"? To znamená, že v této části budeme uvažovat množiny, které se skládají z rozličný objektů. Například ... ne, nebudu nabízet kaši s páječkou a žábou, je lepší si dát něco chutnějšího =) Představte si, že se před vámi na stole zhmotnilo jablko, hruška a banán ( pokud je máte, lze situaci simulovat ve skutečnosti). Plody rozmístíme zleva doprava v následujícím pořadí:
jablko / hruška / banán
Otázka jedna: Kolika způsoby je lze přeskupit?
Jedna kombinace již byla napsána výše a se zbytkem nejsou žádné problémy:
jablko / banán / hruška
hruška / jablko / banán
hruška / banán / jablko
banán / jablko / hruška
banán / hruška / jablko
Celkový: 6 kombinací nebo 6 permutace.
Dobře, nebylo těžké vyjmenovat všechny možné případy, ale co když existuje více objektů? S pouhými čtyřmi různými druhy ovoce se počet kombinací výrazně zvýší!
Otevřete prosím referenční materiál (je vhodné vytisknout návod) a v bodě č. 2 najděte vzorec pro počet permutací.
Žádné potíže – 3 objekty lze přeskupit různými způsoby.
Otázka dvě: Na kolik způsobů můžete vybrat a) jeden plod, b) dva druhy ovoce, c) tři druhy ovoce, d) alespoň jeden plod?
Proč si vybrat? Chuť k jídlu jsme si tedy vypracovali v předchozím bodě – abychom se najedli! =)
a) Jedno ovoce lze vybrat samozřejmě třemi způsoby - vezměte si buď jablko, hrušku nebo banán. Formální výpočet se provádí podle vzorec pro počet kombinací:
Záznam v tomto případě je třeba chápat takto: „Kolik způsobů si můžete vybrat 1 ovoce ze tří?
b) Uveďme všechny možné kombinace dvou druhů ovoce:
jablko a hruška;
jablko a banán;
hruška a banán.
Počet kombinací lze snadno zkontrolovat pomocí stejného vzorce:
Záznam je chápán podobně: "Kolik způsobů si můžete vybrat 2 ovoce ze tří?"
c) A nakonec je jen jeden způsob, jak vybrat tři druhy ovoce:
Mimochodem, vzorec pro počet kombinací zůstává smysluplný pro prázdný vzorek:
Tímto způsobem si nemůžete vybrat ani jedno ovoce - ve skutečnosti si neberte nic a je to.
d) Kolika způsoby se můžete vydat aspoň jeden ovoce? Podmínka „alespoň jedno“ znamená, že jsme spokojeni s 1 ovocem (jakýmkoli) nebo libovolnými 2 ovocemi nebo všemi 3 druhy ovoce:
pomocí těchto metod si můžete vybrat alespoň jedno ovoce.
Čtenáři, kteří si pečlivě prostudovali úvodní lekci na teorie pravděpodobnosti, už jsme něco tušili. Ale o významu znaménka plus později.
K zodpovězení další otázky potřebuji dva dobrovolníky... ...No, protože nikdo nechce, zavolám si vás do představenstva =)
Otázka tři: Kolika způsoby můžete dát Dáše a Nataše po jednom ovoce?
Abyste mohli distribuovat dva druhy ovoce, musíte je nejprve vybrat. Podle odstavce „být“ předchozí otázky to lze provést způsoby, přepíšu je:
jablko a hruška;
jablko a banán;
hruška a banán.
Teď ale bude kombinací dvakrát tolik. Vezměme si například první pár ovoce:
Dášu můžete ošetřit jablkem a Natašu hruškou;
nebo naopak - Dáša dostane hrušku a Nataša jablko.
A taková permutace je možná pro každý pár plodů.
Vezměme si stejnou skupinu studentů, která šla na tanec. Kolika způsoby mohou být chlapec a dívka spárováni?
Způsoby, jak můžete vybrat 1 mladého muže;
způsoby, jak si můžete vybrat 1 dívku.
Tedy jeden mladý muž A Můžete si vybrat jednu dívku: 
způsoby.
Když je vybrán 1 objekt z každé sady, pak další princip počítání kombinací: " každý objekt z jedné sady může tvořit pár s každým objekt jiné množiny."
To znamená, že Oleg může vyzvat k tanci kteroukoli ze 13 dívek, Evgeny také kteroukoli ze třinácti a zbytek mladých lidí má podobnou volbu. Celkem: možné páry.
Je třeba poznamenat, že v tomto příkladu nezáleží na „historii“ vytvoření páru; pokud však vezmeme v úvahu iniciativu, musí se počet kombinací zdvojnásobit, protože každá ze 13 dívek může vyzvat k tanci i libovolného chlapce. Vše závisí na podmínkách konkrétního úkolu!
Podobný princip platí pro složitější kombinace, například: kolika způsoby si můžete vybrat dva mladé muže? A aby se dvě dívky zúčastnily parodie KVN?
svaz A jasně naznačuje, že kombinace je třeba znásobit:
Možné skupiny umělců.
Jinými slovy, každý může vystupovat dvojice chlapců (45 unikátních párů). žádný dvojice dívek (78 unikátních párů). A pokud vezmeme v úvahu rozdělení rolí mezi účastníky, bude kombinací ještě více. ...moc chci, ale i tak se zdržím pokračování, abych ve vás nevzbudil odpor ke studentskému životu =).
Platí také pravidlo pro násobení kombinací velké množství multiplikátory:
Problém 8
Kolik existuje trojciferných čísel, která jsou dělitelná 5?
Řešení: pro názornost označme toto číslo třemi hvězdičkami: ***
V stovky míst Můžete napsat libovolné z čísel (1, 2, 3, 4, 5, 6, 7, 8 nebo 9). Nula není vhodná, protože v tomto případě přestává být číslo třímístné.
Ale v desítky místo(„uprostřed“) si můžete vybrat kteroukoli z 10 číslic: .
Podle podmínky musí být číslo dělitelné 5. Číslo je dělitelné 5, pokud končí 5 nebo 0. Spokojíme se tedy se 2 číslicemi v nejméně významné číslici.
Celkem existuje: trojciferná čísla, která jsou dělitelná 5.
V tomto případě je dílo dešifrováno následovně: „9 způsobů, jak si můžete vybrat číslo stovky míst A 10 způsobů, jak vybrat číslo desítky místo A 2 cesty dovnitř číslice jednotek»
Nebo ještě jednodušeji: " každý od 9 číslic do stovky míst kombinuje s každým 10 číslic desítky místo a s každým ze dvou číslic na číslice jednotek».
Odpovědět: 180
A teď…
Ano, málem bych zapomněl na slíbený komentář k problému č. 5, ve kterém lze Borovi, Dimovi a Voloďovi rozdat každému po jedné kartě různými způsoby. Násobení zde má stejný význam: způsoby, jak odstranit 3 karty z balíčku A v každém vzorek je uspořádat způsoby.
A teď úkol pro nezávislé rozhodnutí... teď vymyslím něco zajímavějšího, ... ať je to o stejné ruské verzi blackjacku:
Problém 9
Kolik výherních kombinací 2 karet existuje při hře „bod“?
Pro ty, kteří nevědí: výherní kombinace je 10 + ACE (11 bodů) = 21 bodů a uvažujme vítěznou kombinaci dvou es.
(na pořadí karet v libovolném páru nezáleží)
Krátké řešení a odpověď na konci lekce.
Mimochodem, nepovažujte příklad za primitivní. Blackjack je téměř jediná hra, pro kterou existuje matematicky založený algoritmus, který vám umožní porazit kasino. Zájemci snadno najdou množství informací o optimální strategii a taktice. Pravda, takoví mistři docela rychle skončí na černé listině všech provozoven =)
Je čas konsolidovat probraný materiál několika pevnými úkoly:
Problém 10
Vasya má doma 4 kočky.
a) kolika způsoby mohou být kočky usazeny v rozích místnosti?
b) kolika způsoby můžete pustit kočky na procházku?
c) kolika způsoby může Vasja zvednout dvě kočky (jednu nalevo, druhou napravo)?
Pojďme se rozhodnout: za prvé byste měli znovu věnovat pozornost skutečnosti, že se problém zabývá odlišný předměty (i když jsou kočky jednovaječná dvojčata). To je velmi důležitá podmínka!
a) Ticho koček. S výhradou tohoto provedení všechny kočky najednou
+ jejich umístění je důležité, takže zde jsou permutace:
pomocí těchto metod můžete umístit kočky do rohů místnosti.
Opakuji, že při permutaci pouze počet různých objektů a jejich vzájemné domluvě. V závislosti na Vasyově náladě může zvířata posadit v půlkruhu na pohovce, v řadě na parapetu atd. – ve všech případech bude existovat 24 permutací Pro usnadnění si mohou zájemci představit, že kočky jsou vícebarevné (například bílá, černá, červená a mourovatá) a uvést všechny. možné kombinace.
b) Kolika způsoby můžete pustit kočky na procházku?
Předpokládá se, že kočky chodí na procházky pouze dveřmi a z otázky vyplývá lhostejnost ohledně počtu zvířat - na procházku může jít 1, 2, 3 nebo všechny 4 kočky.
Počítáme všechny možné kombinace:
Způsoby, jak můžete nechat jednu kočku (kteroukoli ze čtyř) jít na procházku; 
způsoby, jak můžete nechat dvě kočky jít na procházku (uveďte možnosti sami);
způsobem můžete nechat tři kočky jít na procházku (jedna ze čtyř sedí doma);
Tímto způsobem můžete uvolnit všechny kočky.
Pravděpodobně jste uhodli, že výsledné hodnoty by měly být sečteny:
způsoby, jak můžete nechat kočky chodit na procházky.
Pro nadšence nabízím komplikovanou verzi problému – kdy jakákoliv kočka v jakémkoliv vzorku může náhodně vyjít ven, a to jak dveřmi, tak oknem v 10. patře. Bude znatelný nárůst kombinací!
c) Kolika způsoby může Vasja sebrat dvě kočky?
Situace zahrnuje nejen výběr 2 zvířat, ale také jejich umístění do každé ruky:
Tímto způsobem můžete vyzvednout 2 kočky.
Druhé řešení: můžete si vybrat dvě kočky pomocí metod A způsoby pěstování každý pár po ruce: 
Odpovědět: a) 24, b) 15, c) 12
No, pro vyčištění svědomí něco konkrétnějšího o násobení kombinací... Nechte Vasyu mít 5 dalších koček =) Kolika způsoby můžete nechat 2 kočky jít na procházku? A 1 kočka?
Tedy s každý pár koček může být vypuštěno každý kočka.
Další knoflíková harmonika pro samostatné řešení:
Problém 11
Tři cestující nastoupili do výtahu 12patrové budovy. Každý, bez ohledu na ostatní, může se stejnou pravděpodobností vystoupit na libovolném (od 2.) podlaží. Kolika způsoby:
1) cestující mohou vystoupit na stejném patře (na pořadí odchodu nezáleží);
2) dvě osoby mohou vystoupit na jednom patře a třetí na druhém;
3) lidé mohou vycházet na různých podlažích;
4) mohou cestující opustit výtah?
A tady se často ptají znovu, objasňuji: pokud 2 nebo 3 lidé vystupují na stejném patře, pak na pořadí výstupu nezáleží. MYSLETE, používejte vzorce a pravidla pro sčítání/násobení kombinací. V případě potíží je pro cestující užitečné uvést jména a spekulovat, v jakých kombinacích mohou výtah vystoupit. Není třeba se rozčilovat, když se něco nepovede, třeba bod č. 2 je docela záludný.
Kompletní řešení s podrobné komentáře na konci lekce.
Poslední odstavec je věnován kombinacím, které se také vyskytují poměrně často - podle mého subjektivního hodnocení přibližně u 20-30% kombinatorických úloh:
Permutace, kombinace a umístění s opakováním
Uvedené druhy kombinace jsou uvedeny v odstavci č. 5 referenčního materiálu Základní vzorce kombinatoriky, některé z nich však nemusí být při prvním čtení příliš jasné. V tomto případě je nejprve vhodné se s ním seznámit praktické příklady a teprve poté porozumět obecné formulaci. Jít:
Permutace s opakováním
V permutacích s opakováním, jako v „obyčejných“ permutacích, všech mnoho objektů najednou, ale je tu jedna věc: v této množině se jeden nebo více prvků (objektů) opakuje. Dodržujte následující standard:
Problém 12
Kolik různých kombinací písmen lze získat přeskupením karet s následujícími písmeny: K, O, L, O, K, O, L, b, Ch, I, K?
Řešení: v případě, že by se všechna písmena lišila, bylo by nutné použít triviální vzorec, ale je zcela jasné, že pro navrhovanou sadu karet budou některé manipulace fungovat „nečinně“, například pokud vyměníte libovolné dvě karty s písmeny "K" " v libovolném slově získáte stejné slovo. Navíc fyzicky mohou být karty velmi odlišné: jedna může být kulatá s vytištěným písmenem „K“, druhá může být čtvercová s nakresleným písmenem „K“. Ale podle smyslu úkolu i takové karty jsou považovány za stejné, protože podmínka se ptá na kombinace písmen.
Vše je extrémně jednoduché - pouze 11 karet včetně písmene:
K – opakuje se 3x;
O – opakuje se 3x;
L – opakuje se 2x;
b – opakování 1krát;
H – opakováno 1krát;
A - opakováno 1krát.
Kontrola: 3 + 3 + 2 + 1 + 1 + 1 = 11, což je potřeba zkontrolovat.
Podle vzorce počet permutací s opakováním:
lze získat různé kombinace písmen. Více než půl milionu!
Pro rychlý výpočet velké hodnoty faktoriálu je vhodné použít standardní funkci Excelu: zadejte do libovolné buňky =FAKT(11) a stiskněte Vstupte.
V praxi je celkem přijatelné obecný vzorec nepsat a navíc vynechat jednotkové faktoriály: 
Ale předběžné komentáře k opakovaným dopisům jsou povinné!
Odpovědět: 554400
Další typický příklad permutací s opakováním nastává v problému umístění šachových figurek, které lze nalézt ve skladu hotová řešení v odpovídajícím pdf. A pro nezávislé řešení jsem přišel s méně vzorovým úkolem:
Problém 13
Alexey se věnuje sportu a 4 dny v týdnu - atletika, 2 dny - silových cvičení a odpočívá 1 den. Kolika způsoby si může vytvořit týdenní rozvrh pro sebe?
Vzorec zde nefunguje, protože počítá s náhodnými záměnami (například záměna středečních posilovacích cviků za čtvrteční). A znovu - vlastně to samé 2 silový trénink se mohou navzájem velmi lišit, ale v kontextu úkolu (z hlediska plánu) jsou považovány za stejné prvky.
Dvouřádkové řešení a odpověď na konci lekce.
Kombinace s opakováním
Vlastnosti Tento typ kombinace spočívá v tom, že vzorek je čerpán z několika skupin, z nichž každá se skládá z identických objektů.
Všichni dnes tvrdě pracovali, takže je čas se osvěžit:
Problém 14
Studentská jídelna prodává uzeniny v těstě, tvarohové koláče a koblihy. Kolika způsoby si můžete koupit pět koláčů?
Řešení: ihned věnujte pozornost typickému kritériu pro kombinace s opakováním - podle podmínky se nenabízí k výběru soubor objektů jako takový, ale různé druhy předměty; předpokládá se, že v prodeji je minimálně pět párků v rohlíku, 5 tvarohových dortů a 5 koblih. Koláče v každé skupině jsou samozřejmě jiné - protože naprosto identické koblihy lze simulovat pouze na počítači =) Fyzikální vlastnosti koláčů však nejsou pro účel problému podstatné a párky v rohlíku / tvarohové koláče / koblihy ve svých skupinách jsou považovány za stejné.
Co může být ve vzorku? Předně nutno podotknout, že ve vzorku budou určitě identické koláče (jelikož vybíráme 5 kusů, a na výběr jsou 3 druhy). Zde jsou možnosti pro každý vkus: 5 párků v rohlíku, 5 tvarohových koláčů, 5 donutů, 3 párky v rohlíku + 2 tvarohové koláče, 1 párek v rohlíku + 2 tvarohové koláče + 2 koblihy atd.
Stejně jako u „běžných“ kombinací nezáleží na pořadí výběru a umístění koláčů ve výběru - stačí si vybrat 5 kusů a je to.
Použijeme vzorec 
počet kombinací s opakováním: 
Tímto způsobem můžete zakoupit 5 koláčů.
Dobrou chuť!
Odpovědět: 21
Jaký závěr lze vyvodit z mnoha kombinatorických problémů?
Někdy je nejtěžší porozumět stavu.
Podobný příklad pro nezávislé řešení:
Problém 15
V peněžence je toho dost velký počet 1-, 2-, 5- a 10-rublové mince. Kolika způsoby lze z peněženky odstranit tři mince?
Pro účely sebeovládání odpovězte na několik jednoduchých otázek:
1) Mohou se všechny mince ve vzorku lišit?
2) Pojmenujte „nejlevnější“ a „nejdražší“ kombinaci mincí.
Řešení a odpovědi na konci lekce.
Z mého osobní zkušenost, mohu říci, že kombinace s opakováním jsou v praxi nejvzácnějším hostem, což nelze říci o následujícím typu kombinací:
Umístění s opakováním
Ze sady skládající se z prvků se prvky vybírají a pořadí prvků v každém výběru je důležité. A všechno by bylo v pořádku, ale poněkud nečekaný vtip je v tom, že si můžeme vybrat jakýkoli předmět původní sady, kolikrát chceme. Obrazně řečeno, „množství se nezmenšuje“.
Kdy se to stane? Typickým příkladem je číselný zámek s několika disky, ale vzhledem k vývoji technologie je důležitější zvážit jeho digitálního potomka:
Problém 16
Kolik čtyřmístných kódů PIN existuje?
Řešení: ve skutečnosti k vyřešení problému stačí znalost pravidel kombinatoriky: způsoby můžete vybrat první číslici PIN kódu A způsoby - druhá číslice PIN kódu A tolika způsoby - třetí A stejné číslo - čtvrté. Podle pravidla násobení kombinací lze tedy čtyřmístný pin kód skládat: způsoby.
A nyní pomocí vzorce. Podle stavu je nám nabídnuta sada čísel, ze kterých se čísla vybírají a řadí v určitém pořadí, přičemž čísla ve vzorku se mohou opakovat (tj. libovolnou číslici původní sady lze použít libovolný počet opakování). Podle vzorce pro počet umístění s opakováním: 
Odpovědět: 10000
Co mě tu napadá... ...pokud bankomat kartu „sežere“ po třetím neúspěšném pokusu o zadání PIN kódu, pak je šance na náhodné vyzvednutí velmi malá.
A kdo řekl, že kombinatorika nemá praktický význam? Poznávací úkol pro všechny čtenáře webu:
Problém 17
Podle státní norma, SPZ auta se skládá ze 3 číslic a 3 písmen. V tomto případě je číslo se třemi nulami nepřijatelné a písmena se vybírají z množiny A, B, E, K, M, N, O, P, S, T, U, X (používají se pouze písmena azbuky, jejichž pravopis se shoduje s latinskými písmeny).
Kolik různých SPZ lze vytvořit pro region?
Mimochodem, není jich tolik. Ve velkých regionech takové množství nestačí, a proto pro ně existuje několik kódů pro nápis RUS.
Řešení a odpověď jsou na konci lekce. Nezapomeň používat pravidla kombinatoriky ;-) ...chtěl jsem se pochlubit tím, co bylo exkluzivní, ale ukázalo se, že exkluzivní není =) Koukal jsem na Wikipedii - jsou tam výpočty, i když bez komentáře. I když pro vzdělávací účely to asi málokdo řešil.
Naše vzrušující lekce skončila a na závěr chci říci, že jste neztráceli čas – z toho důvodu, že kombinatorické vzorce nacházejí další zásadní praktické uplatnění: nacházejí se v různých problémech v teorie pravděpodobnosti,
a dovnitř problémy zahrnující klasické určování pravděpodobnosti- hlavně často =)
Děkujeme všem za aktivní účast a brzy na viděnou!
Řešení a odpovědi:
Úkol 2: Řešení: najděte počet všech možných permutací 4 karet:
Když je karta s nulou umístěna na 1. místě, číslo se stává třímístné, takže tyto kombinace by měly být vyloučeny. Nechť je na 1. místě nula, pak zbývající 3 číslice na spodních číslicích lze různě přeskupovat.
Poznámka
: protože Protože existuje jen několik karet, je snadné zde uvést všechny možnosti:
0579
0597
0759
0795
0957
0975
Z navržené sady tedy můžeme vytvořit:
24 – 6 = 18 čtyřmístných čísel
Odpovědět
: 18
Úkol 4: Řešení: způsoby si můžete vybrat 3 karty z 36.
Odpovědět
: 7140
Úkol 6: Řešení: 
způsoby.
Jiné řešení
: způsoby, jak můžete vybrat dva lidi ze skupiny a a
2) „Nejlevnější“ sada obsahuje 3 rublové mince a „nejdražší“ – 3 desetirublové mince.
Problém 17: Řešení: 
pomocí těchto metod můžete vytvořit digitální kombinaci čísla vozu, přičemž jedna z nich (000) by měla být vyloučena: .
pomocí těchto metod můžete vytvořit kombinaci písmen SPZ.
Podle pravidla násobení kombinací lze součet vytvořit:
poznávací značky
(každý digitální kombinace je kombinována s každým kombinace písmen).
Odpovědět
: 1726272
V kombinatorice studují otázky, kolik kombinací určitého typu lze vytvořit z daných předmětů (prvků).
Zrod kombinatoriky jako oboru je spojen s pracemi B. Pascala a P. Fermata o teorii hazardu. Velkým přínosem pro rozvoj kombinatorických metod byl G.V. Leibniz, J. Bernoulli a L. Euler.
Francouzský filozof, spisovatel, matematik a fyzik Blaise Pascal (1623–1662) projevoval své vynikající matematické schopnosti již brzy. Pascalův okruh matematických zájmů byl velmi rozmanitý. Pascal dokázal jednu věc
ze základních vět projektivní geometrie (Pascalova věta), navrhl sčítací stroj (Pascalův sčítací stroj), dal metodu pro výpočet binomických koeficientů (Pascalův trojúhelník), jako první přesně definoval a aplikoval metodu matematické indukce k důkazu, uvedl metodu výpočtu binomických koeficientů (Pascalův trojúhelník). učinil významný krok ve vývoji infinitezimální analýzy, hrál důležitá role v počátcích teorie pravděpodobnosti. V hydrostatice Pascal stanovil svůj základní zákon (Pascalův zákon). Pascalovy „Dopisy provinciálovi“ byly mistrovským dílem francouzské klasické prózy.
Gottfried Wilhelm Leibniz (1646–1716) byl německý filozof, matematik, fyzik a vynálezce, právník, historik a lingvista. V matematice spolu s I. Newtonem rozvinul diferenciální a integrální počet. Významně přispěl ke kombinatorice. Zejména jeho jméno je spojeno s problémy teorie čísel.
Gottfried Wilhelm Leibniz neměl příliš působivý vzhled, a proto působil dojmem spíše obyčejně vypadajícího člověka. Jednoho dne v Paříži zašel do knihkupectví v naději, že si koupí knihu od filozofa, kterého znal. Když se návštěvník zeptal na tuto knihu, knihkupec si ho prohlédl od hlavy až k patě a posměšně řekl: „Proč ji potřebujete? Opravdu jsi schopen číst takové knihy?" Než vědec stačil odpovědět, vstoupil do obchodu sám autor knihy se slovy: "Zdravím a respektuji Velkého Leibnize!" Prodejce nemohl pochopit, že se skutečně jedná o slavného Leibnize, jehož knihy byly mezi vědci velmi žádané.
V budoucnu budou hrát důležitou roli následující
Lemma. Nechte v sadě prvků a v sadě - prvky. Potom počet všech odlišných párů kde se bude rovnat .
Důkaz. S jedním prvkem z množiny totiž můžeme vytvořit takové různé dvojice a celkem v množině prvků.
Umístění, permutace, kombinace
Mějme sadu tří prvků. Jakými způsoby můžeme vybrat dva z těchto prvků? .
Definice. Uspořádání množiny různých prvků podle prvků jsou kombinace, které se skládají z daných prvků podle prvků > a liší se buď prvky samotnými, nebo pořadím prvků.
Počet všech uspořádání množiny prvků podle prvků se značí (z počátečního písmene francouzského slova „arrangement“, což znamená uspořádání), kde a .
Teorém. Počet umístění sady prvků prvky se rovná
Důkaz.Řekněme, že máme prvky. Nechť jsou možná umístění. Tato umístění vytvoříme postupně. Nejprve definujeme první prvek umístění. Z dané sady prvků jej lze vybrat různé způsoby. Po výběru prvního prvku stále existují způsoby, jak vybrat druhý prvek atd. Vzhledem k tomu, že každá taková volba dává nové umístění, lze všechny tyto volby vzájemně volně kombinovat. Proto máme:
Příklad. Kolika způsoby může být vlajka složena ze tří vodorovných pruhů různých barev, pokud existuje materiál v pěti barvách?
Řešení. Požadovaný počet třípásmových vlajek:
Definice. Permutace množiny prvků je uspořádání prvků v určitém pořadí.
Tedy všechny různé permutace množiny tří prvků jsou
Je uveden počet všech permutací prvků (z počátečního písmene francouzského slova „permutace“, což znamená „permutace“, „pohyb“). Proto se počet všech různých permutací vypočítá podle vzorce
Příklad. Kolika způsoby lze věže umístit šachovnice aby se netrefili?
Řešení. Požadovaný počet věží
A-priory!
Definice. Kombinace různých prvků podle prvků jsou kombinace, které se skládají z daných prvků po prvcích a liší se alespoň v jednom prvku (jinými slovy -prvkové podmnožiny dané množiny prvků).
Jak vidíte, v kombinacích se na rozdíl od umístění nebere v úvahu pořadí prvků. Je uveden počet všech kombinací prvků, prvků v každém z nich (z počátečního písmene francouzského slova „combinasion“, což znamená „kombinace“).
Čísla
Všechny kombinace ze sady dvou jsou .
Vlastnosti čísel (\sf C)_n^k
Ve skutečnosti každá podmnožina -prvků dané sady prvků odpovídá jedné a pouze jedné podmnožině prvků stejné sady.
Ve skutečnosti můžeme vybrat podmnožiny prvků následujícím způsobem: opravit jeden prvek; počet podmnožin -prvků obsahujících tento prvek je roven ; počet podmnožin -prvků neobsahujících tento prvek je roven .
Pascalův trojúhelník
V tomto trojúhelníku jsou extrémní čísla v každém řádku rovna 1 a každé neextrémní číslo se rovná součtu dvou čísel nad ním z předchozího řádku. Tento trojúhelník vám tedy umožňuje počítat čísla.
Teorém.
Důkaz. Uvažujme množinu prvků a vyřešme následující problém dvěma způsoby: kolik sekvencí lze vytvořit z prvků daného
sady, ve kterých se žádný prvek nevyskytuje dvakrát?
1 způsob. Vybereme první člen posloupnosti, pak druhý, třetí atd. člen
Metoda 2. Nejprve vybereme prvky z dané množiny a poté je uspořádáme v nějakém pořadí
Vynásobte čitatele a jmenovatele tohoto zlomku:
Příklad. Kolika způsoby můžete ve hře „Sportloto“ vybrat 5 čísel ze 36?
Požadovaný počet způsobů
Úkoly.
1.
Registrační značky automobilů se skládají ze 3 písmen ruské abecedy (33 písmen) a 4 číslic. Kolik různých registračních značek existuje?
2.
Na klavíru je 88 kláves. Kolika způsoby můžete vytvořit 6 zvuků za sebou?
3.
Kolik existuje šesticiferných čísel, která jsou dělitelná 5?
4.
Kolika způsoby lze umístit 7 různých mincí do tří kapes?
5.
Kolik pětimístných čísel můžete zadat desítkový zápis které číslo 5 se objeví alespoň jednou?
6.
Kolika způsoby lze usadit 20 lidí? kulatý stůl, přičemž metody jsou stejné, pokud je lze získat jedna od druhé pohybem v kruhu?
7.
Kolik existuje pěticiferných čísel, která jsou dělitelná 5 a neobsahují stejné číslice?
8.
Na kostkovaný papír se stranou buňky 1 cm je nakreslena kružnice o poloměru 100 cm, která neprochází vršky buněk a nedotýká se stran buněk. Kolik buněk může tento kruh protínat?
9.
Kolika způsoby lze čísla uspořádat za sebou tak, aby čísla sousedila a byla ve vzestupném pořadí?
10.
Kolik pěticiferných čísel lze vytvořit z číslic, pokud lze každou číslici použít pouze jednou?
11.
Ze slova ROT přeskupením písmen získáte tato slova: TOP, ORT, OTR, TRO, RTO. Říká se jim anagramy. Kolik anagramů dokážete vytvořit ze slova LOGARITHM?
12.
Zavolejme štěpení přirozené číslo, jeho reprezentace jako součet přirozených čísel. Zde jsou například všechny oddíly čísla:
Oddíly jsou považovány za odlišné, pokud se liší buď v počtu nebo v pořadí jejich termínů.
Kolik různých rozdělení čísla na členy existuje?
13.
Kolik trojciferných čísel existuje s nerostoucím pořadím číslic?
14.
Kolik čtyřciferných čísel existuje s nerostoucím pořadím číslic?
15.
Kolika způsoby lze posadit 17 lidí do řady tak, aby skončili vedle sebe?
16.
dívky a chlapci sedí náhodně v řadě sedadel. Kolika způsoby je lze posadit, aby vedle sebe neseděly dvě dívky?
17.
dívky a chlapci sedí náhodně v řadě sedadel. Kolika způsoby je lze posadit tak, aby všechny dívky seděly vedle sebe?
