rdck.dev

Kombagra 1


Higher beings, these words are for you alone. Občas tu je něco blbě tak bacha

Spolupachatel skript Hanek Javatý.

Josef “Pepa” Tkadlec💖

Požadavky

Balls

Odhady

[P: chapter 1, MN: chapter 3]

Odhady faktoriálů

Definice: Faktoriál

n!:=n(n1)(n2)21n ! := n \cdot \left ( n - 1 \right ) \cdot \left ( n - 2 \right ) \cdot \ldots \cdot 2 \cdot 1

Pozorování

(n0)(n!nn)\left ( \forall n \in \mathbb{N}_{0} \right ) \left ( n ! \le n^{n} \right )

Důkaz


Nejdříve dokážeme AG nerovnost, kterou použijeme při důkazu tvrzení níže. Actually that was a lie ale nechám to tady jelikož už sem to vyasciimatha s c i i m a t hoval.

Pozorování

AG nerovnost x,y0\forall x , y \in \mathbb{R} \ge 0

xyx+y2\sqrt{x y} \le \frac{x + y}{2}

Důkaz

(xy)20\left ( \sqrt{x} - \sqrt{y} \right )^{2} \ge 0 x2xy+y0x - 2 \sqrt{x y} + y \ge 0 x+y2xyx + y \ge 2 \sqrt{x y} x+y2xy\frac{x + y}{2} \ge \sqrt{x y}

Pozorování

(n0)(nn2n!nn)\left ( \forall n \in \mathbb{N} \ge 0 \right ) \left ( n^{\frac{n}{2}} \le n ! \le n^{n} \right )

Důkaz

n!2=(n1)((n1)2)((n2)3)(1n)n !^{2} = \left ( n \cdot 1 \right ) \cdot \left ( \left ( n - 1 \right ) \cdot 2 \right ) \cdot \left ( \left ( n - 2 \right ) \cdot 3 \right ) \cdot \cdots \cdot \left ( 1 \cdot n \right )

Každý z těchto činitelů cinc_{i} \ge n, ci=i(ni+1)c_{i} = i \cdot \left ( n - i + 1 \right ). To protože na okrajích i=1i = 1 nebo i=ni = n je to zjevně nn.

V intervalu i{2,n1}i \in \left \lbrace 2 , n - 1 \right \rbrace je min(i,ni+1)2\min \left ( i , n - i + 1 \right ) \ge 2 a max(i,ni+1)n2\max \left ( i , n - i + 1 \right ) \ge \frac{n}{2}

tudíž

n!2nnn !^{2} \ge n^{n}

n!nn2n ! \ge n^{\frac{n}{2}}

Nyní ta těžší nerovnost

Pozorování

n0\forall n \in \mathbb{N} \ge 0

e(ne)nn!en(ne)ne \left ( \frac{n}{e} \right )^{n} \le n ! \le e n \left ( \frac{n}{e} \right )^{n}

Důkaz

Předem se omlouvám, je to convoluted AF. Obrázek je důležitej, vlastně zavíráme ln(n!)\ln{\left ( n ! \right )} mezi dva integrály ln(n!)\ln{\left ( n ! \right )} co má jiný meze.

Spodní odhad. Pojďme se podívat na to, jak se chová funkce ln(n!)\ln{\left ( n ! \right )}.

ln(n!)=i=1nln(i)=\ln{\left ( n ! \right )} = \sum_{i = 1}^{n} \ln{\left ( i \right )} = modrá část.


ln(n!)\ln{\left ( n ! \right )} tedy odpovídá modré části. Ta je určitě větší než červená, což je integrál lnx\ln{x} od 11 do nn.

Červená:

1nln(x)dx=[xlnxx]1n=nlnnn+1\int_{1}^{n} \ln{\left ( x \right )} dx = \left [ x \cdot \ln{x} - x \right ]_{1}^{n} = n \ln{n} - n + 1

Můžeme z logaritmu udělat výsledek itegrálu tím hodnotu zmenšit. n!=eln(n!)enlnnn+1=nn1ene=e(ne)nn ! = e^{\ln{\left ( n ! \right )}} \ge e^{n \ln{n} - n + 1} = n^{n} \cdot \frac{1}{e^{n}} \cdot e = e \left ( \frac{n}{e} \right )^{n}

K dokázání horního odhadu nám pomůže zelená část. Je vlastně stejná jako ta modrá, akorát je posunutá doprava. Pokud budeme porovnávat její hodnotu s červenou částí, tak červená bude větší, musíme ji ale také posunout. Integrál bude tedy od 11 do n+1n + 1

ln(n!)1n+1ln(x)dx=[xlnxx]1n+1\ln{\left ( n ! \right )} \le \int_{1}^{n + 1} \ln{\left ( x \right )} dx = \left [ x \cdot \ln{x} - x \right ]_{1}^{n + 1} =(n+1)ln(n+1)n= \left ( n + 1 \right ) \ln{\left ( n + 1 \right )} - n

n!=eln(n!)en+1ln(n+1)n=(n+1)n+1enn ! = e^{\ln{\left ( n ! \right )}} \le e^{n + 1} \ln{\left ( n + 1 \right )} - n = \frac{\left ( n + 1 \right )^{n + 1}}{e^{n}}

Nyní opět evil matematický dosazení aby nám vyšlo to co chceme. Za nn dosadíme n1n - 1.

n!=n(n1)!dis onen(nnen1)=en(ne)nn ! = n \cdot \underbrace{\left ( n - 1 \right ) !}_{\text{dis one}} \le n \cdot \left ( \frac{n^{n}}{e^{n - 1}} \right ) = e n \left ( \frac{n}{e} \right )^{n}

Celkově tedy

e(ne)nn!en(ne)ne \left ( \frac{n}{e} \right )^{n} \le n ! \le e n \left ( \frac{n}{e} \right )^{n} 🔲

Pozorování

Stirling formula n!(2πn)12(ne)nn ! \cong \left ( 2 \pi n \right ) \frac{1}{2} \left ( \frac{n}{e} \right )^{n}

Důkaz

Patří do analýzy nebo tak něco

Odhady binomického koeficientu

Definice: Binomický koeficient

(nk)=n!k!(nk)!=n(n1)(nk+1)k!\left ( \begin{matrix} n \\ k \end{matrix} \right ) = \frac{n !}{k ! \left ( n - k \right ) !} = \frac{n \cdot \left ( n - 1 \right ) \cdot \ldots \cdot \left ( n - k + 1 \right )}{k !}

Pozorování

(nk)k(nk)(enk)k\left ( \frac{n}{k} \right )^{k} \le \left ( \begin{matrix} n \\ k \end{matrix} \right ) \le \left ( \frac{e n}{k} \right )^{k}

Důkaz

Spodní odhad

(i{0,,k1})(nikink)\left ( \forall i \in \left \lbrace 0 , \ldots , k - 1 \right \rbrace \right ) \left ( \frac{n - i}{k - i} \ge \frac{n}{k} \right )

(důkaz roznásobením). Díky tomu

(nk)=defi=0k1nikii=0k1nk=(nk)k\left ( \begin{matrix} n \\ k \end{matrix} \right ) \overset{\text{def}}{=} \prod_{i = 0}^{k - 1} \frac{n - i}{k - i} \ge \prod_{i = 0}^{k - 1} \frac{n}{k} = \left ( \frac{n}{k} \right )^{k}

Horní odhad

Nechť x=knx = \frac{k}{n}. Všimni si že 0x10 \le x \le 1 protože knk \le n

Budiž vymyšlený výraz:

(n0)x0+(n1)x1++(nn)xn=(1+x)n\left ( \begin{matrix} n \\ 0 \end{matrix} \right ) x^{0} + \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) x^{1} + \ldots + \left ( \begin{matrix} n \\ n \end{matrix} \right ) x^{n} = \left ( 1 + x \right )^{n}

Na levé straně vynecháme sčítance za xkx^{k}

(n0)x0+(n1)x1++(nk)xk(1+x)n\left ( \begin{matrix} n \\ 0 \end{matrix} \right ) x^{0} + \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) x^{1} + \ldots + \left ( \begin{matrix} n \\ k \end{matrix} \right ) x^{k} \le \left ( 1 + x \right )^{n}

Vydělíme xkx^{k}

1xk0(n0)+1xk1(n1)++1xkk(nk)(1+x)nxk\frac{1}{x^{k - 0}} \left ( \begin{matrix} n \\ 0 \end{matrix} \right ) + \frac{1}{x^{k - 1}} \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) + \ldots + \frac{1}{x^{k - k}} \left ( \begin{matrix} n \\ k \end{matrix} \right ) \le \frac{\left ( 1 + x \right )^{n}}{x^{k}}

Na levé straně je každý koeficient 1\ge 1, takže když je vynecháme tak stranu pouze zmenšíme.

