Poznámky a řešení úloh z Diskrétní matematiky A3

Catalanova čísla

Definice.

C_{n} = p o \overset{ˇ}{c} e t z a k o \overset{ˇ}{r} e n \overset{ˇ}{e} n \overset{ˊ}{y} c h r o v i n n \overset{ˊ}{y} c h s t r o m \overset{˚}{u} o n v r c h o l e c h

1,1,2,5,14,42,132,132,429,1430

Příklad.

C_{4} = 5

Věta.

\forall n \geq 2, C_{n} = \sum_{k = 1}^{n - 1} C_{k} C_{n - k}

Důkaz. Každý strom s více než jedním vrcholem můžeme jednoznačně rozdělit na dva stromy tak, že odtrhneme první větev kořene.

Věta.

C_{n} = \frac{(\binom{2 n - 2}{n - 1})}{n}

Důkaz. Předpokládejme, že generující funkce

C (x) ≔ \sum_{n = 1}^{\infty} C_{n} x^{n}

absolutně konverguje.

\begin{aligned} C (x) & = \sum_{n = 1}^{\infty} C_{n} x^{n} \\ = C_{1} x + \sum_{n = 2}^{\infty} (\sum_{k = 1}^{n - 1} C_{k} C_{n - k}) x^{n} \\ = C_{1} x + \sum_{n = 2}^{\infty} \sum_{k = 1}^{n - 1} (C_{k} x^{k}) (C_{n - k} x^{n - k}) \\ = C_{1} x + (\sum_{n = 1}^{\infty} C_{n} x^{n}) (\sum_{n = 1}^{\infty} C_{n} x^{n}) \\ = x + C (x)^{2} \\ = \frac{1 - \sqrt{1 - 4 x}}{2} \\ = \dots \\ = \sum_{n = 1}^{\infty} \frac{(\binom{2 n - 2}{n - 1})}{n} \end{aligned}

Cvičení. Dokažte, že

C_{n}

je liché právě tehdy, když

n

je mocnina dvojky.

Definice. Dijckovo slovo je slovo na abecedě

{x, y}

takové, že v každém prefixu je počet

x

větší nebo roven počtu

y

a celkem je jich stejně. (Ekvivalentně, jde o dobře uzávorkovaný řetězec závorek.)

Věta. Počet Dijckových slov délky

2 n

C_{n + 1}

Důkaz. Nechť

2 k

je délka prvního prefixu, která má obou písmen stejně. Zřejmě tento prefix začíná na

x

a končí na

y

. Uvnitř téchto dvou písmen musí být Dijckovo slovo, a stejně tak za prefixem. Tímto způsobem se jim dají přiřadit stromy.

Věta. Počet neklesajících cest v mřížce

n \times n

, které nepřekročí diagonálu, je

C_{n + 1}

Důkaz. Každé cestě přiřadíme jednoznačné Dijckovo slovo tak, že posun doprava =

x

a posun dolů =

y

Věta. Počet způsobů, jak vyplnit tabulku

2 \times n

čísly

1, \dots, 2 n

tak, aby oba řádky i všechny sloupce byly rostoucí, je

C_{n + 1}

Důkaz. Vezměme Dijckovo slovo, za každé

x

píšeme další číslo do prvního řádku a za

y

do druhého řádku.

Věta (Eulerova). Počet triangulací konvexního

n

-úhelníku je

C_{n - 1}

Příklad.

C_{4 - 1} = C_{3} = 2

Důkaz. Vezměme libovolnou hranu a trojúhelník, jehož je součástí. To nám mnohoúhelník rozděluje na dva menší.

Věta.

\forall n \geq 2, C_{n + 1} = C_{n} \frac{4 n - 2}{n + 1}

Důkaz.

C (x) = \frac{1 - \sqrt{1 - 4 x}}{2} C^{'} (x) = \frac{1}{\sqrt{1 - 4 x}} C^{'} (x) (1 - 4 x) = \sqrt{1 - 4 x} = 1 - 2 C (x) ? ? ?

