Základní vzorce kombinátorů. Kombinatorika: vzorec pro permutaci, umístění

V tomto článku budeme diskutovat o speciální části matematiky nazvané kombinátora. Vzorce, pravidla, příklady řešení problémů - to vše najdete zde, po přečtení článku až do konce.

Takže, co je tento oddíl? Kombinatorika se zabývá otázkou počítání všech objektů. Ale v tomto případě nejsou objekty švestky, hrušky nebo jablka, ale něco jiného. Combinatorics nám pomáhá najít pravděpodobnost události. Například při hraní karet - jaká je pravděpodobnost, že soupeř má trumfovou kartu? Nebo příklad - jaká je pravděpodobnost, že dostanete bílou tašku z tašky s dvaceti kuličkami? Je to pro takové problémy, které potřebujeme znát alespoň základy této sekce matematiky.

Kombinatorické konfigurace

Vzhledem k otázce základních pojmů a vzorců kombinátorů nemůžeme věnovat pozornost kombinatorickým konfiguracím. Používají se nejen pro formulaci, ale také pro řešení různých kombinatorické problémy. Příklady takových modelů jsou:

• ubytování;
• permutace;
• kombinace;
• složení čísla;
• rozdělení čísla.

O prvních třech se budeme bavit podrobněji později, ale věnujeme pozornost kompozicím a rozdělení v této sekci. Když hovoříme o složení určitého počtu (řekněme a), máme na mysli reprezentaci čísla a ve formě uspořádaného součtu určitých pozitivních čísel. Rozdělení je neuspořádaná částka.

Sekce

Předtím, než půjdeme přímo do kombinatorických vzorců a do úvahy problémů, stojí za to věnovat pozornost tomu, že kombinatorika, stejně jako ostatní matematické obory, má své vlastní podkapitoly. Patří sem:

• enumerative;
• strukturální;
• extrémní;
• Ramseyova teorie;
• pravděpodobnostní;
• topologické;
• Infinational.

V prvním případě mluvíme o výpočtu kombinatoriky, problémy považují výčet nebo počítání různých konfigurací, které jsou tvořeny prvky sady. Obecně platí, že na tyto sady jsou uložena všechna omezení (rozlišitelnost, nerozlišitelnost, možnost opakování atd.). A počet těchto konfigurací se vypočítá pomocí pravidla přidání nebo násobení, o kterém budeme mluvit o něco později. Teorie grafů a matroidů jsou strukturální kombinatorika. Příkladem tohoto problému extrémních kombinatoriky - Jaká je největší rozměr grafu, který splňuje následující svoystvamhellip- Ve čtvrtém odstavci jsme se zmínili o teorii Ramsay, který studuje v přítomnosti náhodných konfiguracích pravidelných struktur. Pravděpodobná kombinatorika je schopna odpovědět na otázku - jaká je pravděpodobnost, že daná sada má určitou vlastnost. Není obtížné odhadnout, že topologická kombinatorika aplikuje metody v topologii. A konečně, sedmý bod - nekonečná kombinatorika kombinatorika studuje použití metod nekonečných množin.

Pravidlo přidávání

Mezi kombinatorickými pojmy najdeme poměrně jednoduché, s nimiž jsme již dlouho obeznámeni. Příkladem je pravidlo součtu. Předpokládejme, že jsou uvedeny ve dvou krocích (C a E), v případě, že se vzájemně vylučují, v platnosti od uskutečnitelný několika způsoby (například), a účinek E uskutečnitelný b-způsoby, aby byly v souladu s některou z nich (C nebo E), mohou být A + B způsoby .

Teoreticky je toto obtížné pochopit, pokoušíme se přenést celý bod na jednoduchý příklad. Vezměme si průměrný počet žáků jedné třídy - řekněme, pětadvacet. Mezi nimi je patnáct dívek a deset chlapců. Každý den ve třídě je přiřazena jedna osoba ve službě. Kolik způsobů je dnes jmenovat úředníka? Řešení problému je poměrně jednoduché, uchýlíme se k dodatečnému pravidlu. Text problému neříká, že pouze chlapci nebo dívky mohou být ve službě. V důsledku toho mohou být někteří z patnácti dívek nebo někdo z deseti chlapců. Aplikujeme-li pravidlo součtu, dostáváme poměrně jednoduchý příklad, s nímž může student základní školy snadno zvládnout: 15 + 10. Po počítání dostaneme odpověď: pětadvacet. To znamená, že pro dnešek je k dispozici pouze dvacet pět způsobů, jak stanovit třídu povinností.