(n0)+(n1)++(nk)(1+x)nxk\left ( \begin{matrix} n \\ 0 \end{matrix} \right ) + \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) + \ldots + \left ( \begin{matrix} n \\ k \end{matrix} \right ) \le \frac{\left ( 1 + x \right )^{n}}{x^{k}}

Všimni si cool feature je že už tam je ten (nk)\left ( \begin{matrix} n \\ k \end{matrix} \right ) který chceme! Expandujeme x=knx = \frac{k}{n}.

(n0)+(n1)++(nk)(1+kn)n(nk)k\left ( \begin{matrix} n \\ 0 \end{matrix} \right ) + \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) + \ldots + \left ( \begin{matrix} n \\ k \end{matrix} \right ) \le \left ( 1 + \frac{k}{n} \right )^{n} \cdot \left ( \frac{n}{k} \right )^{k}

(všimni si obrácení zlomku kn\frac{k}{n} kterým dělíme)

využijeme fakt: 1+xex1 + x \le e^{x} (1+knekn\to 1 + \frac{k}{n} \le e^{\frac{k}{n}}) pro umlácení pravé strany:

(1+kn)n(ekn)n=ek\left ( 1 + \frac{k}{n} \right )^{n} \le \left ( e^{\frac{k}{n}} \right )^{n} = e^{k}

tedy dostaneme

(n0)+(n1)++(nk)ek(nk)k\left ( \begin{matrix} n \\ 0 \end{matrix} \right ) + \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) + \ldots + \left ( \begin{matrix} n \\ k \end{matrix} \right ) \le e^{k} \cdot \left ( \frac{n}{k} \right )^{k}

Vlevo zahodíme Binomické koeficienty které nás nezajímají (zase pouze zmenší)

(nk)(enk)k\left ( \begin{matrix} n \\ k \end{matrix} \right ) \le \left ( \frac{e n}{k} \right )^{k}

🔲

Nyní se podívejme co se děje s prostředním binomickým koeficientem, ten by měl být řekněme největší (něco něco pascalův trojúhelník);

Pozorování

22m2m(2mm)22m2m\frac{2^{2 m}}{2 \sqrt{m}} \le \left ( \begin{matrix} 2 m \\ m \end{matrix} \right ) \le \frac{2^{2 m}}{\sqrt{2 m}}

Důkaz

Nejdříve si pořiďme P. P:=135(2m1)246(2m)P := \frac{1 \cdot 3 \cdot 5 \cdot \cdots \cdot \left ( 2 m - 1 \right )}{2 \cdot 4 \cdot 6 \cdot \cdots \cdot \left ( 2 m \right )} Vynásobíme 1 P=135(2m1)246(2m)24(2m)24(2m)P = \frac{1 \cdot 3 \cdot 5 \cdot \cdots \cdot \left ( 2 m - 1 \right )}{2 \cdot 4 \cdot 6 \cdot \cdots \cdot \left ( 2 m \right )} \cdot \frac{2 \cdot 4 \cdot \cdots \cdot \left ( 2 m \right )}{2 \cdot 4 \cdot \cdots \cdot \left ( 2 m \right )} =(2m)!22m(m!)2= \frac{\left ( 2 m \right ) !}{2^{2 m} \cdot \left ( m ! \right )^{2}} =122m(2mm)= \frac{1}{2^{2 m}} \cdot \left ( \begin{matrix} 2 m \\ m \end{matrix} \right ) To nám pomůže, protože v dokazované nerovnosti jsou v čitatelích právě 22m2^{2 m}, takže nyní nám stačí dokázat 12mP12m\frac{1}{2 \sqrt{m}} \le P \le \frac{1}{\sqrt{2 m}}

Horní odhad

Uvažme posloupnost (322)(3542)(5662)(2m1)(2m+1)(2m)2\left ( \frac{3}{2^{2}} \right ) \cdot \left ( \frac{3 \cdot 5}{4^{2}} \right ) \cdot \left ( \frac{5 \cdot 6}{6^{2}} \right ) \cdot \cdots \cdot \frac{\left ( 2 m - 1 \right ) \left ( 2 m + 1 \right )}{\left ( 2 m \right )^{2}}, ta má ve výsledku v čitateli (skoro) všechna lichá čísla dvakrát a všechna sudá čísla ve jmenovateli dvakrát. Tado posloupnost se tedy rovná P2P^{2} až na přebytek. Co zbývá? 11 vlevo a 2m+12 m + 1 vpravo. =(2m+1)P2= \left ( 2 m + 1 \right ) P^{2} Jelikož každý činitel <1< 1, tak dostáváme že (2m+1)P2<1\left ( 2 m + 1 \right ) P^{2} < 1, tedy P212m+1P^{2} \le \frac{1}{2 m + 1} Zmenšíme jmenovatel, takže zvětšíme pravou stranu. P212mP^{2} \le \frac{1}{2 m} P12mP \le \frac{1}{\sqrt{2 m}}

Spodní odhad je podobný, ale má obrácené čitatele a jmenovatele. Uvažme posloupnost (2432)(4652)(6872)(2m2)(2m)(2m1)2\left ( \frac{2 \cdot 4}{3^{2}} \right ) \cdot \left ( \frac{4 \cdot 6}{5^{2}} \right ) \cdot \left ( \frac{6 \cdot 8}{7^{2}} \right ) \cdot \cdots \cdot \frac{\left ( 2 m - 2 \right ) \left ( 2 m \right )}{\left ( 2 m - 1 \right )^{2}}, Tato posloupnost se chová skoro stejně jako 1P2\frac{1}{P^{2}}, až na přebytek v čitateli. Co přebývá? 22 vlevo a 2m2 m vpravo. Tudíž =12(2m)P2= \frac{1}{2 \cdot \left ( 2 m \right ) \cdot P^{2}} Každý člen je opět <1< 1, takže 12(2m)P2<1\frac{1}{2 \cdot \left ( 2 m \right ) \cdot P^{2}} < 1 P2>122mP^{2} > \frac{1}{2 \cdot 2 m} P>12mP > \frac{1}{2 \sqrt{m}} 🔲

Příklad: random walk. Kolikrát v průměru se dostaneme po 2m krocích zpátky do počátku, jestliže se v každém kroku rozhodneme jít náhodně doleva/doprava?

Řešení: po 2m2 m krocích existuje (2mm)\left ( \begin{matrix} 2 m \\ m \end{matrix} \right ) procházek které končí v 0. Celkem je tedy pravděpodobnost (2mm)22m\frac{\left ( \begin{matrix} 2 m \\ m \end{matrix} \right )}{2^{2 m}} že po 2m2 m krocích jsme v nule. Suma přes všechny délky:

m=1(2mm)22mm=112m\sum_{m = 1}^{\infty} \frac{\left ( \begin{matrix} 2 m \\ m \end{matrix} \right )}{2^{2 m}} \ge \sum_{m = 1}^{\infty} \frac{1}{2 \sqrt{m}} což diverguje. Po nekonečně krocích tedy můžeme očekávat nekonečně návšťev počátku.

Divergence se může ověřit vytáhnutím 12\frac{1}{2} ven a omezení harmonickou řadou.

Vytvořující funkce

Motivační příklad, kolika způsoby jde vytáhnout 7 míčků z pytle ve kterém jsou 3 červené, 4 zelené a 5 modrých? Moudrý čtenář ví že je to konvoluce (x+x2+x3)(x++x4)(x++x5)\left ( x + x^{2} + x^{3} \right ) \left ( x + \cdots + x^{4} \right ) \left ( x + \cdots + x^{5} \right ) a ptáme se na koeficient x7x^{7}.

Definice: Vytvořující funkce (VF)

Nechť je (an)n=0\left ( a_{n} \right )_{n = 0}^{\infty} posloupnost reálných čísel. Vytvořující funkce této posloupnosti je řada a(x)=i=0aixia \left ( x \right ) = \sum_{i = 0}^{\infty} a_{i} x^{i}

Poznámka: Spíše než nekonečná řada je důležitá uzavřená reprezentace vytvořující funkce. Např. řada a(x)=1+x+x2+a \left ( x \right ) = 1 + x + x^{2} + \cdots je generovaná funkcí 11+x\frac{1}{1 + x}. Pokud je xx v intervalu (1,1)\left ( - 1 , 1 \right ), tak řada konverguje a má stejný součet. (Důkaz taylorova řada).

Z toho dostáváme jakousi podmínku pro to, aby posloupnost měla vytvořující funkci. Stačí, aby |an|Kn\left | a_{n} \right | \le K^{n} pro nějaké reálné KK a n1\forall n \to 1. Pak totiž pro x(1K,1K)\forall x \in \left ( - \frac{1}{K} , \frac{1}{K} \right ) řada a(x)=i=0aixia \left ( x \right ) = \sum_{i = 0}^{\infty} a_{i} x^{i} konverguje.