Lineární rekurence pomocí generujících funkcí

Příklad (Binetův vzorec pomocí generujících funkcí).

F_{n + 2} = F_{n + 1} + F_{n} F_{0} = 0, F_{1} = 1

f (x) ≔ \sum_{n = 0}^{\infty} F_{n} x^{n}

\sum_{n = 0}^{\infty} F_{n + 2} x^{n} = \sum_{n = 0}^{\infty} F_{n + 1} x^{n} + \sum_{n = 0}^{\infty} F_{n} x^{n}

\frac{1}{x^{2}} \sum_{n = 0}^{\infty} F_{n + 2} x^{n + 2} = \frac{1}{x} \sum_{n = 0}^{\infty} F_{n + 1} x^{n + 1} + \sum_{n = 0}^{\infty} F_{n} x^{n}

\frac{1}{x^{2}} \sum_{n = 2}^{\infty} F_{n} x^{n} = \frac{1}{x} \sum_{n = 1}^{\infty} F_{n} x^{n} + \sum_{n = 0}^{\infty} F_{n} x^{n}

\frac{f (x) - F_{1} x - F_{0}}{x^{2}} = \frac{f (x) - F_{0}}{x} + f (x)

\frac{f (x) - x}{x^{2}} = \frac{f (x)}{x} + f (x)

\begin{aligned} f (x) & = \frac{- x}{x^{2} + x - 1} \\ = \frac{- φ}{\sqrt{5} (x + φ)} + \frac{ϕ}{\sqrt{5} (x + ϕ)} \\ = \frac{1}{\sqrt{5} (1 - φ x)} - \frac{1}{\sqrt{5} (1 - ϕ x)} \\ = \frac{1}{\sqrt{5}} \sum_{n = 0}^{\infty} (φ^{n} - ϕ^{n}) x^{n} \end{aligned}

F_{n} = \frac{φ^{n} - ϕ^{n}}{\sqrt{5}}

Příklad (Fontána z mincí).

Definice. Bloková fontána z mincí vypadá tak, že dole je řádek z

n

mincí, na něm leží další souvislý řádek mincí (s posunutím o polovinu), apod.

b_{n} ≔ p o \overset{ˇ}{c} e t b l o k o v \overset{ˊ}{y} c h f o n t \overset{ˊ}{a} n s n m i n c e m i d o l e

b_{n} = 1 + \sum_{k = 1}^{n - 1} (n - k) b_{k}

\begin{aligned} b (x) & ≔ \sum_{n = 0}^{\infty} b_{n} x^{n} \\ = \sum_{n = 0}^{\infty} x^{n} + \sum_{n = 2}^{\infty} \sum_{k = 1}^{n - 1} (n - k) b_{k} x^{n} \\ = \frac{1}{1 - x} + (\sum_{n = 1}^{\infty} n x^{n}) (\sum_{n = 1}^{\infty} b_{n} x^{n}) \\ = \frac{1}{1 - x} + \frac{x}{{(1 - x)}^{2}} (b (x) - 1) \\ = \frac{1 - 2 x}{1 - 3 x + x^{2}} \\ ⋮ \\ = (1 - 2 x) \sum_{n = 0}^{\infty} \frac{φ^{2 n + 2} - ϕ^{2 n + 2}}{\sqrt{5}} x^{n} \end{aligned}

b_{n} = \dots = \frac{φ^{2 n - 1} - ϕ^{2 n - 1}}{\sqrt{5}} = F_{2 n - 1}

Cvičení. Řešte pomocí generujících funkcí:

a_{n} = a_{n - 1} + 2 a_{n - 2} + {(- 1)}^{n} a_{0} = a_{1} = 1

Řešení (klasickým způsobem).

a_{n} - a_{n - 1} - 2 a_{n - 2} = {(- 1)}^{n}

λ^{2} - λ - 2 = (λ - 2) (λ + 1)

