Nové symboly pro čísla V kapitole Intuitivní kombinatorika jsme řešili tyto dva typy příkladů. Stále se v nich opakují součiny přirozených čísel, tak jak jdou za sebou, někdy až do 1, někdy skončí dříve. Proto si zavedeme dva nové symboly pro čísla. 1. typ: 11 sportovců se má postavit do zástupu. Kolika způsoby se to může provést? Řešení o o o o o o o o o o o 11.10.9.8. 7. 6. 5. 4. 3. 2. 1 = 39916800 možností Budeme to zkracovat na symbol 11! (za číslicí je !) a znamená součin až do jedné včetně. Takže
n! = n(n-1)(n-2)…2.1
2. typ: Z 11 sportovců se má vybrat 5, kteří budou družstvo reprezentovat ve štafetě. Kolika způsoby lze vybrat tuto pětici? Řešení o o o o o 11.10. 9. 8. 7 = 55440 možností ALE nám nezáleží na pořadí: stále půjde o tutéž skupinu reprezentantů, ať je vybereme jako ABCDE nebo ACEDB či CADAE a tak dále. 5 reprezentantů představuje 5.4.3.2.1 = 120 různých uspořádání tedy z 11 sportovců můžeme vybrat různých pětic reprezentantů celkem 55440/120 = 462
11.10.9.8.7 11.10.9.8.7 5.4.3.2.1 5! Zatím je výsledek 11.10.9.8.7.6.5.4.3.2.1 11! 5!.6.5.4.3.2.1 5!.6!
11 5
Tyto symboly si nyní nadefinujeme přesně a seznámíme se s jejich základními vlastnostmi. Oba jsou v oboru kombinatoriky potřebné a užitečné.
Definice faktoriálu: Číslo n! se nazývá n-faktoriál a je definováno pro každé n N0 rekurentně: (n+1)! = (n+1) . n! (užitečné, nemusíme vypisovat součiny třeba od 1000.999…) 0! = 1 (to aby nám vycházeli různé vzorce) Poznámka: 0! = 1, 1! = 1, 2! = 2.1 = 2, 3! = 3.2.1 = 6, 4! = 4.3.2.1 = 24, …
Příklad 1: Dokažte mat. indukcí, že n N: n! = n.(n-1).(n-2)….3.2.1 (že jde o součin přirozených čísel od n sestupně až do 1 je důležité nezapomenout)
1) a = 1 L1=1!=(podle rek. definice)=1.0!=P1 1 P 2) IP k 1 k! = k(k-1)(k-2)…2.1 MD (k+1)! = (k+1)k(k-1)…2.1 vlastní důkaz 2. kroku vedeme z levé strany na pravou Lk+1 = (k+1)! =(podle rek. definice)= (k+1).k! =(podle IP)= (k+1)k(k-1)(k-2)…2.1 = Pk+1 (k+1) P q.e.d.
Příklad 2: Dokažte úpravami 1. n! + n2 (n-1)! = (n+1)! 2. (n+1)! – n.n! = n! 3. n[n! + (n-1)!] + n2 (n-1)! + (n+1)! = (3n+2) n! Řešení: ad 1 L = n! + n2 (n-1)! = n! + n.n.(n-1)! = n! + n. n! = (n+1) n! = (n+1)! = P ad 2 L = (n+1)! – n.n! = (n+1)n! – n.n! = n.n! + n! - n.n! = n! = P ad 3 L = n[n! + (n-1)!] + n2 (n-1)! + (n+1)! = n.n! + n.(n-1)! + n.n.(n-1)! + (n+1).n! = = n.n! + n! + n.n! + n.n! + n! = (3n+2) n! = P
Příklad 3: Dokažte mat. indukcí, že n
n N :n 1
x . x! ( n 1)! 1 x 1
Řešení: l) a=1
L1 = 1.1! = 1 = 2 – 1 = 2! – 1
1 P
n
2) IP
k 1
x . x! = (k+1)! – 1 = Pk
Lk = x 1 n 1
MD
x . x! = (k+2)! – 1 = Pk+1
Lk+1 = x 1 n 1
n
x . x! + (k+1)(k+1)! = (použijeme IP a dále jen úpravy) =
x . x! =
Lk+1 = x 1
x 1
= (k+1)! – 1 + (k+1)(k+1)! = (1 + k+1)(k+1)! – 1 = = (k+2)(k+1)! – 1 = (k+2)! – 1 = Pk+1 (k+1) P q.e.d.
Definice kombinačních čísel:
n se nazývá kombinační číslo, čte se „en nad ká“, je definováno k n n! 0 k n k! ( n k )! k
Číslo
pro k,n N0 :
k
n
n
0
k
Příklad 4: Dokažte z definice
n 0
n n
n k
n n k
n k
1,
n 1
n n 1
krajní hodnoty
n
symetrie tvar pro „ruční“ výpočet v čitateli je stejný počet činitelů jako jich je ve jmenovateli
n.( n 1)( n 2)....( n k 1) k ( k 1)( k 2)...2.1
n 1 k
n k
n k 1
pro k
vlastnost pro „výrobu“ Pascalova trojúhelníku
1
Řešení velmi jednoduché. Zde dokážeme jen poslední vztah. Jde jen o jednoduchou úpravu výrazů.
P
n
n
k
k 1
n! k! ( n k )!
n! ( n k 1) k! ( n k )!( n k 1) n! n n! k n! n! k k! ( n k 1)!
n! ( k 1)!( n k 1)!
n! k k ( k 1)! ( n k 1)!
n! ( n 1) k! ( n k 1)!
n 1 k
L
Pascalův trojúhelník: Seřaďme kombinační čísla do trojúhelníku; právě dokázaná poslední vlastnost se
v trojúhelníku projevuje takto: 0
1
0 1
1
0
1
2
2
0
1
1 2
1
2
3
3
3
3
0
1
2
3
4
4
4
4
0
1
2
3
1 2
1 4
1
4
5
5
5
5
5
5
0
1
2
3
4
5
6
6
6
6
6
6
0
1
2
3
4
5
1
6
7
7
7
7
7
7
7
7
0
1
2
3
4
5
6
7
1
3
4
1 6
3 6
5 6
10
21
1 4
10
15
7
1
20 35
1 5
15 35
1 6
21
1 7
Porovnejte známé vzorečky s Pascalovým trojúhelníkem (a + b)2 = a2 + 2ab + b2 (a + b)3 = a3 + 3a2b + 3ab2 + b3 (a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4
0 0 1
1
0
1
2 0 3 0 4 0
2 1 3 1
4 1
1
3 2 4 2
1
2 2
1
4 3
2
1
3 3
1
1 1
3 4
3 6
4 4
Binomická věta Jsou-li a,b R reálná čísla a n N0 přirozené číslo nebo nula, pak platí:
1 4
1
1
n nk k a b k
n
(a b)n
k 0
n
Ak
n
Ak k 0
an k bk
k
Ak se nazývá k+1 člen binomického rozvoje.
Poznámka – speciální případy: n
(1 x ) n
a=1, b=x
k 0
(a b)n
n
( a ( b))n
k 0
n k x k
n nk a ( b)k k
n
( 1) k
k 0
n nk k a b k
Příklad 5: Vypočítejte užitím binomické věty 1,023 . Řešení:
1,023
(1 0,02) 3
3 k 0
3 0,02k k
1 3.0,02 3.0,022
0,023
= 1 + 0,06 + 0,0012 + 0,000008 = 1,061208
Příklad 6: Vypočtěte s přesností na 5 desetinných míst 1,037 , 1,0210 , 0,989 Řešení: 1,037 = (1 + 0,03)7 = 1 + 7.0,03 + 21.0,0009 + 35.0,000027 + 35.0,00000081 … = = 1 + 0,21 + 0,0189 + 0,000945 + 0,00002835 = 1,22987 10 1,02 = 1,21899 0,989 = (1 – 0,02)9 = 1 – 9.0,02 + 36.0,0004 – 84.0,000008 + 126.0,00000016 …= = 0,83375
Příklad 7: Dokažte, že platí n k 0
Řešení: 2n = (1 + 1)n = …
n k
2n
n
,
( 1) k
k 0
0 = (1 – 1)n = …
n k
0
Příklad 8: Který člen binomického rozvoje
Řešení: k+1 člen
3x
1 x
2
10
obsahuje x8 a který x vůbec neobsahuje?
10 ( 3 x 2 ) k ( 1) k x k
Ak
k
konst. x 20
2k k
konst. x 8
20 – 3k = 8 k=4 5-tý člen 20 – 3k = 0 k = 20/3 není přirozené všechny členy rozvoje obsahují x, žádný člen rozvoje není pouze číslo
Příklad 9: Dokažte, že výraz (1 – x)5 + x5 – 1 je dělitelný 10 pro všechna x C. Řešení: (1 – x)5 + x5 – 1 = 1 – 5x + 10x2 – 10x3 + 5x4 – x5 + x5 – 1 = = 5(x4 – 2x3 + 2x2 +x) = = 5x(x3 – 2x2 + 2x +1) = = 5x(x – 1)(x2 – x + 1) x(x – 1) je vždy dělitelné 2 => původní výraz je dělitelný 10
Příklad 10: Vypočítejte:
6 3
6 4
7 a 1 5
n 1
n k
n k 1
Řešení: Použijeme vlastnost
n 1 2
n 2 3
n 3 . 4
n 1 je to jen jinak napsaná dokázaná k 1
vlastnost. viz výše.
6 3
6 4
7 5
7 4
7 5
8 5
8 3
8.7.6 3.2.1
56 n
U druhého výrazu si nejprve šikovně přepíšeme počáteční 1 = ( 0)
n
n 1
n 2
n 3
n
n
n 1
n 2
n 3
1
2
3
4
0
1
2
3
4
n 1 1
n 1 2
n 2 3
n 3 4
n 2 3
n 3 4
n 3
n 3
n 4
1
3
4
4
n 2 2
Příklad 11:
x 1 x 2
Řešte rovnici
x 2 x 4
4
Řešení: Použijeme symetrii kombinačních čísel a rozepíšeme je na zlomky
x 1
x 2
x 2
x 4
x 1
x 2
1
2
4
získané kořeny poslední kvadratické rovnice musíme ověřit zkouškou
4
x = -1 nevyhovuje, protože v kombinačních číslech smí být pouze nezáporná čísla
( x 2)( x 3) 4 x=4 2 .1 2x 2 x2 5x 6 8 L 2 x 3x 4 0
( x 1)
( x 4 )( x 1) 0 x1
4
x2
3 2
2 0
3.2 1 3 1 4 2.1
P
Zkouška pro x = 4 prověřila, že je to kořen původní rovnice.
1
Příklad 12: Řešte rovnice
7 x
7 5
a
5 x
5 x 1
6 4
Řešení: Nehledejte v tom nějaké zázraky, jde jen o to si uvědomit jak se kombinační čísla tvoří a jejich základní vlastnosti. Také se můžete inspirovat Pascalovým trojúhelníkem pro n=7 viz výše.
7 x
7 5
7 => pouhým porovnáním dostáváme dvě řešení: x1 = 2, x2 = 5 2
U druhé rovnice nejprve použijeme vzorec pro součet kombinačních čísel
5 x
5 x 1
6 4
6 x 1
6 4
Příklad 13: Řešte v N rovnici Řešení:
3
x 1 2
3
x 2
2.4!
6 2
x1
3, x2
1
( x 1)( x 2) x ( x 1) 3 2.4.3.2 2.1 2.1 ( x 1)( x 2) x ( x 1) 32 3
2x2
krát 2, delit 3
4 x 30 0
x 2 2 x 15 0 ( x 3)( x 5) 0
x1
3,
x2
5
x1 = -3 nevyhovuje původní rovnici, nejde o nezáporné číslo x2 = 5 vyžaduje zkoušku
L 3
4 2
KONEC
3
5 2
3.6 3.10 48 P
2.4! 2.24 48 L
P