Zajímavé je co se stane, když do VF dosadíme 0. V tu chvíli dostaneme první prvek a0a_{0}, protože všechny ostatní se vynulují. Také je zajímavé derivovat VF. Tím se všechny členy posloupnosti posunou o jedna doleva a vydělí se předchozím exponentem. Kombinací těchto dvou faktů dostáváme vzorec pro nn-tý člen posloupnosti. Uděláme nn-tou derivaci, vydělíme n!n ! a dosadíme 00.

an=a(n)(0)n!a_{n} = \frac{a^{\left ( n \right )} \left ( 0 \right )}{n !}

Definice: Tabulka operací s VF
Operace Řada Úprava
Součet a0+b0,a1+b1,a2+b2,a_{0} + b_{0} , a_{1} + b_{1} , a_{2} + b_{2} , \ldots a(x)+b(x)a \left ( x \right ) + b \left ( x \right )
Násobek αa0,αa1,αa2,α a_{0} , α a_{1} , α a_{2} , \ldots αa(x)α a \left ( x \right )
Posun doprava 0,a0,a1,0 , a_{0} , a_{1} , \ldots xa(x)x \cdot a \left ( x \right )
Posun doleva a1,a2,a3,a_{1} , a_{2} , a_{3} , \ldots a(x)a0x\frac{a \left ( x \right ) - a_{0}}{x}
Substituce αxα x α0a0,α1a1,α2a2,α^{0} a_{0} , α^{1} a_{1} , α^{2} a_{2} , \ldots a(αx)a \left ( α x \right )
Substituce xnx^{n} a0,0,,0n1,a1,0,,0n1,a2,a_{0} , \overbrace{0 , \ldots , 0}^{n - 1} , a_{1} , \overbrace{0 , \ldots , 0}^{n - 1} , a_{2} , \ldots a(xn)a \left ( x^{n} \right )
Derivace a1,2a2,3a3,a_{1} , 2 a_{2} , 3 a_{3} , \ldots a(x)a ' \left ( x \right )
Integrování 0,a1,a22,a33,0 , a_{1} , \frac{a_{2}}{2} , \frac{a_{3}}{3} , \ldots 0xa(t)dt\int_{0}^{x} a \left ( t \right ) dt
Konvoluce an=k=0n(akbnk)a_{n} = \sum_{k = 0}^{n} \left ( a_{k} \cdot b_{n - k} \right ) a(x)b(x)a \left ( x \right ) \cdot b \left ( x \right )

Ověř si to :)

Teď dlouhej talk o tom jak vyjádřit uzavřeně nějakou hodnotu rekurentně zadané rovnice. Tldr: Zapiš si posloupnost jako řadu, vypiš prvních pár prvků abys tam měl ten člen co máš rekurentně zadanej.

an+2=an+1+2ana_{n + 2} = a_{n + 1} + 2 a_{n}

a(x)=a0+a1x+x2n=0an+2xna \left ( x \right ) = a_{0} + a_{1} x + x^{2} \sum_{n = 0}^{\infty} a_{n + 2} x^{n}

Všimni si pár triků, např vytknutí xx před sumu. Poté dosaď rekurenci, roztrhni sumu a snaž se nekonečnou sumu nahradit za tvou VF. Neboj se podvádět, musíš přičítat nulté a první členy, zvracej xx zpátky do sumy, prostě se snaž dostat tvar n=000anxn\sum_{n = 0}^{00} a_{n} x^{n}. To pak nahraď za a(x)a \left ( x \right ) a vyřeš pro a(x)a \left ( x \right ).

Potom dostaneš uzavřený tvar pro tvojí VF. Dostaň ji do tvarů a1x+\frac{a}{1 - x} + to samé několikrát, kde xx není nutně xx a aa je konstanta. Nejspíš budeš řešit parciální zlomky. Pak se podívej do tabulky, vyhaluz posloupnosti co sčítáš a máš vzoreček pro ana_{n}. Snadné, že? :)

Přikládám svůj úkol protože si to nebudu pamatovat :)/

Zobecněná binomická věta

Definice: Zobecněný binomický koeficient

r,k0\forall r \in \mathbb{R} , \forall k \in \mathbb{N}_{0}

(rk)=r(r1)(r2)(rk+1)k!\left ( \begin{matrix} r \\ k \end{matrix} \right ) = \frac{r \left ( r - 1 \right ) \left ( r - 2 \right ) \ldots \left ( r - k + 1 \right )}{k !}

Prostě normální koeficient :)

Definice: Zobecněná binomická věta

r,x(1,1)\forall r \in \mathbb{R} , x \in \left ( - 1 , 1 \right )

(1+x)r=(r0)x0+(r1)x1+\left ( 1 + x \right )^{r} = \left ( \begin{matrix} r \\ 0 \end{matrix} \right ) x^{0} + \left ( \begin{matrix} r \\ 1 \end{matrix} \right ) x^{1} + \cdots

Z toho plyne, že pro n,x(1,1)n \in \mathbb{N} , x \in \left ( - 1 , 1 \right )

1(1x)n=(n1n1)x0+(nn1)x1+(n+1n1)x2+=\frac{1}{\left ( 1 - x \right )^{n}} = \left ( \begin{matrix} n - 1 \\ n - 1 \end{matrix} \right ) x^{0} + \left ( \begin{matrix} n \\ n - 1 \end{matrix} \right ) x^{1} + \left ( \begin{matrix} n + 1 \\ n - 1 \end{matrix} \right ) x^{2} + \cdots = =i=0(n+i1n1)xi= \sum_{i = 0}^{\infty} \left ( \begin{matrix} n + i - 1 \\ n - 1 \end{matrix} \right ) x^{i}

Příklad: jak spočítat motivační příklad ale lépe.

V krabici je 30 červených, 40 žlutých a 50 zelených míčků. Kolika způsoby lze vybrat 70?

(1+x+x30)(1+x++x40)(1+x++x50)=\left ( 1 + x + \cdots x^{30} \right ) \left ( 1 + x + \cdots + x^{40} \right ) \left ( 1 + x + \cdots + x^{50} \right ) =

=1x311x1x411x1x511x= \frac{1 - x^{31}}{1 - x} \frac{1 - x^{41}}{1 - x} \frac{1 - x^{51}}{1 - x}

Wait, cože? <- tohle bys měl být ty. Jak jsme přišli na to že 1+x++x301 + x + \cdots + x^{30} je nějakej random zlomek? Vem vytvořující funkci samých 1 a vynásob jí 1x311 - x^{31}.

11xx311x=11x(1x31)\frac{1}{1 - x} - \frac{x^{31}}{1 - x} = \frac{1}{1 - x} \cdot \left ( 1 - x^{31} \right )

Co dostaneš? Normální vytvořující funkci (1\cdot 1), od které ale odečítáš posunutou VF od x31x^{31}. To znamená že ti zbyde jen 1+x++x301 + x + \cdots + x^{30}.🪄

To ale znamená že máme funkci v uzavřené formě, a díky zobecněné binomické větě víme, že

=((22)+(33)x+)(1x31)(1x41)(1x51)= \left ( \left ( \begin{matrix} 2 \\ 2 \end{matrix} \right ) + \left ( \begin{matrix} 3 \\ 3 \end{matrix} \right ) x + \cdots \right ) \left ( 1 - x^{31} \right ) \left ( 1 - x^{41} \right ) \left ( 1 - x^{51} \right )

A ptáme se na koeficient u x70x^{70}, který ==

(722)+\left ( \begin{matrix} 72 \\ 2 \end{matrix} \right ) + za samé 1, (72312)+- \left ( \begin{matrix} 72 - 31 \\ 2 \end{matrix} \right ) + když vybereme x31x^{31} atd…

Definice: Zakořeněný binární strom

Strom je buď prázdný, nebo má levý a pravý podstrom, které jsou také binárními stromy (můžou být prázdné)

Budeme počítat kolik jich je, bn=b_{n} = počet různých binárních zakořeněných stromů na n vrcholech.

Lze si rozmyslet že bn=k=0n1bkbnk1b_{n} = \sum_{k = 0}^{n - 1} b_{k} \cdot b_{n - k - 1}, protože se rekurzíme na obě části, do každé přiřadíme část vrcholů. Když z toho uděláme VF, tak vychází, že

b(x)=xb(x)b(x)+1b \left ( x \right ) = x \cdot b \left ( x \right ) \cdot b \left ( x \right ) + 1

+1+ 1 aby vycházelo b(0)b \left ( 0 \right ) správně a xx je posun. Pak už je to pouze konvoluce. Vyjádříme b(x)b \left ( x \right )🪄 - normální kvadratická rovnice. Na odmocninu použij zobecněnou binomickou větu (mocníš na 12\frac{1}{2}).

b(x)=k=1(4)k(12k)xk2xb \left ( x \right ) = \frac{- \sum_{k = 1}^{\infty} \left ( - 4 \right )^{k} \left ( \begin{matrix} \frac{1}{2} \\ k \end{matrix} \right ) x^{k}}{2 x}

Vyjádření konkrétního koeficientu pak dává Catalanovo číslo