Pravidlo násobení

Pravidlo násobení platí pro základní vzorce kombinatoriky. Začněme teorií. Například potřebujeme provést několik akcí (a): první akce se provádí 1 cestou, druhá v c2, třetí s c3 metodami a tak dále až do poslední akce provedené stejným způsobem. Pak všechny tyto činy (z nichž všichni máme) lze provádět N cestami. Jak vypočítat neznámé N? V tom budeme pomáhat vzorcem: N = c1 * c2 * c3 * hellip- * sa.

Opět teoreticky není jasné, že se obracíme na jednoduchý příklad použití pravidla násobení. Vezměme stejnou třídu pětadvaceti lidí, ve kterých studuje patnáct dívek a deset chlapců. Teprve tentokrát musíme vybrat dva lidi v práci. Mohou to být jakmile budou chlapci nebo dívky a chlapec s dívkou. Pokračujeme k základnímu řešení problému. Vybrali jsme si první osobu ve službě, jak jsme se rozhodli v posledním odstavci, získáme dvacet pět možných možností. Druhou osobu ve službě může být někdo z ostatních lidí. Měli jsme pětadvacet studentů, ten, který jsme si vybrali, takže druhá osoba by mohla být zbylých dvacet čtyři lidí. Konečně platí pravidlo násobení a zjistíme, že dva lidé ve službě mohou být voleni v šesti stovkách způsobů. Tento počet jsme vynásobili pětadvacet a dvacet čtyři.

Změna uspořádání

Teď budeme zvažovat ještě jeden kombinatorický vzorec. V této části článku budeme hovořit o permutacích. Okamžitě zvažte problém s příkladem. Vezměte si kulečníkové koule, které mají jejich n-té číslo. Potřebujeme vypočítat, kolik voleb máme k uspořádání v řadě, tj. K sestavení objednané sady.

Začněme, pokud nemáme koule, pak máme stejné varianty uspořádání jako nula. A pokud máme jednu kouli, pak je uspořádání stejné (matematicky to může být napsáno následovně: P1 = 1). Dvě koule lze umístit dvěma různými způsoby: 1,2 a 2,1. V důsledku toho P2 = 2. Tři koule 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. A jestli nejsou tři takové kuličky, ale deset nebo patnáct? Vyčistěte všechny možné možnosti po velmi dlouhou dobu, pak přijdeme k záchranným kombinátorům. Permutační vzorec nám pomůže nalézt odpověď na otázku, která nás zajímá. Pn = n * P (n-1). Pokud se pokusíme zjednodušit vzorec, dostaneme: Pn = n * (n-1) * hellip- * 2 * 1. A je to produkt prvních přirozených čísel. Toto číslo se nazývá faktoriální a označuje se jako n!

Zvažte problém. Leader každé ráno staví svůj tým v řadě (dvacet lidí). Oddělení má tři nejlepší kamarády - Kostyu, Sasu a Leshu. Jaká je pravděpodobnost, že budou stát vedle sebe? Abychom našli odpověď na otázku, měla by být pravděpodobnost "dobrého" výsledku rozdělena na celkový počet výsledků. Celkový počet permutací je 20! = 2,5 quintilion. Jak vypočítat počet "dobrých" výsledků? Předpokládejme, že Kostya, Sasha a Lesha jsou supermani. Pak máme jen osmnáct předmětů. Počet permutací v tomto případě je 18 = 6,5 kvadrillionů. Se všemi těmi se Kostya, Sasha a Lesha mohou libovolně pohybovat mezi sebou ve svých nedělitelných třech a to je 3! = 6 možností. Takže máme jen 18 "dobrých" uspořádání! * 3! Můžeme najít požadovanou pravděpodobnost: (18! * 3!) / 20! Co se rovná přibližně 0.016. Převedete-li na procento, pak se ukáže pouze 1,6%.