a_{n}^{h} = α 2^{n} + β {(- 1)}^{n}

a_{n}^{p} = {(- 1)}^{n} n γ

⋮

a_{n} = \frac{7}{9} 2^{n} + (\frac{2}{9} + \frac{n}{3}) {(- 1)}^{n}

Řešení. Toto řešení bylo schováno, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a řešení vás zajímá, kontaktujte mě.

Věta. Mějme posloupnost

a_{n}

a její generující funkci

f (x)

. Potom

\frac{f (x) + f (- x)}{2}

je generující funkce posloupnosti, kde je každý lichý člen nahrazen nulou.

Důkaz. Nahrazení nulou lze vyjádřit takto:

b_{n} ≔ \frac{1 + {(- 1)}^{n}}{2} a_{n}

Generující funkce této posloupnosti je

g (x) = \sum_{n = 0}^{\infty} \frac{1 + {(- 1)}^{n}}{2} a_{n} x^{n} = \frac{1}{2} (\sum_{n = 0}^{\infty} a_{n} x^{n} + \sum_{n = 0}^{\infty} a_{n} {(- x)}^{n}) = \frac{f (x) + f (- x)}{2}

Cvičení. Najděte generující funkci pro

(1,1,2,2,4,4,8,8,16,16, \dots)

Řešení. Toto řešení bylo schováno, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a řešení vás zajímá, kontaktujte mě.

Cvičení. Mějme slovo s konstantními mezerami. Nechť

n_{i}

je první výskyt písmene

i

p_{i}

jeho perioda. Přiřadíme ke každému písmenu generující funkci:

f_{i} (x) ≔ \sum_{k = 0}^{\infty} x^{n_{i} + k p_{i}} = \frac{x^{n_{i}}}{1 - x^{p_{i}}}, x \in B_{0} (1)

Jejich sečtením dostaneme

\sum_{k = 1}^{\infty} x^{k} = \frac{x}{1 - x} = \sum_{i = 0}^{d} \frac{x^{n_{i}}}{1 - x^{p_{i}}}, x \in B_{0} (1)

Dokažte pomocí těchto generujících funkcí:

$\sum_{i = 1}^{d} \frac{1}{p_{i}} = 1$
Důkaz. Vyjdeme ze vztahu $\sum_{i = 1}^{d} \frac{x^{n_{i}}}{1 - x^{p_{i}}} = \frac{x}{1 - x}$ Vynásobme obě strany $1 - x$ : $\sum_{i = 1}^{d} \frac{x^{n_{i}}}{\frac{1 - x^{p_{i}}}{1 - x}} = x$ $\sum_{i = 1}^{d} \frac{x^{n_{i}}}{\sum_{j = 0}^{p_{i} - 1} x^{j}} = x$ Vezměme nyní limitu pro $x \to 1$ , pro kterou za podmínky existence musí rovnost také platit, jelikož platí na $x \in (- 1,1)$ : $\lim_{x \to 1^{-}} \sum_{i = 0}^{d} \frac{x^{n_{i}}}{\sum_{j = 0}^{p_{i} - 1} x^{j}} = \lim_{x \to 1^{-}} x$ $\sum_{i = 1}^{d} \frac{1^{n_{i}}}{\sum_{j = 0}^{p_{i} - 1} 1^{j}} = 1$ $\sum_{i = 1}^{d} \frac{1}{p^{i}} = 1$
Nechť $d > 1$ . Potom $(\forall m \in ℕ) ((\exists j \in \hat{d}) (m | p_{j}) ⟹ (\exists_{2} j \in \hat{d}) (m | p_{j}))$ (Pokud číslo dělí alespoň jednu periodu, potom dělí alespoň dvě periody.)
Důkaz. Tento důkaz byl schován, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a důkaz vás zajímá, kontaktujte mě.
Nechť $d > 1, p_{1} \leq \dots \leq p_{d}$ . Potom $p_{d - 1} = p_{d}$ . (Tedy nejvyšší periodu mají alespoň dvě písmena.)
Důkaz. Tento důkaz byl schován, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a důkaz vás zajímá, kontaktujte mě.
$\sum_{i = 1}^{d} \frac{n_{i}}{p_{i}} = \frac{d + 1}{2}$