bn=1n+1(2nn)b_{n} = \frac{1}{n + 1} \left ( \begin{matrix} 2 n \\ n \end{matrix} \right )

TODO #partitions of n into odd parts = #partitions of n into distinct parts [MN 12.7 / here]

Finite projective planes (fpp FPR)

[P: chapter 3, MN: chapter 9]

Definice: množinový systém

budiž:

  • XX množina
  • S(X)S \subseteq \mathbb{P} \left ( X \right ) (některé podmnožiny XX)

Množinový systém je dvojice (X,S)\left ( X , S \right )

Definice: Konečná projektivní rovina (FPR)

Jako kdyby 2\mathbb{R}^{2} ale very nice✨ and neat✨ and all✨ (máme rádi FPR)

XX je množina bodů. \mathcal{L} je množina čar. (X,)\left ( X , \mathcal{L} \right ) je množinový systém.

  1. Existují 4 různé body takové že libovlná přímka protne maximálně 2 z nich.
  2. Libovolné 2 přímky mají právě jeden společný bod
  3. Libovolné 2 body mají právě jednu společnou přímku
Pozorování

Nechť (X,)\left ( X , \mathcal{L} \right ) FPR.

Všechny přímky mají stejný počet bodů.

Důkaz

Vemme libovolné L,LL , L ' \in \mathcal{L}. Nejprve pomocné pozorování:

Pozorování

Existuje bod zXz \in X který není ani na LL ani na LL '

Důkaz

Vezmeme 4-prvkovou množinu FF z prvního axiomu. Máme |LF|2\left | L \cup F \right | \le 2 a |LF|2\left | L ' \cup F \right | \le 2.

Pokud FF není podmnožina LLL \cup L ' pak máme hotovo. Znamená to že alespoň jeden bod z FF je mimo LL i LL '.

Jinak musí LL protínat FF ve 2 bodech aa a bb a zároveň musí LL ' protínat FF ve druhých 2 bodech cc a dd (více by bylo ve sporu s axiomem) (F={a,b,c,d}F = \left \lbrace a , b , c , d \right \rbrace).

Pak vezmeme přímky:

  • R1R_{1} protíná aa a cc
  • R2R_{2} protíná bb a dd

Nechť zz je průnik R1R_{1} s R2R_{2}. Pak zz není v LL ani v LL '.

LL a R1R_{1} se protínají v bodě aa. Pokud by zz byl v LL pak by se LL a R1R_{1} protínají v bodech zz i aa což je spor. Tudíž zz nemůže ležet na LL a analogicky ani na LL '. 🔲

Ozbrojeni tímto pozorováním, LL a LL ' mají stejnou velikost, definujíc funkci φ:LL\varphi : L \to L '.

Ukážeme, že φ\varphi je bijekce.

Neformálně: zz je náš sniping spot a xLx \in L jsou body skrz které střílíme do LL '.

Vemme náš shiny bod zz mimo LLL \cup L ' a definujme obraz (terč) φ(x)\varphi \left ( x \right ) pro xLx \in L jako průnik LL ' s přímkou která prochází body xx a zz (bullet trail).

Z axiomů 2 a 3 je terč dobře definovaný. Dvě různá x,yLx , y \in L musí mít různé obrazy $varphi(x), φ(y)\varphi \left ( y \right ) jinak by tyto dva bullet traily (přímky) sdílely více než jeden bod. Tudíž φ\varphi je bijekce.

Definice: Řád FPR

Řád FPR (X,)\left ( X , \mathcal{L} \right ) je |L|1\left | L \right | - 1 pro libovolné LL \in \mathcal{L} (všechny LL jsou stejně dlouhé).

(To 1- 1 je lehce otravné ale není to chyba…)

Pro FPR (X,)\left ( X , \mathcal{L} \right ) řádu nn:

Pozorování

Právě n+1n + 1 přímek prochází každým bodem xx

Důkaz

Nechť libovolný xXx \in X. Jistě máme LL \in \mathcal{L} která neobsahuje xx.

Pro každý yLy \in L vezmeme přímku procházející xx a yy. To je jistě přímka a jistě prochází xx a jistě jich je n+1n + 1. Nice.

Ale co kdyby existovala nějaká další zlá přímka ZZ? Taková by musela protnout xx ale zároveň každé 2 přímky mají společný bod takže existuje zZLz \in Z \cup L takže zz je jedno z yy a žádná zlá přímka ZZ neexistuje.

Pozorování

|X|=n2+n+1\left | X \right | = n^{2} + n + 1

Důkaz

Vezmeme L={x0,,xn}}L = \left \lbrace x_{0} , \ldots , x_{n} \right \rbrace \in \mathcal{L} \rbrace a bod aa mimo LL. Pak vyrobíme přímky L0,LnL_{0} , \ldots L_{n} kde LiL_{i} protíná aa a xix_{i}. Každá LiL_{i}nn dalších bodů mimo aa, takže dohromady n+1n + 1 přímek obsahuje nn různých bodů plus samotné aa. (n+1)n+1=n2+n+1\left ( n + 1 \right ) \cdot n + 1 = n^{2} + n + 1.

(Jednotlivá LiL_{i} nemohou sdílet těchto “nn dalších bodů” protože pak by tyto 2 přímky sdíleli 2 body (aa a tento jeden další))

Pozorování

||=n2+n+1\left | \mathcal{L} \right | = n^{2} + n + 1

Důkaz

Důkaz vypadne automaticky z toho minulého po researchnutí duality.

Dualita

Definice: Dualita

Dualita znamená “prohození role přímky a bodu”. Pro přesnou formulaci si pro FPR zavedeme graf incidence.

Definice: Graf incidence

Bipartitní graf kde v první partii vrcholy reprezentují přímky a v druhé partii vrcholy reprezentují body.

Mezi vrcholi je hrana pokud daný bod patří do dané přímky.

Pro dané FPR (X,)\left ( X , \mathcal{L} \right ) jeho duál (X,)\left ( X ' , \mathcal{L} ' \right ) dostaneme vyrobením grafu incidence, prohozením významu partií a přeinterpretováním transformovaného bipartitního grafu incidence zpět na FPR.

Pozorování

Duál FPR je také FPR

Důkaz

Budiž FPR (X,)\left ( X , \mathcal{L} \right ) a jeho duál (,Λ)\left ( \mathcal{L} , \Lambda \right ), kde Λ\Lambda je systém podmnožin \mathcal{L}. Každý z těchto podmnožin odpovídá nějakému bodu z XX.

Všimněte si, že pro různé xXx \in X dostaneme různé podmnožiny \mathcal{L}.

Musíme ověřit axiomy FPR pro tento duál.

  1. Přeloženo pro duál říká: Existují 4 přímky takové že žádné 3 z nich nemají společný bod. Vezmeme {a,b,c,d}\left \lbrace a , b , c , d \right \rbrace z původního axiomu pro neduál. Z něj vyrobíme 4 přímky: L1=abL_{1} = a b, L2=cdL_{2} = c d, L3=adL_{3} = a d, L4=bcL_{4} = b c. Pro tyhle to platí.
  2. Je to samé jako 3. pro neduál!
  3. Je to samé jako 2. pro neduál!
Pozorování

Duál FPR řádu nn je FPR řádu nn

Důkaz

plyne z pozorování o počtu bodů na přímce a přímek procházející bodem

Pozorování

Existují FPR řádu 2, 3, 4, 5. 6 ne. 7, 8, 9 existují, 10 ne.

Existují pokud existuje těleso řádu nn (tedy n=pαn = p^{\alpha} pro prvočíslo pp).

Konstrukce FPR z konečného tělesa.

  1. Prohlásíme že existují trojice prvků z tělesa.
  2. Budiž ekvivalence \approx kde trojice (a,b,c)(d,e,f)\left ( a , b , c \right ) \approx \left ( d , e , f \right ) kdyžž existuje nenulová λ\lambda z tělesa taková že a=λda = \lambda d, b=λeb = \lambda e, c=λfc = \lambda f.
  3. Body v FPR jsou třídy této ekvivalence KROM (0,0,0)\left ( 0 , 0 , 0 \right ). (Takhle vyrobené FPR se často značí PK2P K^{2} kde KK je to původní těleso)
  4. Přímky v tomto FPR jsou opět trojice prvků z tělesa bez (0,0,0)\left ( 0 , 0 , 0 \right ).
  5. Bod (x,y,t)\left ( x , y , t \right ) leží na přímce (a,b,c)\left ( a , b , c \right ) kdyžž ax+by+ct=0a x + b y + c t = 0.
  6. Profit

Stačí dokázat axiomy:

Pozorování

Začneme s tím že 2 přímky sdílí právě 1 bod.

Důkaz

Nechť máme (a1,b1,c1)\left ( a_{1} , b_{1} , c_{1} \right ) a (a2,b2,c2)\left ( a_{2} , b_{2} , c_{2} \right ), 3D vektory v tělese KK. Oba nenulové.

