Diskrétní matematika - cvičení 10. týden
Lukáš Vokřínek
Masarykova univerzita Fakulta informatiky
jaro 2020
Pripomeňme si vzoreček pro kombinační číslo:
fk\_       k\        _ k'{k-l)--{k-n + l) \n) ~ n\> (k- n)\ ~        n • (n - 1) • • • 1 '
Poslední z těchto výrazů dává smysl i pro k reálné (r? musí být přirozené - jedná se o počet činitelů). Určete, čemu se rovná (~/c).
Príklad
Připomeňme si vzoreček pro kombinační číslo:
k\
n
n\ • (k- n)\
k-(k-l)---(k- n + 1) n • (r? — 1) • • • 1
Poslední z těchto výrazů dává smysl i pro k reálné (r? musí být přirozené - jedná se o počet činitelů). Určete, čemu se rovná (~^)
Řešení
n
(-k) • (-k - 1) • • • (-k - n + 2) • (-k - n + 1)
n ■ (n — 1)•••2 • 1 „   {k +n-l)-(k +n-2)---{k + l)-k
= (-1)
r? • (r? — 1) • • • 2 • 1
Príklad
Připomeňme si vzoreček pro kombinační číslo:
k\
n
n\ • (k- n)\
k-(k-l)---(k- n + 1) n • (r? — 1) • • • 1
Poslední z těchto výrazů dává smysl i pro k reálné (r? musí být přirozené - jedná se o počet činitelů). Určete, čemu se rovná (~^)
Řešení
-k n
(-k) • (-k - 1) • • • (-k - n + 2) • (-k - n + 1)
n ■ (n — 1)•••2 • 1 „   {k +n-l)-(k +n-2)---{k + l)-k
= (-1)
r? • (r? — 1) • • • 2 • 1
Príklad
Určete, čemu se rovná ( ľJ2)
Príklad
Určete, čemu se rovná ( ľJ2)
Řešení
1/2 n
(-l/2).(-3/2)...(-(2n-l)/2)
= (-1/2)"
= (-1/2)" = (-1/4)"
n ■ (n — 1) • • • 1 l-3---(2n- 1)
(2")'
2-4-(2n) = (_1/2)"
n!
(2n)! = (-1/4)" •
n\ ■ n\
(2n)\ 2"-n\
n\
2ri
n
Poznámka
Základem pro nás bude vztah mezi posloupnostmi
tzv. (formálními) mocninnými řadami
oo
^ 3n • Xn = 3p + 3i • X + 32 ' X2 +
n=0
(jedná se jen o jiný zápis posloupnosti) a jim příslušnými generujícími funkcemi f(x) - součet mocninné řady. Např.
oo   1 1 oo
n=0 n=0
tedy ex je generující funkcí posloupnosti (gy, j,, ...) a je generující funkcí posloupnosti (1,1,1,...).
Poznámka
Zobecněná binomická věta: pro libovolné reálné k platí
oo
n=0
n
Pojďme toto reinterpretovat s využitím (   ) = (—l)n • ('k_x )
oo
E
n=0
/c- 1
x
n
Pro /c = 1 jsou všechna kombinační čísla rovna 1 a dostaneme vzorec pro součet geometrické řady jako speciální případ.
V dalším se nám bude ještě krom součtu nekonečné geometrické řady
oo ^
Vx" = l+x + x2 + -- - =--
^ 1-X
n=0
hodit také vzorec pro součet konečné geometrické řady
k 1 _ xk+l
Exn = 1 + x + x2 H-----hxk =-. 1-x
n=0
Příklad
Kolika způsoby můžeme pomocí českých mincí zaplatit platbu N = 100, resp. jiné hodnoty?
Kolika způsoby můžeme pomocí českých mincí zaplatit platbu N = 100, resp. jiné hodnoty?
■v
Řešení
Jedná se o příklad téměř totožný s posledním z minulého týdne. Výsledkem je koeficient u x100 ve výrazu
(1 + x + x2 + • • • )(1 + x2 + x4 + • • • )(1 + x5 + x10 + • • •) • • •
1 1 1 1 1 1
" 1-x ' 1-x2 ' 1-x5 ' 1-x10 ' 1-x20 ' 1-x50
V tomto případě výsledek nezjednodušíme, nicméně systémy počítačové algebry, např. sage volně dostupný na cocalc.com, jsou schopny tento koeficient snadno spočítat:
var('x' )
f = l/(l-x)*l/(l-x^2)*l/(l-x^5)*l/(l-x^l0)*l/(l-x^20)*l/(l-x^50)
r = taylor(f, x, 0, 100)
r.coefficients(sparse = false)[100]
da vysledek 4562.
Príklad
Určete kolika způsoby je možné naplnit tašku n kusy uvedených druhů ovoce, přičemž jednotlivé kusy téhož druhu nerozlišujeme, nemusí být využity všechny druhy a navíc:
• jablek může být libovolný počet,
• banánů musí být sudý počet,
• hrušek musí být násobek 4,
• pomeranče mohou být nejvýše 3 a
• pomelo může být pouze jedno (nebo žádné).
Príklad
Určete kolika způsoby je možné naplnit tašku n kusy uvedených druhů ovoce, přičemž jednotlivé kusy téhož druhu nerozlišujeme, nemusí být využity všechny druhy a navíc:
• jablek může být libovolný počet,
• banánů musí být sudý počet,
• hrušek musí být násobek 4,
• pomeranče mohou být nejvýše 3 a
• pomelo může být pouze jedno (nebo žádné).
Řešení	
Tady již příklad dopočítáme do konce v	ruce. Jedná se o koeficient
u x" ve výrazu	
(1 + x + x2 + • • • )(1 + x2 + x4 + •	• • )(1 + x4 + x8 + • • •)
• (1 + x + x2 +x3)(l + x)	
Tady již příklad dopočítáme do konce v ruce. Jedná se o koeficient u x" ve výrazu
(1 + x + x2 + • • • )(1 + x2 + x4 + • • • )(1 + x4 + x8 + • • •) • (1 + x + x2 +x3)(l + x)
1 1 1 l-x4l-x2
1-x   1-x2   1-x4    1-x 1-x
OO
, / n -\- y\
.n
(1-x)3 ~ ^ I 2
V J        n=0 V
X
Hledaný počet tedy je (n^2)
Rozviňte do mocninných řad racionální funkce
x x2 + x + 1
x + 2'    2x3 - 3x2 + ľ
Príklad
Rozviňte do mocninných řad racionální funkce
x
x2 + x + 1
x + 2'    2x3 - 3x2 + ľ
Rešení
Základem je rozklad na parciální zlomky, v prvním případě je to triviální:
x =1 + ^ = 1 +
-i
oo
2 + x
2 + x
OO
1 - (-x/2)
OO
1 - £(-*/2)n
A7=0
1 - V2)n •     = = 0] " (-V2)") •
n=0
n=0
kde [r? = 0] značí hodnotu tohoto logického výrazu, tj.: pro n = 0 je hodnota 1, jinak je hodnota 0.
Rozviňte do mocninných řad racionální funkce
x x2 + x + 1
x + 2'    2x3 - 3x2 + 1'
Príklad
Rozviňte do mocninných řad racionální funkce
x
x2 + x + 1
x + 2'    2x3 - 3x2 + ľ
Rešení
Podobně pro druhý zlomek:
x2 + x + 1 2x3 - 3x2 + 1
C
x2 + x + 1 (x-l)2(2x + l)
4 B x - 1 + (x - l)2 + 2x + 1
4(x - l)(2x + 1) + e(2x + 1) + C(x
(x-l)2(2x+l)
>0 0,0
Podobně pro druhý zlomek:
X2 +X+1     _        X2 +X+1
2x3 - 3x2 + 1 = (x- l)2(2x + l)
A B C
~ x - 1 + (x - l)2 + 2x + 1
_ A{x - l)(2x + 1) + g(2x + 1) + C(x - l)2
(x-l)2(2x+l)
dostáváme tedy pro neznámé koeficienty rovnici
A(x - l)(2x + 1) + e(2x + 1) + C(x - l)2 = x2 + x + 1,
Řešení
dostáváme tedy pro neznámé koeficienty rovnici
A(x - l)(2x + 1) + B(2x + 1) + C(x - l)2 = x2 + x + 1,
kterou buď řešíme roznásobením a porovnáním koeficientů nebo vhodným dosazováním: vždy se hodí dosadit kořeny jmenovatele, tj. 1 a —1/2, jako třetí hodnotu dosadíme libovolné číslo:
x = 1: 6 ■ 3 = 3    =>•    B = l
9 3
x= -1/2: C - - = -1 4 4
x = 0:/\-(-l) + e + C = l
3
(také by šlo rovnici zderivovat a dosadit x = 1, což by dalo A • 3 + B • 2 = 3). Vypočtené konstanty dosadíme do rozkladu
Vypočtené konstanty dosadíme do rozkladu
xz+x+l        1/3 1 1/3
H---h
2x3 - 3x2 + 1     x - 1    (x - l)2    2x + 1
-1/3 1 1/3
l-x    (1-x)2 l-(-2x) -V3-£*" + Eft 1)x" + l/3.X;(-2x)«'
oo
£(-1/3 + (n + 1) + 1/3 • (-2)") • x".
n=0
Určete vytvořující funkce posloupností
9	(i,	2, 3, 4, 5,...)				
9	(i>	4,9,16,25,..				
9	(i,	1 2 2 4 4 8	8,.	••).		
9	(9,	0,0,2-16,0,	0,4	•25,	0,0,	8-36,...)
9	(9,	1,-9,32,1,-	-32,	100,	1,-	100,.. .)■
Určete vytvořující funkce posloupností
9 9 9 9 9
(1 2 3 4 5 )
(1,4,9,16,25,...), (1,1,2,2,4,4,8,8,...),
(9,0,0, 2 • 16,0,0,4 • 25,0,0,8 • 36,...),
(9,1, -9,32,1, -32,100,1, -100,...).
Řešení
V prvním případě hledáme součet
Bn+1)-*" = £C,T1>|-X',= 1
(l-x)
Určete vytvořující funkce posloupností
•	(i,	2, 3, 4, 5,...)				
O	(i,	4,9,16,25,..				
9	(i,	1 2 2 4 4 8	8,.	••).		
9	(9,	0,0,2-16,0,	0,4	•25,	0,0,	8-36,...)
O	(9,	1,-9,32,1,-	-32,	100,	1,-	100,.. .)■
■v
Řešení
V druhém případě hledáme součet XX n + 1) ' x"' přičemž:
Řešení
V druhém případě hledáme součet XX n + -O2 ' x"' P^cemž se pokusíme vyjádřit (podobně jako v rozkldu na parciální zlomky)
,       -     .   fn + 2\     _   fn + l\     _   /n + 0
Podle zobecněné binomické věty pak totiž můžeme XX n + l)2 ' x" spočítat jako
n+ 2'
x
"+e E("íV" + c-E
n + 0' 0
x
n
= A-
(1-x)
+ B
(1-x):
+ C-
1-x
Zbývá najít neznáme koeficienty A, B, C, rozepišme proto kombinační čísla:
Řešení
(n + l)2 = A
n2 + 2n + 1 = A
= 2 ■
n2 + 3n + 2
n2 + 3n + 2
+ B-(n + l) + C -l-(n + l) + 0
Hledané koeficienty jsou tedy A = 2, B = — 1, C = 0 a nakonec
^(n + l)2-x" = 2
(l-x)3 (1-x)
2 '
Určete vytvořující funkce posloupností
9
(1 2 3 4 5 )
(1,4,9,16,25,...),
(1,1,2,2,4,4,8,8,...)-
(9,0,0, 2 • 16,0,0,4 • 25,0,0,8 • 36,...),
(9,1, -9,32,1, -32,100,1, -100,...).
Řešení
Ve třetím případě rozdělme posloupnost na součet dvou posloupností: (1, 0, 2, 0,4, 0, 8, 0,...) + (0,1, 0, 2, 0,4, 0,8,.. každou dostaneme snadno formulku, hledáme proto součet ^2"-x2n + E2"-x2"+1.
.). Pro
Ve třetím případě hledáme součet ^ 2n • x2n + ^ 2n • x2n+1. Úpravou získáme
2" • x2n +     2" • x2n+1 = J](2x2)" + x • J](2x2)"
1 1
" 1 - 2x2 + X ' 1 - 2x2
-   1 + x " 1 - 2x2'
Zkuste tuto řadu sečíst pomocí rozkladu na parciální zlomky a porovnejte výsledek se zadáním.
Určete vytvořující funkce posloupností
•	(i,	2, 3, 4, 5,...)				
9	(i,	4,9,16,25,..				
9	(i,	1 2 2 4 4 8	8,.	••).		
9	(9,	0,0,2-16,0,	0,4	•25,	0,0,	8-36,...)
9	(9,	1,-9,32,1,-	-32,	100,	1,-	100,.. .)■
■v
Řešení
Ve čtvrtém případě hledáme součet ^ 2n • (r? + 3)2 • x
Řešení
2 ,3n
Ve čtvrtém případě hledáme součet     2" • (n + 3) • x
2" • (n + 3)2 • x3" = J](n + 3)2 • (2x3)".
Opět vyjádříme (n + 3)  pomocí kombinačních čísel
(n + 3)2 = A
n2 + 6n + 9 = A
= 2 ■
2     + M   1 l+C'
n2 + 3n + 2
n + 0' 0
n2 + 3n + 2
+ e-(n + l) + C + 3-(n + l) + 4
Hledané koeficienty jsou tedy A = 2, 6 = 3, C = 4 a nakonec B» + 3f • (2x3)» = 2. _!       + 3. _J_ + 4. _í_
V) o
V krabici je 30 červených, 40 modrých a 50 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 70 míčků?
Příklad
V krabici je 30 červených, 40 modrých a 50 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 70 míčků?
Řešení
Jedná se o koeficient u x70 v
(1 + x + • • • + x30)(l + x + • • • + x4U)(l + x +
_ 1 _ x31    ! _ x41    l_ x51
1—x      1 — x      1 — X _ (l-x31)(l-x41)(l-x51)
_ 1 - x31 - x41 - x51 + x72 + • • •
(1-X)3
.40
+ x50)
Podle zobecněné binomické věty pak
1 _ x31 _ x41 _ x51 + x72 + . .
(1-X>
n+ 2
= (l_x31_x41_x51+x72 + ...).
x"
Koeficient u x70 dostaneme vynásobením prvních čtyř členů v závorce odpovídajícími členy v druhé sumě - tak, aby exponent vyšel 70:
Príklad
Jaká je pravděpodobnost, že při hodu 12 hracími kostkami padne součet 30?
Príklad
Jaká je pravděpodobnost, že při hodu 12 hracími kostkami padne součet 30?
Rešení
Počet všech možných hodů je samozřejmě 612, počet příznivých hodů je roven koeficientu u x30 v
(x + x2+x3+x4+x5+x6)12
•7\12 i 12/1      ,.6\12 1
X — X 1 — X
= xiZ(l -x°)
(1-x)
12
a tedy koeficientu u x18 v (1 — xb)12 • ^xy2. tj
6M2
12 0
12i 6 , 1 -x +
12
12 X —
12.   18 ,
3 'X +
n=0
L-ľ
>0 Q,o
a tedy koeficientu u x18 v (1 — x6)12 • ^xy2. tj
oo
n=0
Výsledná pravděpodobnost je tak rovna
(?) O - (i) O + (2) (n) - C3) (n)
612
= 0,8815%.
K výsledku lze dojít také principem inkluze a exkluze a příkladu z minule.