Mince

Cvičení. Kolik reprezentací má částka 1689 Kč pomocí mincí 3 Kč a 4 Kč?

Řešení. Toto řešení bylo schováno, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a řešení vás zajímá, kontaktujte mě.

Řešení (obecnější). Zkusme najít obecný předpis pro počet reprezentací

h (n)

libovolné částky

n \in ℕ_{0}

. Vezměme generující funkci

f (x) ≔ (\sum_{n = 0}^{\infty} x^{3 n}) (\sum_{n = 0}^{\infty} x^{4 n}) = \sum_{n = 0}^{\infty} h_{n} x^{n}

Rovnost plyne ze skutečnosti, že každá reprezentace odpovídá součinu dvou členů. Tedy pokud chceme najít předpis pro

h_{n}

, stačí tuto funkci rozvinout do mocninné řady.

\begin{aligned} f (x) & = \frac{1}{1 - x^{3}} \frac{1}{1 - x^{4}} \\ = \frac{D_{1}}{1 - x} + \frac{D_{2}}{{(1 - x)}^{2}} + \frac{C_{1}}{x - ω} + \frac{C_{2}}{x - \overline{ω}} + \frac{B_{1}}{x + 1} + \frac{B_{2}}{x + i} + \frac{B_{3}}{x - i} \\ = \frac{D_{1}}{1 - x} + \frac{D_{2}}{{(1 - x)}^{2}} + \frac{C_{1}^{'}}{1 - \frac{x}{ω}} + \frac{C_{2}^{'}}{1 - \frac{x}{\overline{ω}}} + \frac{B_{1}}{1 - (- x)} + \frac{B_{2}^{'}}{1 - \frac{x}{i}} + \frac{B_{3}^{'}}{1 + \frac{x}{i}} \end{aligned}

Spočtením

\lim_{1} f

dostaneme

D_{2} = \frac{1}{12}

f (x) = \sum_{n = 0}^{\infty} (\frac{1}{12} (n + 1) x^{n} + D_{1} x^{n} + C_{1}^{'} \frac{x^{n}}{ω^{n}} + C_{2}^{'} \frac{x^{n}}{{\overline{ω}}^{n}} + B_{1} {(- 1)}^{n} x^{n} + B_{2}^{'} \frac{x^{n}}{i^{n}} + B_{3}^{'} \frac{x^{n}}{{(- i)}^{n}})

h_{n} = \frac{n}{12} + \frac{1}{12} + D_{1} + \frac{C_{1}^{'}}{ω^{n}} + \frac{C_{2}^{'}}{{\overline{ω}}^{n}} + B_{1} {(- 1)}^{n} + \frac{B_{2}^{'}}{i^{n}} + \frac{B_{3}^{'}}{{(- i)}^{n}} ≕ \frac{n}{12} + a_{n}

a_{n}

je zřejmě periodická s periodou

12

, takže ji můžeme jednoznačně určit tím, že spočteme prvních 12 hodnot

h_{n}

\begin{array}{ccccccccccccc} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ h_{n} & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ a_{n} & 1 & - \frac{1}{12} & - \frac{1}{6} & \frac{3}{4} & \frac{2}{3} & - \frac{5}{12} & \frac{1}{2} & \frac{5}{12} & \frac{1}{3} & \frac{1}{4} & \frac{1}{6} & \frac{1}{12} \end{array}

Nyní už můžeme dopočítat pro původní zadání:

h_{1689} = \frac{1689}{12} + a_{1689} = \frac{1689}{12} + a_{9} = \frac{1689 + 3}{12} = 141

Cvičení. Kolik reprezentací má částka 1689 Kč pomocí mincí 3 Kč a 5 Kč?