Jelikož oba nejsou násobky toho druhého, jsou lineárně nezávislé. Takže matice

(a1b1c1a2b2c2)\left ( \begin{matrix} a_{1} & b_{1} & c_{1} \\ a_{2} & b_{2} & c_{2} \end{matrix} \right )

má rank 2. Jukněme na sloupce jako 2D vektory. Víme že 3 vektory v 2D prostoru musí být lineárně závislé. Takže existují 3 čísla x,y,tKx , y , t \in K taková že ne všechny najednou jsou 0 kde:

x(a1,a2)+y(b1,b2)+t(c1,c2)=(0,0)x \left ( a_{1} , a_{2} \right ) + y \left ( b_{1} , b_{2} \right ) + t \left ( c_{1} , c_{2} \right ) = \left ( 0 , 0 \right )

Pokud toto přepíšeme pro každou souřadnici zvlášť, dostaneme že bod (x,y,t)\left ( x , y , t \right ) leží na obou přímkách!! (z definice ležení na přímce)

Zároveň ale protože rank matice je 2, musí existovat 2 lineárně nezávislé sloupce. Búno to jsou (a1,a2)\left ( a_{1} , a_{2} \right ) a (b1,b2)\left ( b_{1} , b_{2} \right ). To znamená že pro libovolný vektor (u,v)\left ( u , v \right )x(a1,a2)+y(b1,b2)=(u,v)x \left ( a_{1} , a_{2} \right ) + y \left ( b_{1} , b_{2} \right ) = \left ( u , v \right ) unikátní řešení.

Takže pokud se koukneme na tamtu rovnici znova:

x(a1,a2)+y(b1,b2)+t(c1,c2)=(0,0)x \left ( a_{1} , a_{2} \right ) + y \left ( b_{1} , b_{2} \right ) + t \left ( c_{1} , c_{2} \right ) = \left ( 0 , 0 \right )

pak první 2 čelny jsou zašpendlíkované na místě a jediná vůle je v posledním členu když ho škálujeme ttčkem. ALE to znamená že rovnice může vycházet jen pro jednu hodnotu tt!

Pozorování

2 body sdílí právě 1 přímku

Důkaz

stejně jako 2 přimky sdílí 1 bod

Pozorování

existují 4 body takové že každá přímka protne max 2

Důkaz

Třeba: (0,0,1),(0,1,0),(1,0,0),(1,1,1)\left ( 0 , 0 , 1 \right ) , \left ( 0 , 1 , 0 \right ) , \left ( 1 , 0 , 0 \right ) , \left ( 1 , 1 , 1 \right ) i think

Latinský čtverec

Definice: Latinský čtverec řádu nn

čtvercová tabulka nn řádků a nn sloupců. V každém políčku je jedno číslo od 11 do nn.

Každé číslo se objevuje právě jednou v každém sloupečku a právě jednou v každém řádku.

Definice: Ortogonalita latinského čtverce

Když vezmu 2 a transparentně je položím na sebe, v každém z n2n^{2} políček dostanu dvojici čísel. Tyto 2 LČ jsou ortogonální pokud se žádná dvojice nezopakuje.

(Jelikož dvojic je n2n^{2}, každá dvojice se ve skutečnosti musí objevit právě jednou)

Pozorování

Počet ortogonálních latinských čtverců řádu nn je maximálně n1n - 1

Důkaz

Nejprve pozorování: Budiž ortogonální latinské čtverce AA a BB oba řádu nn a π\pi permutace čísel 1,2,,n1 , 2 , \ldots , n.

Vyrobíme nový latinský čtverec AA '. Ten bude mít na pozici (i,j)\left ( i , j \right ) číslo π(aij)\pi \left ( a_{i j} \right ) (kde aija_{i j} je pozice (i,j)\left ( i , j \right ) v LČ AA).

Po rozmyšlení je vidět že i AA ' je ortogonální k BB. Tudíž:

Pozorování

Ortogonalita LČ se nezmění přejmenováním symbolů v jednom z nich.

Představme si latinské čtverce A1,A2,,AtA_{1} , A_{2} , \ldots , A_{t} každé 2 z nich ortogonální.

Pro každé AiA_{i}: permutujme jeho symboly tak aby měl na prvním řádku bylo 1,2,,n1 , 2 , \ldots , n.

Podle pozorování víme, že i tyto A1,A2,,AtA '_{1} , A '_{2} , \ldots , A '_{t} jsou každý s každým ortogonální.

Jukněme, co může být na pozici (2,1)\left ( 2 , 1 \right ) některého AiA '_{i}:

  • určitě ne 11. Ta už je ve stejném sloupci na (1,1)\left ( 1 , 1 \right ).
  • žádné 2 Ai,AjA '_{i} , A '_{j} tam nemůžou mít stejné číslo. Kdyby tam měli stejné číslo, jejich dvojice by na (2,1)\left ( 2 , 1 \right ) měla dvojici (k,k)\left ( k , k \right ) ale ta se už objevila na kktém místě prvního řádku! tudíž 2,3,,n2 , 3 , \ldots , n mohou být na pozici (2,1)\left ( 2 , 1 \right ) pouze v jednom AiA '_{i} takže tn1t \le n - 1. 🔲
Pozorování

Pro n2n \ge 2 existuje FPR řádu nn pokudd existuje n1n - 1 navzájem ortogonálních LČ řádu nn.

Důkaz

Nejprve sestrojíme FPR řádu nn z n1n - 1 navzájem ortogonálních LČ řádu nn.

Jako template vezmem fancy tvar:


a teď si všimni že tam je dost bodů ale málo čar. Takže podle těch LČ které jsme stále nepoužili budeme proplétat nové přímky tím gridem vpravo dole.

Pro každé m{1,2,,n}m \in \left \lbrace 1 , 2 , \ldots , n \right \rbrace a k{1,2,,n1}k \in \left \lbrace 1 , 2 , \ldots , n - 1 \right \rbrace vyrobíme přímku:

Lkm={sk}{(i,j)(Sk)ij=m}L_{k m} = \left \lbrace s_{k} \right \rbrace \cup \left \lbrace \left ( i , j \right ) \mid \left ( S_{k} \right )_{i j} = m \right \rbrace

Tzn: Začneme přímku v sks_{k} a tam kde má LČ kk políčko s číslem mm appendneme do přímky.

Tohle je určitě FPR (důkaz vymysli na místě). Jde provést pozpátku pro vytvoření LČ z FPR. Stačí vybrat rr a cc libovolně.🔲

Numberphile video about M.O.L.S.

Toky v sítích

Takovej speedrun protože to určitě umíme.

Definice: Síť + tok

Síť je čtveřice (G,s,t,c)\left ( G , s , t , c \right ). GG je graf (dvojice množiny vrcholů a relace), ss a tt jsou vrcholy (source a sink) a c je funkce z hran do [0,+]\left [ 0 , + \infty \right ].

Tok je pak funkce ff která dává hranám ohodnocení.

Pravidla pro toky:

val(f)v a l \left ( f \right ) je velikost toku, třeba přebytek ve stoku

Pozorování

Každá síť má maximální tok - sketch, asi přes rozbor algoritmu xd

Definice: Řez

Řez je množina hran po jejichž odstranění se graf rozpadne na více komponent

Definice: Elementární řez (partition)

Je to vlastně to samý, ale komponenty musí být 2. Obv zdroj je v A a stok je v B. val(f)=f(A,B)f(B,A)v a l \left ( f \right ) = f{\left ( A , B \right )} - f{\left ( B , A \right )}

Pozorování
  1. elementární řez je taky řez a
  2. Každý řez obsahuje elementární řez.
Důkaz

Takový hrátky z cestami. v (i) si pořidíme cestu z ss do tt a říkáme, že jedna z hran této cesty je v řezu. To je vidět, protože ss a tt jsou v jiných komponentách.

ve (ii) je to to samé. Máme řez RR. Pořídíme AA a BB, A bude množina vrcholů do kterých se dá dostat v GRG - R z ss a BB bude její doplněk. Pak tvrdíme že S(A,B)RS \left ( A , B \right ) \subset R. Kdyby nebyl, tak existuje hrana v (x,y)Sr\left ( x , y \right ) \in S r, xAx \in A a yBy \in B. Pak ale cesta do y nekřižuje R, tedy je ve stejné komponentě jako ss a tedy musí být v AA.

Ano, je to kokotina.

Pozorování

val(f)c(R)v a l \left ( f \right ) \le c \left ( R \right )

Důkaz

Zadefinujeme přebytek na vrcholu -tj. rozdíl mezi přítokem a odtokem. Tento rozdíl je pak roven fΔ(A,B)=vBfΔ(v)=fΔ(t)f^{\Delta}{\left ( A , B \right )} = \sum_{v \in B} f^{\Delta}{\left ( v \right )} = f^{\Delta}{\left ( t \right )}. První rovnost rozborem případů kudy vede hrana, druhá rovnost je triviální - všechny vrcholy mají přebytek 0.

