Domácí úkol z kombinatoriky, 7. prosince 2023
Přestože tento domácí úkol nebudete odevzdávat, měli byste si jej ve vlastním zájmu sepsat. Nezapomeňte vždy zapsat i úvahu, kterou jste k výsledku došli, způsobem, kterým byste svůj postup vysvětlili spolužákovi.
Vzorové řešení zadaných úloh bude uveřejněno v interaktivní osnově 10. prosince 2023, abyste si svůj domácí úkol mohli sami opravit.
1. Ve čtvercové síti je povoleno jít dolů, doprava a diagonálně vpravo dolů (viz náčrtek). Označme an, kde nGZ,ii>0, počet cest z daného startovního bodu do cílového bodu, který je o dvě délky strany čtverce níže a o n délek strany čtverce vpravo (náčrtek popisuje situaci pro n = 9).
Nalezněte rekurentní vztah pro výpočet členů posloupnosti {an}^Lo pomocí předchozích členů. Vypočtěte 013.
2. Rekurentní posloupnost {&n}^Lo Je dána svými počátečními hodnotami &o = 1, bi = 5, a rekurentním vztahem bn+i = Abn — 76n_i platným pro každé přirozené číslo n. Nalezněte explicitní vyjádření členu bn této posloupnosti, tj. vyjádření, ve kterém nebudou vystupovat jiné členy této posloupnosti (jedinou proměnnou bude n).
3. Kolik anagramů můžeme vytvořit ze slova ABCDE? Určete, kolik z těchto anagramů splňuje, že každé jejich písmeno stojí na jiném místě než stálo v původním slově (tj. dotyčný anagram nezačíná písmenem A, nemá na druhém místě písmeno B, nemá na třetím místě písmeno C, nemá na čtvrtém místě písmeno D, ani nekončí písmenem E).
Vzorové řešení
1. Ze startovního bodu musíme vyjít jedním ze tří způsobů.
Vyjdeme-li vpravo, dostaneme se do bodu, odkud můžeme pokračovat právě an_i různými cestami.
Vyjdeme-li dolů, dostaneme se do bodu, ze kterého je cílový bod vzdálen o jednu délky strany čtverce níže a o n délek strany čtverce vpravo. Při pokračování cesty musíme tedy právě jednou jít buď dolů anebo jít diagonálně vpravo dolů, všechny ostatní kroky už budou vpravo. Šipek dolů je n + 1, šipek vpravo dolů je n. Protože každá z těchto cest je jednoznačně určena tím, kterou z těchto 2n + 1 šipek použijeme, je počet cest, kterými můžeme pokračovat, roven 2n + 1.
Vyjdeme-li diagonálně vpravo dolů, dostaneme se do bodu, ze kterého je cílový bod vzdálen o jednu délky strany čtverce níže a o n — 1 délek strany čtverce vpravo. Podobně jako v předchozím případě odvodíme, že počet cest, kterými můžeme pokračovat, je roven 2n — 1.
Z tohoto rozboru plyne rekurentní vztah an = an_\ + An. Je zřejmé, že a0 = 1.
Užitím rekurentního vztahu postupně dostaneme
	= a0 4	-A-	1 =	5,
a2	= ai -i	-A-	2 =	13,
a3	= a2 -i	-A-	3 =	25,
	= a3 4	-A-	4 =	41,
a5	= aA-\	-A-	5 =	61,
a6	= a5 4	-A-	6 =	85,
ďj	= a6 -i	-A-	7 =	113,
a8	= a7 -i	-A-	8 =	145,
Clg	= a8 -i	-A-	9 =	181,
a10	= a9 -i	-A-	10 =	= 221,
an	= dio	+ 4	• 11	= 265
0.12	= an	+ 4	• 12	= 313
«13	= ai2	+ 4	• 13	= 365
Hledané a±s = 365.
Poznámka: Z rekurentního vztahu lze v tomto případě snadno získat explicitní vyjádření postupným dosazováním
an = An + 4(n - 1) + 4(n - 2) H-----h 8 + 4 + 1.
Sečtením členů aritmetické posloupnosti dostaneme
an = 2n{n + 1) + 1 = 2n2 + 2n + 1.
Proto je možné vypočítat hledané a 13 také dosazením do tohoto explicitního vyjádření: a13 = 2 • 13 • 14 + 1 = 365.
2. Protože jde o lineární rekurentní formuli druhého řádu s konstantními koeficienty, tvoří posloupnosti, které ji vyhovují, vektorový prostor dimenze 2. Charakteristický polynom je polynom, jehož kořeny jsou kvo-ficienty g / 0 geometrických posloupností vyhovujících této formuli. Protože podmínka qn+1 = Aqn — 7qn~ľ je splněna pro každé přirozené číslo n, právě když q2 = Aq — 7, je charakteristický polynom x2 — Ax + 7. Ten má jednoduché kořeny 2 + iy/Š, 2 — iy/Š. Proto je daná posloupnost lineární kombinací posloupností {(2 + i\ŕŠ)n}^L0 a {(2 — i\/3)n}™=0. Pro vhodná čísla u, v G C proto platí
bn = u ■ (2 + i\/~3)n + v ■ (2 — i\/3)n      pro každé n G Z, n > 0.
Čísla u, v dostaneme porovnáním hodnot počátečních členů
1 = b0 = u + v,
5 = bľ = u ■ (2 + iVŠ) + v ■ (2 - iVŠ).
Řešením této soustavy lineárních rovnic je u = v = Tím
jsme dostali explicitní vyjádření bn. Pro libovolné n G Z, n > 0 tedy platí
&n = 1^1 . (2 + n/3)n + ±±M . (2 -řV3)n.
3. Protože všechna písmena slova ABCDE jsou po dvou různá, má množina M všech anagramů vytvořených z tohoto slova právě 5! prvků. Označme Mi podmnožinu množiny M, jejímiž prvky jsou právě ty anagramy, které mají na i-tém místě stejné písmeno jako má slovo ABCDE. Pak sjednoceni \ji=1 M;t se sklada pravě z těch anagramu, které na alespoň jednom místě mají stejné písmeno jako slovo ABCDE. Podle zadání
y y o y I   |5 '
mame spočítat počet prvku rozdílu množin M - U=imí- Hledaný počet 5! — |Uí=i-^íI spočítáme pomocí principu inkluze a exkluze. Platí, že pro každé i je |Mj| = 4! (poloha i-tého písmene je předepsaná, zbylá čtyři písmena můžeme permutovat 4! způsoby). Podobně průnik libovolných dvou různých z těchto pěti množin má 3! prvků (poloha dvou písmen je předepsaná, zbylá tři písmena můžeme permutovat 3! způsoby), průnik libovolných tří různých z těchto pěti množin má 2!
prvků (poloha tří písmen je předepsaná, zbylá dvě písmena můžeme permutovat 2! způsoby). Konečně průnik libovolných čtyř z těchto pěti množin, podobně jako průnik všech pěti množin obsahuje jediné slovo (totiž ABCDE).
Princip inkluze a exkluze proto dává
Hledaný počet je
M-ÚM,|^!-5.4!+Q.3!-Q.2!+0-Q
= 10-3! - 10-21 + 5- 1 = 44.