Věta. Mějme mince o hodnotách

a, b; a ⟂ b

. Potom:

Každé $n \geq ϰ ≔ (a - 1) (b - 1)$ má reprezentaci.
$ϰ - 1$ nemá reprezentaci.
Mezi částkami ${0, \dots, ϰ - 1}$ má právě polovina reprezentaci.

Důkaz. Podle Bezoutovy věty má rovnice

a x + b y = n

ℤ

řešení

x_{0}, y_{0}

. Každé další řešení je potom ve tvaru

x = x_{0} - k b, y = y_{0} + k a

. Z toho plyne, že existuje řešení (stále v

ℤ

), kde

0 \leq x < b

Lemma. Pokud má rovnice

a x + b y

řešení v

ℕ_{0}

, pak má v

ℕ_{0}

i řešení

x^{'}, y^{'}

, kde

0 \leq x < b

Důkaz. Zvolme

x^{'} ≔ x mod b ≕ x - l b, y^{'} ≔ y + l a

Zvolme

ϰ - 1 ≔ a (b - 1) - b

. Tato částka tedy nebude mít reprezentaci a každá vyšší už ji mít bude. Tím máme první dva body věty. Co se týče třetího bodu, dá se nějak dokázat, že pokud

n = a x + b y

nemá reprezentaci, potom

ϰ - 1 - n

ji má, a to

ϰ - 1 - n = a (b - 1 - x) + b (- 1 - y)

Věta (Schurova). Mějme mince o hodnotách

1 \leq a_{1} < a_{2} < \dots < a_{M}

, kde

a_{i} \in ℕ

\gcd (a_{1}, \dots, a_{M}) = 1

. Označme

h_{n}

počet reprezentací částky

n

. Potom

\lim_{n \to \infty} h_{n} = \infty

Důkaz. Definujme si generující funkci

f (x) ≔ \sum_{n = 0}^{\infty} h_{n} x^{n} = \prod_{k = 1}^{M} \frac{1}{1 - x^{a_{k}}}

Kořen

1

má násobnost

M

, ostatní kořeny

ω

mají menší násobnost

γ_{ω} < M

. Proveďme rozklad na parciální zlomky:

\begin{aligned} f (x) & = \sum_{k = 1}^{M} \frac{D_{i}}{{(1 - x)}^{k}} + \sum_{\begin{array}{c} ω k o \overset{ˇ}{r} e n \\ ω \neq 1 \end{array}} \sum_{k = 1}^{γ_{ω}} \frac{C_{ω, k}}{{(1 - \frac{x}{ω})}^{k}} \\ = \sum_{k = 1}^{M} D_{k} \sum_{n = 0}^{\infty} (\binom{n + k - 1}{n}) x^{n} + \sum_{\begin{array}{c} ω k o \overset{ˇ}{r} e n \\ ω \neq 1 \end{array}} \sum_{k = 1}^{γ_{ω}} C_{ω, k} \sum_{n = 0}^{\infty} (\binom{n + k - 1}{n}) \frac{x^{n}}{ω^{n}} \end{aligned}

\begin{aligned} h_{n} & = \sum_{k = 1}^{M} D_{k} (\binom{n + k - 1}{n}) + \sum_{\begin{array}{c} ω k o \overset{ˇ}{r} e n \\ ω \neq 1 \end{array}} \sum_{k = 1}^{γ_{ω}} C_{ω, k} (\binom{n + k - 1}{n}) \frac{1}{ω^{n}} \\ = \sum_{k = 1}^{M} D_{k} Θ (n^{k - 1}) + \sum_{\begin{array}{c} ω k o \overset{ˇ}{r} e n \\ ω \neq 1 \end{array}} \sum_{k = 1}^{γ_{ω}} C_{ω, k} Θ (n^{k - 1}) \frac{1}{ω^{n}} \\ = \sum_{k = 1}^{M - 1} o (n^{M - 1}) + D_{M} Θ (n^{M - 1}) + \sum_{\begin{array}{c} ω k o \overset{ˇ}{r} e n \\ ω \neq 1 \end{array}} \sum_{k = 1}^{γ_{ω}} o (n^{M - 1}) \frac{1}{ω^{n}} \\ = Θ (D_{M} n^{M - 1} + o (n^{M - 1})) \end{aligned}