Zlepšující hrany (augmenting path), věta o tom že maximální tok je roven minimálnímu řezu. [P 4.2.5], známe z primy.

Ford-Fulkerson algoritmus hledá cesty v síti rezerv. Když ji najde, tak ji přičte do toku. Na celočíselných hranách se zastaví a vydá maximální tok. (bez důkazu)

[P: chapter 4.4, 4.5]

Definice: Systém různých reprezentantů

Nechť MM je konečný systém konečných množin. Nechť NN je sjednocení všech množin mMm \in M . Potom funkci f:MNf{:} M \to N nazveme systém různých reprezen- tantů právě tehdy, když je prostá a současně mM:f(m)m\forall m \in M : f{\left ( m \right )} \in m.

Definice: Párování

Buď G=(V,E)G = \left ( V , E \right ) graf a buď MEM \le E množina dvojic vrcholů GG. Pak MM nazveme párování v grafu GG právě tehdy, když je každý vrchol GG v nejvýše jedné dvojici v MM.

Věta: Hallova

Nechť MM je konečný systém konečných množin. Pak platí, že MM má systém různých reprezentantů právě tehdy, když pro každou FMF \subseteq M a sjednocení všech jejích prvků F\cup F platí |F||F|\left | \cup F \right | \ge \left | F \right | .

Věta: Hallova, bipartitní formulace

Nechť G = (V, E) je bipartitní graf s parti tami X a Y . Pak má G párování obsahující všechny vrcholy partity X právě tehdy, když pro každou M ⊆ X platí, že z ní vedou hrany k alespoň |M | různým vrcholům Y.

Pozorování

König-Egerváry theorem

Velikost maximálního párování v bipartitním grafu je rovna minimální velikosti vrcholového pokrytí (proof ommited, ale docela obvious). N

Grafová souvislost

[P: chapter 5.1, 5.2]

Definice: Vrcholová souvislost kv(G)k_{v} \left ( G \right )

Pokud GG je KnK_{n} pak to je n1n - 1 JINAK

kv(G)k_{v} \left ( G \right ) je velikost nejmenšího vrcholového řezu AA.

Definice: Hranová souvislost ke(G)k_{e} \left ( G \right )

ke(G)k_{e} \left ( G \right ) je velikost nejmenšího hranového řezu.

Definice: Hranově/Vrcholově souvislý

GG je hranově/vrcholově kk-souvislý pokud ke/v(G)kk_{e / v} \left ( G \right ) \ge k.

Pozorování

Pro graf GG s alespoň 2 vrcholy:

(eE(G))(ke(G)1ke(Ge)ke(G))\left ( \forall e \in E \left ( G \right ) \right ) \left ( k_{e} \left ( G \right ) - 1 \le k_{e} \left ( G - e \right ) \le k_{e} \left ( G \right ) \right )

“Odebráním libovolné hrany se kek_{e} může jedině snížit a to maximálně o 1”

(FE(G))(ke(GF)ke(G))\left ( \forall F \subseteq E \left ( G \right ) \right ) \left ( k_{e} \left ( G - F \right ) \le k_{e} \left ( G \right ) \right )

“Odebráním libovolné množiny hran se kek_{e} může jedině snížit”

Důkaz

To první jistě plyne z toho druhého

Pozorování

ke(G)k_{e} \left ( G \right ) se po odebrání hrany sníží maximálně o 1 (ke(Ge)ke(G)1k_{e} \left ( G - e \right ) \ge k_{e} \left ( G \right ) - 1)

Důkaz
  • Vezmeme ke(G)2k_{e} \left ( G \right ) - 2 velkou FE(Ge)F \subseteq E \left ( G - e \right )
  • Pak F=F{e}F ' = F \cup \left \lbrace e \right \rbrace.
  • Takže |F|ke(G)1\left | F ' \right | \le k_{e} \left ( G \right ) - 1.

Z toho plyne že (Ge)F\left ( G - e \right ) - F je spojitý. ale $abs(F’)

Graph connectivity cont’d and double counting

[P: chapter 5.3] and [P: chapter 6.3, 6.4]

Pozorování

Graf je vrcholově 2-souvislý právě tehdy když zle sestrojit z cyklu kterému přilepujeme uši. (Ear lemma, ušní lema, ušizmus)

Důkaz

\Rightarrow:

Cyklus je jistě vrcholově 2-souvislý. Přidáním ucha nemůže vzniknout vrchol takový že po jeho odebrání se graf rozpadne.

\Leftarrow:

Budiž graf GG který je vrcholově 2-souvislý. K němu vyrobíme co největší podgraf HH který jsme vytvořili z cyklu a přilepování uší.

Tvrdím, že HH je indukovaný podgraf. Pokud ne, pak existuje dvojice vrcholů mezi kterýma nevede hrana v HH ale vede hrana v GG. Pak ale HH není největší možný. Tudíž HH musí být indukovaný.

Předpokládám že existuje vrchol, který je v GG ale není v HH. Jelikož GG je souvislý. Musí existovat dvojice vrcholů uu, vv která sousedí a uu je v HH ale vv ne.

Jelikož je GG vrcholově 2-souvislý, po odebrání uu se nemůže rozpadnout. Tudíž stále existuje cesta z vv do uu. To je ale ucho které jsme měli přidat takže všechny vrcholy GG jsou v HH.

Jelikož HH a GG mají stejné vrchly a jelikož HH je indukovaný podgraf, musí to být stejné grafy. 🔲

Ramseyho teorie

Když máme dost velkou hromadu věcí tak v ní musí být nějaká struktura - Pepík

(syntax shugar: [n]:={1,2,,n}\left [ n \right ] := \left \lbrace 1 , 2 , \ldots , n \right \rbrace)

Pozorování

Pigeonhole principle

Množina [1+n1+n2++nt]\left [ 1 + n_{1} + n_{2} + \cdots + n_{t} \right ] kde každý prvek je obarvený jednou z tt barev.

Pak existuje barva ii která se objeví ni+1\ge n_{i} + 1-krát

Důkaz

Pokud ne, pak je obarveno jen n1+n2++nt\le n_{1} + n_{2} + \cdots + n_{t} koulí.

Pozorování

6-členná party

Pokdu obarvíme hrany K6K_{6} červeně a modře, pak existuje jednobarevný trojúhelník.

Důkaz

(Note: nefunguje pro K5K_{5}. (pentagon s hvězdou uprostřed))

Vem vrchol. Koukni na 5 odchozích vrcholů. 3 z nich musí mít stejnou barvu BÚNO červená.

Teď jukni na tyhle 3 vrcholy. Můžou se stát 2 věci:

  • Nějaké 2 mají taky červenou hranu mezi sebou takže výhra
  • žádné 2 nemají červenou hranu mezi sebou takže! všechny 3 mají mezi sebou modrou hranu, což tvoří modrý trojúhelník.
Definice: Ramseyho číslo R(k,l)R \left ( k , l \right )

R(k,l)R \left ( k , l \right ) je nejmenší možné číslo takové, že kdykoliv obarvujeme hrany grafu KR(k,l)K_{R \left ( k , l \right )} červeně a modře, pak existuje buď:

  • podgraf KkK_{k} kde jsou všechny hrany červené NEBO
  • podgraf KlK_{l} kde jsou všechny hrany modré.

(Poznámka: graf ve kterém hledáme musí být úplný. Grafy které hledáme musí být úplné)

Note: R(3,3)=6R \left ( 3 , 3 \right ) = 6 (6-členná party)

Pozorování

(Ramsey pro hrany a 2 barvy)

(a,b1)(R(a,b)(a1+b1a1))\left ( \forall a , b \ge 1 \right ) \left ( R \left ( a , b \right ) \le \left ( \begin{matrix} a - 1 + b - 1 \\ a - 1 \end{matrix} \right ) \right )

Důkaz

Indukcí po a+ba + b.

Init: pro a=1a = 1 nebo b=1b = 1 pak K1K_{1} funguje haha. (bo K1K_{1} má 0 hran takže pro ně platí všechno)

Indukční předpoklad:

  • R(a1,b)(a2+b1a2)R \left ( a - 1 , b \right ) \le \left ( \begin{matrix} a - 2 + b - 1 \\ a - 2 \end{matrix} \right )
  • R(a,b1)(a1+b2a1)R \left ( a , b - 1 \right ) \le \left ( \begin{matrix} a - 1 + b - 2 \\ a - 1 \end{matrix} \right )

Budiž n=R(a1,b)+R(a,b1)n = R \left ( a - 1 , b \right ) + R \left ( a , b - 1 \right ) a vem KnK_{n}

Teď to přepíšeme aby to vypadalo holubníkovitě:

n1=1+Jedna extra hrana(R(a1,b)1)+(R(a,b1)1)n - 1 = \underbrace{1 +}_{\text{Jedna extra hrana}} \left ( R \left ( a - 1 , b \right ) - 1 \right ) + \left ( R \left ( a , b - 1 \right ) - 1 \right )

