9.1.15
Další vlastnosti kombinačních čísel
Předpoklady: 9107, 9108 Kombinační čísla udávají počet kombinací bez opakování = neuspořádaných k-tic sestavených z n prvků bez opakování. n n! - počet možností jak vybrat z n prvků k bez ohledu na pořadí (jde jen Platí: = k k !⋅ ( n − k ) ! o to, které prvky jsme vybrali a nezáleží na tom, v jakém pořadí jsme výběr provedli)
Př. 1:
n Urči dosazením hodnoty kombinačních čísel: , 0 kombinatoricky zdůvodni.
n , 1
n . Své výsledky n
n n! n! = =1 0 = 0!⋅ ( n − 0 ) ! 1!⋅ n ! n Kolika způsoby můžeme z n prvků vybrat žádný? Jedním , nevybereme nic. 0 n ( n − 1) ! n n! = =n 1 = 1!⋅ ( n − 1) ! 1!⋅ ( n − 1) ! n Kolika způsoby můžeme z n prvků vybrat jeden? Kterýkoliv n prvků si můžeme nechat 1 ⇒ n možností
n n! n! = =1 n = n !⋅ ( n − n ) ! n !⋅ 0! n Kolika způsoby můžeme z n prvků vybrat všech n? Jedním, vybereme všechny. n Další pravidlo už známe. n n Platí: = . k n−k Kombinatorické zdůvodnění je snadné: Když vybíráme k prvků do kombinace zbude v množině n − k prvků, které tvoří také kombinaci, ale n − k -člennou ⇒ k-prvkových kombinací z n prvků bez opakování je stejně jako n − k prvkových (vznikají společně). Poslední kombinatorické pravidlo je nejsložitější:
n n n + 1 Pro všechna celá nezáporná čísla n, k, k < n , platí: + = . k k + 1 k + 1
1
Důkaz předchozí věty je snadný například na tomto konkrétním příkladě: 4B2007 má n = 29 studentů a n + 1 -ního matikáře Krynického. Kolika způsoby je možné z množiny 4B2007+Krynický vybrat k + 1 = 10 lidí? Vytváříme kombinace desetičlenné kombinace bez opakování z 30 prvků ⇒ celkem 30 n + 1 = možností 10 k + 1 Vytvořené kombinace můžeme rozdělit do dvou skupin: 29 n • kombinace bez Krynického: je jich = (vybíráme 10 lidí ze 29 studentů 10 k + 1 4B2007) 29 n • kombinace bez Krynického: je jich = (vybíráme 9 lidí ze 29 studentů 9 k 4B2007 a přidáváme k nim Krynického) 30 29 29 Vypsané dvě skupiny tvoří dohromady všech kombinace ⇒ platí: = + a tedy 10 10 9
n n n + 1 + = . k k + 1 k + 1
Př. 2:
n n n + 1 (BONUS) Dokaž vztah + = dosazením do definice kombinačního k k + 1 k + 1 čísla.
n n n! n! + = + = k k + 1 k !⋅ ( n − k ) ! ( k + 1) !⋅ ( n − [ k + 1]) ! n! n! = + = k !⋅ ( n − k )( n − k − 1) ! ( k + 1) ⋅ k !⋅ ( n − k − 1) ! =
1 n! 1 n! k +1+ n − k + ⋅ = = k !⋅ ( n − k − 1) ! n − k k + 1 k !⋅ ( n − k − 1) ! ( n − k )( k + 1)
=
( n + 1) n ! n! n +1 ⋅ = = k !⋅ ( n − k − 1) ! ( n − k )( k + 1) ( k + 1) k !⋅ ( n − k )( n − k − 1) !
=
( n + 1)! = n + 1 ( k + 1)!⋅ ( n − k )! k + 1
Všechny předchozí vzorce se používají při úpravách výrazů, které obsahují kombinační čísla:
Př. 3:
Vyjádři jedním kombinačním číslem: 20 20 a) + 9 10
2
15 15 b) + 9 5 5 6 7 8 9 c) + + + + 5 5 5 5 5 20 20 a) + 9 10 n n n + 1 20 20 21 použijeme vzorec + = : + = k k + 1 k + 1 9 10 10 15 15 b) + 9 5 n n n + 1 15 na vzorec: + = nemáme správná kombinační čísla, místo bychom k k + 1 k + 1 5 15 n n 15 15 potřebovali , naštěstí platí vztah = a tedy = ⇒ 10 k n−k 5 10 15 15 15 15 16 + = + = 9 5 9 10 10 5 6 7 8 9 c) + + + + 5 5 5 5 5 n n n + 1 na vzorec: + = nemáme na začátku výrazu správná kombinační čísla, místo k k + 1 k + 1 5 6 n 5 6 bychom potřebovali , naštěstí platí vztah = 1 a tedy = 1 = ⇒ 5 6 n 5 6 5 6 7 8 9 6 6 7 8 9 5 + 5 + 5 + 5 + 5 = 6 + 5 + 5 + 5 + 5 =
7 7 8 9 8 8 9 9 9 10 = + + + = + + = + = 6 5 5 5 6 5 5 6 5 6 Díky vzorcům, které pro kombinační čísla platí, můžeme sestavovat zajímavé obrazce
3
Př. 4:
Opiš následující obrazec a vedle něj ho zapiš ještě jednou s tím, že místo kombinačních čísel zapíšeš jejich hodnoty. 0 0 1 0 2 0 3 0
1 1 2 1
3 1
2 2 3 2
3 3
0 0 1 0 2 0
1 1
1
2 1
3 0
3 1
Př. 5:
1
2 2 3 2
1 1
1 2
3
1 3
1
3 3
Dopiš do pravého trojúhelníku s hodnotami kombinačních čísel další řádku. Svůj výsledek zkontroluj dopsáním další řádky do trojúhelníku s kombinačními čísly.
0 0 1 0
1 1 1 1 1
1 2
3 4
3 6
2 0
1 1 4
3 0
1
4 0
1 1 2 1
3 1 4 1
2 2 3 2
4 2
3 3 4 3
4 4
Obrazci, který jsme sestavovali se říká Pascalův trojúhleník (podle známého fyzika a matematika B. Pascala). Protože je celý sestavený z kombinačních čísel, dají se na něm demonstrovat vztahy, které pro ně platí.
4
Př. 6:
Demonstruj na Pascalově trojúhelníku platnost vztahů pro kombinační čísla: n n n n n + 1 a) = b) + = k n−k k k + 1 k + 1
n n a) = ⇒ Pascalův trojúhelník je souměrný podle svislé osy (kombinační čísla k n−k stejné nečerné barvy mají stejnou hodnotu) 0 0
1 0
1 1 1 1 1
1 2
3 4
2 0
1 3
6
1 4
3 0
1
4 0
1 1 2 1
3 1 4 1
2 2 3 2
4 2
3 3 4 3
4 4
n n n + 1 b) + = ⇒ kombinační čísla, která nejsou na bočních stranách trojúhelníka k k + 1 k + 1 získáme jako součet kombinačních čísel nad nimi 0 0
1 0
1 1 + 1 1 1 1
2
3 + 1
3 4
2 0
1
6
4
3 0
1
4 0
+ 2 1
3 1 4 1
1 1 2 2 3 2
4 2
+ 4 3
3 3 4 4
Vzorce, které jsme probrali v první části hodiny, se mohou hodit při řešení některých rovnic nebo nerovnic.
Pedagogická poznámka: Rovnice s kombinačními čísly jsou zařazeny až na konec hodiny, protože nejsou důležité z hlediska další probírané látky a tak není nutné, aby je stihli vypočítat všichni.
5
Př. 7:
x x x + 2 Vyřeš rovnici 11 + 11 = 7 . 5 6 7
Problém: Při řešení předchozích rovnic s kombinačními čísli jsme kombinační čísla rozepisovali do tvaru, který umožňoval řešení klasickými metodami ⇒ při použití v tomto případě hrozí velké mocniny x. ⇒ zkusíme dostat rovnici do tvaru ( ) = ( ) :
x x x + 2 11 + = 7 7 5 6 x + 1 x + 2 11 = 7 přepíšeme kombinační čísla na faktoriály 6 7
( x + 1)! = 7 ( x + 2 )! 6!⋅ ( x + 1 − 6 ) ! 7!⋅ ( x + 2 − 7 ) ! ( x + 1)! = 7 ( x + 2 )( x + 1)! 11 6!⋅ ( x − 5 ) ! 7 ⋅ 6!⋅ ( x − 5 ) ! 11
11 = x + 2 x=9
Př. 8:
Napiš sedmý řádek Pascalova trojúhelníka.
Sedmý řádek je sestavený z kombinačních čísel, která mají nahoře šestku ⇒ 6 6 6 6 6 6 6 0 1 2 3 4 5 6 po dosazení: 1 6 15 20 15 6 1
Př. 9:
x x x + 1 Vyřeš rovnici + = . x − 2 x − 3 3
Stejný postup jako v předchozím příkladu: x x x + 1 + = x − 2 x − 3 3 x + 1 x + 1 n n x + 1 x + 1 = , použijeme vzorec = ⇒ = x − 2 3 k n−k x − 2 3 x + 1 x + 1 = ⇒ tato rovnost platí vždy pokud je kombinační číslo definováno 3 3 x−3≥ 0 ⇒ x ≥ 3 K = { x ∈ N ; x ≥ 3}
6
Př. 10: Petáková: strana 143/cvičení 22 b) c) d) f) strana 143/cvičení 23 a) b) c) d) strana 143/cvičení 24 a) b)
Shrnutí: Vlastnosti kombinačních čísel je možné snadno odvodit z Pascalova trojúhelníka.
7
