Catalanova čísla

Jsou počtem zakořeněných binárních stromů na $n$ vrcholech.

Pozorování: $\forall i\ge 1:b_0{b}_{i-1}+b_1{b}_{i-2}+\dots +b_{i-1}{b}_0={\sum }_{k=1}^{i-1}{b}_k{b}_{i-k-1}$, což je koeficient u $x^{i-1}$ u konvoluce Vytvořující funkce $b(x)\cdot b(x)$.

Chceme-li vytvořující funkci pro Catalanova čísla, tak nám $b(x{)}^2$ nestačí, protože chceme aby koeficient u $n$ odpovídal $n$ a ne $n-1$, tedy musíme řadu posunout a kompenzovat $b_0$, protože to má vyjít $1$ a ne $0$ a sice máme $b(x)=xb(x{)}^2+1$.

$$\begin{array}{rl}b(x)& =xb(x{)}^2+1\text{ meˇjme b(x) jako neznaˊmou a x jako parametr}\\ b(x{)}_{1,2}& =\frac{1\pm \sqrt{1-4x}}{2x}\text{ + v okolıˊ 0 koverguje zleva a zprava k jinyˊm hodnotaˊm}\\ b(x)& =\frac{1-{\sum }_{i=0}^{\infty }(-4{)}^i(\genfrac{}{}{0ex}{}{1/2}{i})x^i}{2x},\end{array}$$

v poslední rovnici aplikujeme na $(1-4x{)}^{1/2}$ důsledek Zobecněná binomická věta.

$$\begin{array}{rl}b(x)& =\frac{1-1-{\sum }_{i=1}^{\infty }(-4{)}^i(\genfrac{}{}{0ex}{}{1/2}{i})x^i}{2x}\\ & =-\frac{1}{2}\sum _{i=1}^{\infty }(-4{)}^i(\genfrac{}{}{0ex}{}{1/2}{i})x^{i-1}\\ b_n& =-\frac{1}{2}(-4{)}^{n+1}(\genfrac{}{}{0ex}{}{1/2}{n+1})x^n\text{, tedˇ naˊs zajıˊmaˊ jen konkreˊtnıˊ koeficient}\\ & \\ b_n& =\frac{1}{2}(-1{)}^n{2}^{2n+2}\frac{\frac{1}{2}\cdot \left(\frac{1}{2}-1\right)\cdot \stackrel{n-2}{\dots }\cdot \left(\frac{1}{2}-(n+1)-1\right)}{(n+1)!}\\ b_n& =\frac{1}{2}(-1{)}^n{2}^{2n+2}\frac{\frac{1}{2}\cdot \left(-\frac{1}{2}\right)\cdot \stackrel{n-2}{\dots }\cdot \left(-\frac{2n-1}{2}\right)}{(n+1)!}\text{ tedˇ roznaˊsobıˊme nasˇich n zaˊpornyˊch cˇlenu˚ pomocıˊ −1}\\ b_n& =\frac{1}{2}{2}^{2n+2}\frac{\frac{1}{2}\cdot \frac{1}{2}\cdot \stackrel{n-2}{\dots }\cdot \frac{2n-1}{2}}{(n+1)!}\text{ vsˇechny zlomky tedˇ roznaˊsobıˊme s 2}\\ b_n& =2^n\frac{1\cdot 1\cdot \stackrel{n-2}{\dots }\cdot (2n-1)}{(n+1)!}\cdot \frac{n!}{n!}\text{ distribuujeme 2 do cˇitatele s n!}\\ b_n& =\frac{1\cdot 3\cdot \dots \cdot (2n-1)}{(n+1)n!}\cdot \frac{2\cdot 4\cdot 6\cdot \cdots \cdot 2n}{n!}\\ b_n& =\frac{1}{n+1}\cdot \frac{(2n)!}{(n!{)}^2}\\ b_n& =\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\end{array}$$