Vem vv, vrchol KnK_{n}, a zase jukni na jeho hrany. Holub tvrdí že bude:

  1. R(a1,b)\ge R \left ( a - 1 , b \right ) červených hran NEBO
  2. R(a,b1)\ge R \left ( a , b - 1 \right ) modrých hran.

Pokud 1. pak z předpokladu víme že:

  • buď červený sousedi obsahují červenou Ka1K_{a - 1}, pak po přidání vv dostaneme červenou KaK_{a}
  • nebo červený sousedi obsahují modrou KbK_{b}, pak yay.

Jinak 2. pak analogicky pro modré sousedy.

Pozorování

lower bound R(k,k)R \left ( k , k \right )

(k3)(R(k,k)>2k2)\left ( \forall k \ge 3 \right ) \left ( R \left ( k , k \right ) > 2^{\frac{k}{2}} \right )

Důkaz

Chňapni KnK_{n} kde n2k2n \le 2^{\frac{k}{2}} a obarvi všechny hrany nezávisle.

Tohle nemusí fungovat obv ALE

Jak často se stane, že když vyberu množinu XX o kk vrcholech pak mají všechny stejnou barvu? well this: (12)(k2)+(12)(k2)\left ( \frac{1}{2} \right )^{\left ( \begin{matrix} k \\ 2 \end{matrix} \right )} + \left ( \frac{1}{2} \right )^{\left ( \begin{matrix} k \\ 2 \end{matrix} \right )}

Jaká je šance že nějaký kk-prvková množina vrcholů má všechny hrany stejné? well \le než počet kk-prvkových množin Pfail\cdot P_{\text{fail}}

něco něco idk nemám rád pravděpodobnost

IF YOU HAVE A SUFFICIENT AMOUNT OF BALLS

Definice: (xp)\left ( \begin{matrix} x \\ p \end{matrix} \right )

Budiž množina XX a pp \in \mathbb{N}.

(xp)\left ( \begin{matrix} x \\ p \end{matrix} \right ) je množina všech pp-prvkových podmnožin XX.

Pozorování

Nekonečná verze Ramseyovy věty pro hypergrafy (bro jestli tohle nezní cool tak idk)

Pro libovolné obarvení (P)\left ( \begin{matrix} \mathbb{N} \\ P \end{matrix} \right ) pomocí tt barev (barva je vlastnost podmnožiny)

existuje nekonečná množina AA \subseteq \mathbb{N} kde Q(AP)\forall Q \in \left ( \begin{matrix} A \\ P \end{matrix} \right ) dostanou stejnou barvu.

Důkaz

Indukce podél pp. Pro p=1p = 1, barvíme \mathbb{N} pomocí tt barev, takže nějaká barva se objeví nekonečně mnoho krát.

Řekněme že pro pp, vem p+1p + 1.

Nechť C:(p+1)[t]C : \left ( \begin{matrix} \mathbb{N} \\ p + 1 \end{matrix} \right ) \to \left [ t \right ] je barvení všech (p+1)\left ( p + 1 \right )-tic pomocí barev 1,2,,t1 , 2 , \ldots , t.

postavíme podmnožiny A1A2A3A_{1} \supseteq A_{2} \supseteq A_{3} \supseteq \ldots kde A1=A_{1} = \mathbb{N} a v1,v2,v_{1} , v_{2} , \ldots \in \mathbb{N} kde v1=1v_{1} = 1.

Pak předpokládáĺe že už máme A1,A2,,AiA_{1} , A_{2} , \ldots , A_{i} a v1,v2,,viv_{1} , v_{2} , \ldots , v_{i} \in \mathbb{N}. Definujeme c:(Ai?p)c ' : \left ( \begin{matrix} A_{i} \, ? \\ p \end{matrix} \right ) přiřazením barvy c(Q)c \left ( Q \cup \right )pp-tici QQ.

Indukcí, najdi nekonečnou podmnožinu $A_i+2 sube A_i$ tak že všechny
$p$-prvkové podmnožiny dostanou stejnou barvu.
Pozorování

König lemma (O nekonečných stromech)

(důkaz nebude ve zkoušce)

Pokud TT je nekonečný strom se všemi stupni konečnými.

Čapni libovolný vrchol. Pak existuje nekonečná cesta po TT z tohoto bodu.

(jakože lol obviously wtf)

Důkaz

(sketch) Vem vrchol x0x_{0} jako kořen. ten má konečně mnoho sousedů. Jukněme na ně. Součet jejich velikostí je nekonečno. takže alespoň jeden ze sousedů musí být nekonečný strom. takže půjdeme tam. Ez done

Vibe: A teď tohle umí spoutat konečné a nekonečné struktury

Pozorování

Ramsey pro hypergrafy, konečný (still cool)

Vem p,t,k1,,ktp , t , k_{1} , \ldots , k_{t} \in \mathbb{N}. Pak existuje konečné číslo Rp(k1,,kt)R_{p} \left ( k_{1} , \ldots , k_{t} \right ) takové že kdykoliv obarvujeme ([n]p)\left ( \begin{matrix} \left [ n \right ] \\ p \end{matrix} \right ) kde nRp(k1,,kt)n \ge R_{p} \left ( k_{1} , \ldots , k_{t} \right ) pak

#(Dec 17): Ramsey theory, cont’d [P: chapter 7.3].:

Věta: Happy ending problem

Pro jakoukoliv množinu pěti bodů v rovině v obecné poloze (ne 3 na přímce) tvoří alespoň jedna čtveřice konvexní čtyřúhelník.

Důkaz

Vezmeme kovexní obal (covex hull) těchto pěti bodů. (i) Pokud je to pětiúhelník -> jakékoliv 4 dělají konvexní čtyřúhelník. (ii) Pokud je to čtyřúhelník, tak ty čtyři na okraji Předpokládejme tedy že obal je trojúhelník. Ostatní dva body nemůžou ležet na jeho okraji (obecná poloha), ale uvnitř.

Vezmeme tedy jeden a postavíme 6 částí jako na obrázku. Podle toho v jaké části leží a5a_{5} vybereme zbývající dva vrcholy trojúhelníku společně s a4a_{4} a máme hotovo. a5a_{5} opět nemůže ležet mezi částmi, kvůli obecné poloze.

Věta: Erdős-Szekeres theorem

Pro t4t \ge 4, jakákoliv mnozina R4(5,t)R^{4} \left ( 5 , t \right ) bodů v rovině v obecné poloze obsahuje alespoň tt bodů tvořící konvexní čtyřúhelník.

Důkaz

Pořídíme si množinu SS R4(5,t)R^{4} \left ( 5 , t \right ) bodů v rovině. V ní obarvíme všechny čtveřice c:(S4)[2]c : \left ( \begin{matrix} S \\ 4 \end{matrix} \right ) \to \left [ 2 \right ] tak, že

  • c(X)=1c \left ( X \right ) = 1, tak netvoří konvexní čtyřúhelník
  • c(X)=2c \left ( X \right ) = 2, tak tvoří konvexní čtyřúhelník

Množství bodů (Ramseyovo číslo) nám teď říká, že:

  • existuje pětice taková, že každá čtveřice z pětice má barvu 1 NEBO
  • existuje t-tice taková, že každá čtveřize z t-tice má barvu 2.

První případ se nemůže stát, je to přímá negace Happy-ending problému. Takže určitě existuje nějaká t-tice A2A_{2}, ve které X(A24):c(X)=2\forall X \in \left ( \begin{matrix} A_{2} \\ 4 \end{matrix} \right ) : c \left ( X \right ) = 2. Vezměme konvexní obal této A2A_{2}. Pokud má t vrcholů, tak jsme vyhráli. Pokud má měné než t vrcholů, tak existuje nějaký vrchol zz, co je uvnitř. To znamená že existují nějaké body x1,x2,x3x_{1} , x_{2} , x_{3} které tvoří trojúhelník ve kterém je zz uzavřeno.

Tato čtveřice bodů ale netvoří čtyřúhelník, což je spor, protože mají barvu 2.

Error-correcting codes

[P: chapter 8]

Motivační příklad. Pojďme si posílat zprávy. Komunikační linka je ale nestabilní a mění nám znaky za jiné. Chtěli bychom za málo poslaných znaků navíc dokázat opravit co nejvíce takto změněných znaků.

Pro jednoduchost pojďme posílat bity. Náš jazyk má tedy pouze dva znaky. Abychom, dokázali opravit nějakou chybu, každý bit co pošleme ztrojíme. Místo “1101” pošleme “111111000111”. Jakýkoliv změněný bit dokážeme opravit, protože druhé dva ve trojici zůstanou nezměněny. Pokud ale někdo změní dva bity, můžeme mít smůlu a kód opravit špatně.

