Tento článek se zaměří na speciální sekci matematiky zvanou kombinatorika. Vzorce, pravidla, příklady řešení problémů - to vše zde najdete, když si článek dočtete až do konce.
Co je tedy tato sekce? Kombinatorika se zabývá problematikou počítání libovolných předmětů. Objekty ale v tomto případě 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 soupeř má trumf? Nebo takový příklad – jaká je pravděpodobnost, že z pytlíku s dvaceti míčky dostanete právě bílou? Právě pro tento druh úloh potřebujeme znát alespoň základy této části matematiky.
Kombinatorní konfigurace
S ohledem na problematiku základních pojmů a vzorců kombinatoriky nezbývá, než věnovat pozornost kombinatorickým konfiguracím. Používají se nejen k formulaci, ale také k řešení různých kombinatorických problémů. Příklady takových modelů jsou:
- placement;
- permutace;
- kombinace;
- složení čísel;
- rozdělené číslo.
O prvních třech si povíme podrobněji později, ale v této části se budeme věnovat složení a dělení. Když mluví o složení určitého čísla (řekněme a), myslí tím zobrazení čísla a jako uspořádaného součtu nějakých kladných čísel. A rozdělení je neuspořádaná částka.
Sekce
Než přejdeme přímo ke vzorcům kombinatoriky a zvažování problémů, stojí za to věnovat pozornost skutečnosti, že kombinatorika, stejně jako jiné sekce matematiky, má své vlastní podsekce. Patří mezi ně:
- enumerative;
- structural;
- extreme;
- Ramseyho teorie;
- probabilistic;
- topological;
- nekonečno.
V prvním případě mluvíme o enumerativní kombinatorice, problémy se týkají enumerace 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í pravidla sčítání nebo násobení, o kterém 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á množina má určitou 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 přidání
Mezi formulemi kombinatoriky lze najít i docela jednoduché, které známe již dlouhou dobu. 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 způsoby b, 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 celou pointu 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ů. Denně je do třídy přidělen jeden účastník. Kolika způsoby je dnes možné přiřadit účastníka kurzu? Řešení problému je celkem jednoduché, uchýlíme se k pravidlu sčítání. Text úkolu neříká, že službu mohou mí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, se kterým si snadno poradí i žák základní školy: 15 + 10. Po výpočtu dostáváme odpověď: dvacet pět. To znamená, že existuje pouze dvacet pět způsobůpřidělte na dnešek služební třídu.
Pravidlo násobení
K základním vzorcům kombinatoriky patří také pravidlo násobení. Začněme teorií. Předpokládejme, že potřebujeme provést několik akcí (a): první akce je provedena 1 způsoby, druhá - 2 způsoby, třetí - 3 způsoby a tak dále, dokud není poslední a-akce provedena sa způsoby. Pak lze všechny tyto akce (kterých máme celkem) provést N způsoby. Jak vypočítat neznámé N? Vzorec nám s tím pomůže: N \u003d c1c2c3…ca.
Opět není nic teoreticky jasné, přejděme k jednoduchému příkladu použití pravidla násobení. Vezměme si stejnou třídu pětadvaceti lidí, ve které studuje patnáct dívek a deset chlapců. Tentokrát si musíme vybrat dva operátory. Mohou to být buď pouze chlapci nebo dívky, nebo chlapec s dívkou. Přejdeme k elementárnímu řešení problému. Vybereme prvního obsluhujícího, jak jsme rozhodli v posledním odstavci, dostaneme 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 si jednoho, to znamená, že druhý ve službě může být kdokoli ze zbývajících čtyřiadvaceti lidí. Nakonec použijeme pravidlo násobení a zjistíme, že dva operátory lze vybrat šesti sty způsoby. Toto číslo jsme získali vynásobením dvaceti pěti a dvaceti čtyřmi.
Vyměnit
Nyní se podíváme na ještě jeden kombinatorický vzorec. V této části článku jsmePojďme se bavit o permutacích. Okamžitě zvažte problém pomocí příkladu. Vezměme kulečníkové koule, máme jich n-tý počet. Potřebujeme spočítat: kolik možností je uspořádat je za sebou, tedy vytvořit uspořádanou sadu.
Začněme, pokud nemáme koule, máme také nulové možnosti umístění. A pokud máme jednu kouli, pak je uspořádání také stejné (matematicky to lze zapsat takto: Р1=1). Dvě kuličky mohou být uspořádány dvěma různými způsoby: 1, 2 a 2, 1. Proto Р2=2. Tři kuličky mohou být uspořádány šesti způsoby (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. A když takových koulí nejsou tři, ale deset nebo patnáct? Vyjmenovat všechny možné možnosti je velmi dlouhé, pak nám přichází na pomoc kombinatorika. Permutační vzorec nám pomůže najít odpověď na naši otázku. Pn=nP(n-1). Pokusíme-li se vzorec zjednodušit, dostaneme: Pn=n (n - 1) … 21. A to je součin prvních přirozených čísel. Takové číslo se nazývá faktoriál a označuje se jako n!
Zvažme problém. Vůdce každé ráno staví svůj oddíl v řadě (dvacet lidí). V oddělení jsou tři nejlepší přátelé - Kostya, Sasha a Lesha. Jaká je pravděpodobnost, že budou 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. Potom jsmeMá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 jsou ještě 3!=6 možností. Takže máme celkem 18 „dobrých“konstelací! 3! Musíme jen najít požadovanou pravděpodobnost: (18!3!) / 20! Což je přibližně 0,016. Pokud převedete na procento, vyjde to pouze na 1,6 %.
Ubytování
Nyní se podíváme na další velmi důležitý a nezbytný kombinatorický vzorec. Ubytování je naším dalším tématem, které doporučujeme zvážit v této části článku. Budeme to mít složitější. Předpokládejme, že chceme uvažovat možné permutace, pouze ne z celé množiny (n), ale z menší (m). To znamená, že uvažujeme permutace n položek pomocí m.
Základní vzorce kombinatoriky by se neměly jen naučit nazpaměť, ale také jim porozumět. I přesto, že se stávají složitějšími, protože nemáme jeden parametr, ale dva. Předpokládejme, že m \u003d 1, potom A \u003d 1, m \u003d 2 a potom A \u003d n(n - 1). Pokud vzorec dále zjednodušíme a přejdeme na zápis pomocí faktoriálů, dostaneme celkem výstižný vzorec: A \u003d n! / (n - m)!
Kombinace
Zvážili jsme téměř všechny základní vzorce kombinatoriky s příklady. Nyní přejděme k závěrečné fázi zvažování základního kurzu kombinatoriky – seznámení se s kombinací. Nyní vybereme m položek z n, které máme, přičemž je vybereme všechny všemi možnými způsoby. Jak se to tedy liší od ubytování? Nebudemezvážit pořádek. Tato neuspořádaná sada bude kombinací.
Okamžitě zaveďte zápis: C. Z n vezmeme umístění m kuliček. Přestáváme dbát na pořádek a dostáváme opakující se kombinace. Abychom získali počet kombinací, musíme počet umístění vydělit m! (m faktoriál). To znamená, C \u003d A / m! Existuje tedy několik způsobů, jak si vybrat z n kuliček, přibližně stejně jako kolik vybrat téměř vše. Existuje na to logické vyjádření: vybrat si málo je totéž, jako vyhodit téměř vše. 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 usnadnit výběr potřebného vzorce pro řešení problému v kombinatorice. Můžete použít následující poměrně jednoduché schéma:
- Zeptejte se sami sebe: je v textu problému zohledněno pořadí prvků?
- Pokud je odpověď ne, použijte kombinační vzorec (C=n! / (m!(n - m)!)).
- Pokud je odpověď ne, musíte odpovědět ještě na jednu 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 alokační vzorec (A=n! / (n - m)!).
Příklad
Zvážili jsme prvky kombinatoriky, vzorce a některé další otázky. Nyní přejděme ks ohledem na skutečný problém. Představte si, že máte před sebou kiwi, pomeranč a banán.
Otázka jedna: Kolika způsoby je lze přeskupit? K tomu použijeme permutační vzorec: P=3!=6 způsobů.
Otázka druhá: kolika způsoby lze vybrat jedno ovoce? To je zřejmé, máme pouze tři možnosti - vyberte si kiwi, pomeranč nebo banán, ale použijeme kombinovaný vzorec: C \u003d 3! / (2!1!)=3.
Otázka třetí: Kolika způsoby lze vybrat dva druhy ovoce? Jaké máme možnosti? Kiwi a pomeranč; kiwi a banán; pomeranč a banán. To znamená tři možnosti, ale to lze snadno zkontrolovat pomocí kombinačního vzorce: C \u003d 3! / (1!2!)=3
Otázka čtvrtá: Kolika způsoby lze vybrat tři druhy ovoce? Jak vidíte, existuje jen jeden způsob, jak si vybrat tři druhy ovoce: vzít 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ň jeden kousek ovoce ze stolu.