Nyní zbývá dokázat, že $D_{M} > 0$ , protože potom zřejmě $h_{n} = Θ (n^{M - 1})$ . Nějak se dá ukázat, že konkrétně $D_{M} = \prod_{k = 1}^{m} \frac{1}{a_{k}}$ .

Definice.

p (n)

je počet zápisů

n

jako součet nerostoucích čísel z

\hat{n}

Příklad.

p (6) = 11

, protože

1 + 1 + 1 + 1 + 1 + 1 = 2 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 = 2 + 2 + 2 = 3 + 1 + 1 + 1 = 3 + 2 + 1 = 3 + 3 = 4 + 1 + 1 = 4 + 2 = 5 + 1 = 6

Věta. Nechť

k \in \hat{n}

. Potom počet rozkladů, jejichž nejvyšší číslo je

k

, je stejný jako počet rozkladů obsahujících přesně

k

sčítanců.

Důkaz. Mezi dvěma zmíněnými množinami existuje bijekce. Vezměme například

9 = 4 + 3 + 2

a najděme k němu rozklad o čtyřech sčítancích:

Věta. Počet rozkladů skládajících se pouze z lichých čísel je stejný jako počet rozkladů skládajících se z různých čísel.

Důkaz.

f (x) ≔ \sum_{n = 0}^{\infty} p (n) x^{n} = \prod_{n = 0}^{\infty} \sum_{k = 0}^{\infty} x^{k n}

f_{r \overset{˚}{u} z n \overset{ˊ}{e}} (x) ≔ \sum_{n = 0}^{\infty} p_{r \overset{˚}{u} z n \overset{ˊ}{e}} (n) x^{n} = \prod_{n = 0}^{\infty} (1 + x^{n})

f_{l i c h \overset{ˊ}{e}} (x) ≔ \sum_{n = 0}^{\infty} p_{l i c h \overset{ˊ}{e}} (n) x^{n} = \prod_{n = 0}^{\infty} \sum_{k = 0}^{\infty} x^{k (2 n + 1)}

To se po rozepsání rovná:

\prod_{n = 0}^{\infty} (1 + x^{n}) = \prod_{n = 0}^{\infty} \frac{(1 + x^{n}) (1 - x^{n})}{1 - x^{n}} = \prod_{n = 0}^{\infty} \frac{1 - x^{2 n}}{1 - x^{n}} = \prod_{n = 0}^{\infty} \frac{1}{1 - x^{2 n + 1}}

Věta (Erdősova-Szekeresova). Mějme libovolnou permutaci čísel

\hat{n^{2} + 1}

. Potom existuje rostoucí nebo klesající podposloupnost o

n + 1

členech.

Důkaz. Mějme permutaci

a_{1}, a_{2}, \dots, a_{n^{2} + 1}

. Nechť

r_{i}, k_{i}

je délka nejdelší rostoucí/klesající posloupnosti začínající číslem

a_{i}

. Aby věta neplatila, musí být

(\forall i \in \hat{n^{2} + 1}) (r_{i} \leq n \land k_{i} \leq n)

. Takových dvojic existuje pouze

n^{2}

, takže podle holubníkového principu najdeme

i < j

taková, že

(r_{i}, k_{i}) = (r_{j}, k_{j})

. To je ale spor, protože k jedné z posloupností od

a_{j}

dokážeme zleva přilepit

a_{i}

■

Cvičení. Dokažte, že pro

\hat{n^{2}}

už Erdősova-Szekeresova věta neplatí pro žádné

n

Důkaz. Tento důkaz byl schován, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a důkaz vás zajímá, kontaktujte mě.