Definice: Primitivy
  • abeceda (alphabet) je konečná množina znaků Σ={s0,,sm}\Sigma = \left \lbrace s_{0} , \cdots , s_{m} \right \rbrace - abeceda často bude nějaké konečné těleso, nejčastěji F2F_{2}
  • slovo délky nn je seznam (nebo řádkový vektor) nn znaků z abecedy
  • Σn\Sigma^{n} je množina všech slov délky nn z abecedy Σ\Sigma
  • kód CC je podmnožina Σn\Sigma^{n}.
  • prvky kódu jsou codewords, for the lack of neat translation
Definice: Hammingova vzdálenost

Je to jednoduše počet rozdílných znaků ve dvou slovech. Formálně x,yΣn,d(x,y):=|{i{1,,n}xiyi}|\forall x , y \in \Sigma^{n} , d \left ( x , y \right ) := \left | \left \lbrace i \in \left \lbrace 1 , \cdots , n \right \rbrace \mid x_{i} \ne y_{i} \right \rbrace \right | Rozmysli si, že je to metrika na Σn\Sigma^{n}.

Definice: Hamming weight (váha?)

Je definovaná jako počet “nenulových” znaků, nebo Hammingova vzdálenost od nulového vektoru.

Jak se tyto primitivy používají?

S je odesílatel, R je přijímač. S i R znají nějakou bijekci π\pi mezi všemy kódy CΣnC \subset \Sigma^{n} a všemi možnými zprávami. Je to bijekce, tedy množina kódů a všech zpráv jsou stejně velké. Všechny zprávy budou tipicky kratší než n, jinak by to byl docela naprd kód.

S tedy vezme zprávu, přeloží ji na kód a pošle R. R zprávu přijme, možná s nějakými chybami. Opraví ji a pomocí π1\pi^{- 1} ji přeloží zpátky na zprávu.

Definice: (n,k,d)q\left ( n , k , d \right )_{q} kód

Předpokládejme abecedu o alespoň dvou znacích a C je kód s alespoň dvěma codewords. Tento kód má pak nějaké parametry.

  • nn = délka slov v CC
  • qq = velikost abecedy (|Σ|\left | \Sigma \right | )
  • kk = velikost CC je |C|\left | C \right | , užitečnější ale bude logaritmus o základu q. k=logq|C|k = \log_{q}{\left | C \right | }
  • dd = minimální vzdálenost v CC (min({d(x,y)(x,yC)(xy)})\min \left ( \left \lbrace d \left ( x , y \right ) \mid \left ( x , y \in C \right ) \left ( x \ne y \right ) \right \rbrace \right ))

To nám dává (n,k,d)q\left ( n , k , d \right )_{q} kód. Rozmysli si, kolik dokážeme v takovém kódu opravit chyb.

řešení d12\left \lfloor \frac{d - 1}{2} \right \rfloor

Příklady kódů. Náš opakující se kód ze začátku byl (n,1,n)qkód\left ( n , 1 , n \right )_{q} - k ó d, kde n je “činitel” (slova jsou roznásobené znaky). Slova jsou dlouhá nn, to si můžeme zvolit jak chceme. Množina kódů je stejně velká jako abeceda, protože akorát vezme každý znak z abecedy a dá ho nnkrát za sebou. kk je tedy 1, protože je to logq(q)\log_{q}{\left ( q \right )}. Minimální vzdálenost bude přesně d=nd = n, protože každá dvě slova jsou kompletně jiná.

Rozmysli si, co je za kód co nic nedělá. Pouze pošle slovo nad nějakou abecedou Σ\Sigma velikosti qq délky nn. Nijak ho nepřeloží.

Hint: nn je zadané, k=logq(|C|)k = \log_{q}{\left ( \left | C \right | \right )} -> kolik je |C|\left | C \right | ? d=d = minimální vzdálenost dvou kódů.

Řešení: (n,n,1)q\left ( n , n , 1 \right )_{q}. To protože kódů je qnq^{n} - jsou to všechny zprávy. Vzdálenost dvou kódů je malá, pouze 1.

Parity code. q=2q = 2 a naše kódy budou mít vždy součet =0= 0 nad 2\mathbb{Z}_{2}. Tento kód bude (n,n1,2)2\left ( n , n - 1 , 2 \right )_{2} kód. |C|=2n1\left | C \right | = 2^{n - 1}, prvních n1n - 1 znaků si můžeme vybrat a poslední určíme tak, aby byl součet co nejmenší. k=log2(2n1)=n1k = \log_{2}{\left ( 2^{n - 1} \right )} = n - 1. Vzdálenost dd je 2, protože dva kódy nemůžou mít vzdálenost 1, to by znamenalo že jeden z nich má součet =1= 1.

Teďka se řeší nějaký boundy na to, jak velký můžou bejt ty množiny kódů (jakoby kk), když nám někdo zadá n,d,q. Upřímně doufám že to ommitne protože to sou fakt hovna xd.

Definice: Singleton bound, Hamming bound, Gilbert-Varshamov bound,

ommited by Džanek, read up on [P 8.3]

Definice: Linear codes

Lineární kód je podprostor prostoru ZqnZ_{q}^{n}. Pokud je to také (n,k,d)q\left ( n , k , d \right )_{q} kód, tak se píše do hranatých závorek, je totiž důležitej :)

Těmi kódy co posíláme jsou opravdu myšleny vektory toho podprostoru. Čím větší si vezmu, tím má větší dimenzi a tím se mi zvětšuje kk. Ale kvůli tomu bude menší dd. Ještě existuje pojem generator matrix - to jsou bazické vektory CC nasázené do sloupce. Z toho se dá vyrobit parity check - to je taky matice, ale tentokrát báze kolmých vektorů.

Vynásobením xHx H lze jednoduše ověřit, jestli xx do C patří, či nikoliv.

Pozorování

Pokud je CC an [n,k,d]q\left [ n , k , d \right ]_{q}-kód, tak dim(C)=k\dim \left ( C \right ) = k

Důkaz

Pořiďme si l:=dim(C)l := \dim \left ( C \right ). {c1,,cl}\left \lbrace c_{1} , \cdots , c_{l} \right \rbrace jsou bazické vektory CC. CC je nyní složené z lineárních kombinací těchto vektorů i=0laici\sum_{i = 0}^{l} a_{i} c_{i}. Pro každé aia_{i} máme qq možností jak si vybrat (protože |Fq|=q\left | F_{q} \right | = q). Jelikož jsou vektory lineárně nezávislé, tak je celkem qlq^{l} různých kódů.

Z toho k=logq(ql)=lk = \log_{q}{\left ( q^{l} \right )} = l 🔲

Pozorování

Pokud je CFqnC \subset F_{q}^{n} [n,k,d]q\left [ n , k , d \right ]_{q} - kód s 0<k<n0 < k < n, tak

d=min{wt(x)xC{0}}d = \min \left \lbrace w t \left ( x \right ) \mid x \in C \backslash \left \lbrace 0 \right \rbrace \right \rbrace

wt je Hammming weight - vzdálenost od 0.

Důkaz

Zafixujeme x0x \ne 0 s nejmenší hammingovskou váhou. Dokazujeme že d=wt(x)d = w t \left ( x \right ).

Jelikož CC je kód ve kterém je 0 i x, tak d(x,0)=wt(x)dd \left ( x , 0 \right ) = w t \left ( x \right ) \ge d z definice d - je nejmenší takové. V CC také existují různé vektory y,zy , z, jejichž d(y,z)=dd \left ( y , z \right ) = d. Jelikož CC je podprostor, tak yzCy - z \in C. Tudíž wt(x)wt(yz)w t \left ( x \right ) \le w t \left ( y - z \right ) - to víme protože x je nejmenší takové.

Celkově d=d(y,z)=wt(yz)wt(x)d = d \left ( y , z \right ) = w t \left ( y - z \right ) \ge w t \left ( x \right ). Složením nerovností 🔲.

Definice: Hamming bound

Když fixneme nn a dd tak kk musí být small.

(wait je tohle hamming code?)

$C sube Z_2^n je (n,k,d=2t+1)\left ( n , k , d = 2 t + 1 \right ) pak |C|2nV(t)\left | C \right | \le \frac{2^{n}}{V \left ( t \right )}.

Důkaz

Pro každé xCx \in C jukni na kouli Bn(x,t)B_{n} \left ( x , t \right ). Protože CCd=2t+1d = 2 t + 1, žádné 2 koule se nepřekrývají.

(slova, slova … důkaz že se nepřekrývají)

pak |C|>n2V(t)\left | C \right | > \frac{n^{2}}{V \left ( t \right )} protože velikost prostoru je 2n2^{n} a V(t)V \left ( t \right ) je volume koule a pokud se nepřekrývají tak něco něco

Gilbert-Varnshmdr Bound

v,d1C2nwithΔ(c)=d\forall v , d \ge 1 \exists C \in \mathbb{Z}_{2}^{n} w i t h \Delta \left ( c \right ) = d and |C|2nV(d1)\left | C \right | \ge \frac{2^{n}}{V \left ( d - 1 \right )}

Zdroje

uuuuwwwiieee