Ubytování

Nyní budeme zvažovat další velmi důležitý a nezbytný vzorec kombinatoriky. Umístění je další otázkou, kterou navrhujeme v této části článku. Budeme komplikovat věci. Předpokládejme, že chceme uvažovat o možných permutacích, ale ne z celé sady (n), ale od menší (m). To znamená, že považujeme permutace n objektů v m.

Základní vzorce kombinátorů nejsou pouze učení, ale pochopení. Dokonce i přes to, že jsou komplikované, protože nemáme žádný parametr, ale dva. Předpokládejme, že m = 1, pak A = 1, m = 2, pak A = n * (n - 1). Pokud dále zjednodušíme vzorec a půjdeme k záznamu pomocí faktoriálů, získáme úplně stručný vzorec: A = n! / (n-m)!

Kombinace

Vezmeme v úvahu téměř všechny základní kombinatorické vzorce s příklady. Nyní se dostaneme do závěrečné fáze posuzování základního kurzu kombinatoriky - seznámení s kombinací. Nyní budeme volit m položky z našich existujících n, zatímco vše vybereme všemi možnými prostředky. Co se tedy od umístění liší? Nepokládáme objednávku. Tato neuspořádaná množina bude kombinací.

Okamžitě uvedeme notaci: C. Postavíme m-kuličky n. Přestáváme věnovat pozornost objednávce a získávat opakované kombinace. Abychom získali počet kombinací, musíme rozdělit počet umístění o m! (m faktorial). To znamená, že C = A / m! Takže způsoby, jak si vybrat z n koulí trochu, je asi stejně jako volba téměř všeho. To je logický výraz: zvolit si trochu stejně, že vyhazovat téměř všechno. I v tomto odstavci je důležité zmínit, že maximální počet kombinací lze dosáhnout při výběru poloviny položek.

Jak zvolit vzorec pro řešení problému?

Podrobně jsme zkoumali 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í kombinatorického problému. Můžeme použít následující poměrně jednoduchou schéma:

1. Zeptejte se sami sebe na otázku: pořadí umístění prvků je zohledněno v textu úkolu?
2. Pokud je odpověď ne, použijte kombinovaný vzorec (C = n! / (M! * (N - m)!)).
3. Pokud není odpověď, je třeba odpovědět na jednu další otázku: jsou všechny prvky obsažené v kombinaci?
4. Pokud je odpověď ano, použijte vzorec permutace (P = n!).
5. Pokud odpověď není, použijte vzorec umístění (A = n! / (N - m)!).

Příklad:

Zkoumali jsme prvky kombinatoriky, vzorce a některé další otázky. Teď se zaměříme na skutečný problém. Představte si, že před vámi položíte kiwi, pomeranč a banán.

První otázka: kolik způsobů může být změněno? K tomu použijeme vzorec permutace: P = 3! = 6 cest.

Druhá otázka: Kolik způsobů mohu vybrat jedno ovoce? To je zřejmé, máme jen tři možnosti - vybrat si kiwi, pomeranč nebo banán, ale použijte vzorec kombinací: C = 3! / (2! * 1!) = 3.

Třetí otázka: kolik způsobů si můžete vybrat ze dvou druhů ovoce? Jaké možnosti máme obecně? Kiwi a oranžové kiwi a banán-pomeranč a banán. To znamená tři možnosti, ale je snadné ověřit pomocí vzorce kombinace: C = 3! / (1! * 2!) = 3

Otázka č. 4: Kolik způsobů můžete vybrat ze tří druhů ovoce? Zřejmě můžete vybrat tři druhy ovoce jedním způsobem: vezměte kiwi, pomeranč a banán. C = 3! / (0! * 3!) = 1.

Otázka pátá: kolik způsobů mohu vybrat alespoň jedno ovoce? Tento stav znamená, že můžeme vzít jedno, dvě nebo všechny tři ovoce. Přidáme proto C1 + C2 + C3 = 3 + 3 + 1 = 7. To znamená, že máme sedm způsobů, jak ze stolu odebrat alespoň jedno ovoce.