Výpis shrnutí
Kombinatorika
Podtémata
Kombinatorika
Kombinatorika je obor matematiky, který se zabývá počítáním možností a uspořádáním prvků v různých situacích. Využívá se například k určení počtu různých kombinací při losování, sestavování týmů nebo určování pořadí.
- Kombinatorika: pojmy – základní pojmy a principy
- Základní kombinatorická pravidla – pravidlo součinu a součtu
- Permutace, kombinace, variace – různé způsoby uspořádání a výběru prvků, včetně jejich vzorců a příkladů
- Kombinační čísla – důkladnější procvičení klíčového pojmu v kombinatorice
- Výrazy s faktoriálem a kombinačními čísly – cílené procvičení výpočtů s faktoriály a kombinačními čísly, což je častý dílčí krok v kombinatorických výpočtech
Kombinatorika: pojmy
K základním pojmům kombinatoriky patří permutace, variace a kombinace. Permutace n prvků je uspořádání všech n prvků, přičemž záleží na pořadí. Variaci a kombinace jsou výběry k prvků z těchto n prvků. Při variaci nám na pořadí těchto prvků záleží, při kombinaci ne. V základních případech prvky neopakujeme, každý prvek použijeme nejvýše jednou. Pokud můžeme některé prvky použít vícekrát, mluvíme o permutacích, variacích a kombinacích s opakováním.
Při řešení kombinatorických úloh často hledáme počet možností výběru nebo uspořádání. K tomu používáme mimo jiné faktoriály a kombinační čísla.
- Faktoriál čísla n je součin všech celých kladných čísel od jedné do n. Značíme ho n! a platí tedy: n!=1 \cdot 2 \cdot 3 \cdot \ldots \cdot n. Faktoriál udává počet všech permutací n prvků. Speciálně 0!=1.
- Kombinační číslo udává počet kombinací, tj. způsobů, jak vybrat k prvků z n prvkové množiny. Pro n\geq k\geq 0 platí: \binom nk = \frac{n!}{k!(n−k)!}
Využití kombinačních čísel
- Zajímavým využitím kombinačních čísel je Pascalův trojúhelník. Binomické koeficienty se uspořádají do trojúhelníku (na obrázku vpravo jsou tyto koeficienty vyčísleny).
- Všimněte si, že každé vnitřní číslo je součtem dvou čísel nad ním.
- Pascalův trojúhelník se používá pro vyčíslení koeficientů výrazů (a+b)^n. Koeficienty jsou čísla na řádku n v tomto trojúhelníku.
Základní kombinatorická pravidla
Při řešení kombinatorických úloh často určujeme počet různých možností, jak něco vybrat nebo sestavit. K tomu nám pomáhají dvě základní pravidla – pravidlo součtu a pravidlo součinu.
Pravidlo součtu
- Pokud vybíráme jednu možnost z několika navzájem se vylučujících skupin.
- Počty možností sečteme.
Příklady použití pravidla součtu
- V automatu jsou 3 druhy džusů a 4 druhy limonád. Vybíráme jeden nápoj, buďto nějaký džus, nebo nějakou limonádu, nemůže to být oboje zároveň. Máme 3+4=7 možností.
- Babička má 2 traktory a 3 elektrokola (předpokládáme, že žádný traktor není elektrokolem a ani žádné elektrokolo se nedá považovat za traktor). Vybírá si jeden dopravní prostředek. Má tedy podle pravidla součtu 2+3=5 možností.
Pravidlo součinu
- Pokud výběr probíhá v několika krocích a kombinujeme možnosti z jednotlivých skupin.
- Počty možností vynásobíme.
Příklady použití pravidla součinu
- Například máme 3 trička a 4 kalhoty. Ke každému tričku můžeme vybrat kterékoli kalhoty, a proto máme 3\cdot4=12 různých outfitů.
- V obchodě mají 6 druhů mobilů a 7 druhů obalů na mobily (předpokládejme, že každý obal pasuje na každý mobil). Máme 6 možností výběru mobilu a pro každý mobil máme 7 možností výběru obalu. Podle pravidla součinu máme celkem 6 \cdot 7 = 42 možností, jak vybrat jeden mobil s obalem.
Permutace, kombinace, variace
Pojmy
- Permutace je uspořádání prvků do fixního pořadí.
- Kombinace (k prvková) je výběr k prvků ze zadané množiny.
- Kombinace s opakováním (k prvková) je výběr k prvků ze zadané množiny, přičemž prvky se mohou opakovat.
- Variace (k prvková) je uspořádaný výběr k prvků ze zadané množiny.
- Variace s opakováním (k prvková) je uspořádaný výběr k prvků ze zadané množiny, přičemž prvky se mohou opakovat.
Příklady
| permutace | \{A, B, C\} | ABC, ACB, BAC, BCA, CAB, CBA |
| kombinace | \{A, B, C, D\}; k=2 | AB, AC, AD, BC, BD, CD |
| kombinace s opakováním | \{A, B, C, D\}; k=2 | AA, AB, AC, AD, BB, BC, BD, CC, CD, DD |
| variace | \{A, B, C, D\}; k=2 | AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC |
| variace s opakováním | \{A, B, C\}; k=2 | AA, AB, AC, BA, BB, BC, CA, CB, CC |
Vzorce
Počty permutací, kombinací a variací udává následující tabulka:
| počet všech permutací n prvků | n! |
| počet všech k prvkových kombinací z n prvků | \binom{n}{k} = \frac{n!}{(n-k)!k!} |
| počet všech k prvkových kombinací s opakováním z n prvků | \binom{n + k - 1}{k} |
| počet všech k prvkových variací z n prvků | \frac{n!}{(n-k)!} |
| počet všech k prvkových variací s opakováním z n prvků | n^k |
Komiks pro zpestření
Kombinační čísla
Kombinační číslo udává počet kombinací, tj. způsobů, jak vybrat k prvků z n prvkové množiny. Kombinační čísla se vyskytují velmi často v kombinatorických výpočtech, a proto mají speciální značení \binom{n}{k} (čteme „n nad k“).
Pro n \geq k \geq 0 platí: \binom{n}{k} = \frac{n!}{k!(n-k)!}
Pro kombinační čísla platí řada dalších vztahů, například:
- \binom{n}{k} = \binom{n}{n-k}
- \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}
- \sum_{k=0}^n \binom{n}{k} = 2^n
Příklady:
| \binom{3}{1} | = 3 |
| \binom{4}{2} | = 6 |
| \binom{5}{3} | = 10 |
| \binom{6}{2} | = 15 |
| \binom{15}{15} | = 1 |
Výrazy s faktoriálem a kombinačními čísly
Pojem faktoriál používáme nejčastěji při řešení kombinatorických úloh. Faktoriál čísla n je součin všech celých kladných čísel od jedné do n. Platí tedy: n!=1 \cdot 2 \cdot 3 \cdot \ldots \cdot n
Speciálně: 0!=1
Častou úpravou výrazů s faktoriály je částečný rozklad faktoriálu na součin několika hodnot a faktoriál menšího čísla.
Příklad – úprava výrazu \dfrac{(x+1)!}{(x-1)!}
- Faktoriál v čitateli rozložíme tak, aby obsahoval faktoriál ze jmenovatele: \dfrac{(x+1)!}{(x-1)!}=\dfrac{(x+1)x(x-1)!}{(x-1)!}
- Výraz s faktoriálem můžeme vykrátit a dostaneme: (x+1)x=x^2+x
Faktoriál také používáme pro definici kombinačního čísla. Pro n\geq k\geq 0 platí: \dbinom nk=\dfrac{n!}{k!(n−k)!}
Při úpravách výrazů s kombinačními čísly můžeme kromě faktoriálů použít některý z následujících vztahů:
- Je n možností, jak vybrat jeden z n prvků: \dbinom n1=n
- Je jedna možnost, jak vybrat 0 z n prvků, a také je jedna možnost, jak vybrat všech n z n prvků (pro n=0 to jsou dokonce stejná kombinační čísla): \dbinom nn=\dbinom n0=1 \dbinom 00=1
- Máme stejný počet možností, jak vybrat skupinku k prvků z n prvků, jako je počet možností, jak vybrat n-k prvků, které do skupinky nezařadíme: \dbinom nk=\dbinom n{n-k}
- Vybíráme-li k prvků z n+1, máme tolik možností, jako když sečteme počet možností výběru k a k-1 prvků z n prvků: \dbinom {n+1}k=\dbinom nk+\dbinom n{k-1}
Zdůvodnění vztahu \dbinom {n+1}k=\dbinom nk+\dbinom n{k-1}
Uvažme n prvků, ke kterým přidáme ještě (n+1). prvek (označme ho X), takže celkem máme n+1 prvků. Vybíráme k prvků z našich n+1 prvků. Kolik máme možností? (Aneb čemu se rovná \dbinom {n+1}k?)
- Takové výběry se dají rozdělit do dvou skupin, podle toho, jestli je
nebo není vybrán prvek X.
- Máme \dbinom nk možností, jak vybrat k prvků z původních n prvků, mezi kterými není X.
- Dále máme \dbinom n{k-1} možností, jak vybrat k-1 prvků z původních n prvků, mezi kterými není X, a přidat k nim do výběru X.
- Celkem tedy podle pravidla součtu platí: \dbinom {n+1}k=\dbinom nk+\dbinom n{k-1}
Příklad – úprava výrazu \dbinom {r+1}r
- Binomické číslo rozložíme na podíl faktoriálů: \dbinom {r+1}r=\dfrac{(r+1)!}{r!((r+1)-r)!}
- Upravíme: \dfrac{(r+1)!}{r!(r+1-r)!}=\dfrac{(r+1)!}{r!1!}
- Víme, že 1!=1. Faktoriál v čitateli dále rozložíme: \dfrac{(r+1)!}{r!1!}=\dfrac{(r+1)r!}{r!\cdot1}
- Nakonec vykrátíme výraz s faktoriálem: \dfrac{(r+1)r!}{r!}=r+1
Příklad – úprava výrazu \dbinom l4+\dbinom l5
- Použijeme vztah pro úpravu dvou binomických čísel: \dbinom {n+1}k=\dbinom nk+\dbinom n{k-1}
- Pro n=l a k=5 dostaneme: \dbinom l4+\dbinom l5=\dbinom {l+1}5
