Katalánská čísla

Katalánská čísla jsou posloupnost čísel, která se vyskytuje v mnoha kombinatorických problémech .

Sekvence je pojmenována po belgickém matematikovi Eugenu Charlesi Catalanovi , ačkoli ji znal také Leonhard Euler .

Katalánská čísla tvoří posloupnost: $C_{n}$ $n=0,1,2,\tečky$

1 , 1 , 2 , 5 , 14 , 42 , 132 , 429 , 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … (sekvence A000108 v OEIS )

Definice

N-té katalánské číslo lze definovat několika ekvivalentními způsoby, například [1] : $C_{n}$

Počet obkladů konvexního ( n +2)-úhelníku na trojúhelníky neprotínajícími se úhlopříčkami .
Počet způsobů, jak spojit 2 n bodů na kružnici s n neprotínajícími se tětivami .
Počet správných závorkových sekvencí délky 2 n , tj. takových sekvencí n levých a n pravých závorek, ve kterých je počet otevíracích závorek roven počtu uzavíracích závorek a v kterékoli z jejich předpon není méně otevíracích závorek než uzavírací závorky.
- Například pro n = 3 existuje 5 takových sekvencí: ((())), ()(()), ()()(), (())(), (()()) to je . $C_{3}=5$

Počet n - tic n přirozených čísel jako pro . $(x_{1},x_{2},\ldots ,x_{n})$ $x_1=1$ $x_{i}\leqslant x_{i-1}+1$ $2 \leqslant i \leqslant n$
Počet neizomorfních uspořádaných binárních stromů s kořenem a n + 1 listy.
Počet možných způsobů linearizace kartézského součinu 2 lineárních uspořádaných množin: ze 2 az n prvků.
Počet Dickových cest z bodu (0,0) do bodu (n, n). [2]

Vlastnosti

Katalánská čísla splňují rekurzivní vztah : $C_{0}=1\quad$ a pro . ${\displaystyle \quad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i))$ $n\geqslant 1$

Tento vztah lze snadno získat ze skutečnosti, že libovolnou neprázdnou sekvenci v pravidelných hranatých závorkách lze jednoznačně reprezentovat jako w = ( w 1 ) w 2 , kde w 1 , w 2 jsou sekvence v pravidelných hranatých závorkách.

Existuje další vztah opakování:

C_{0}=1\quad

a .

\quad C_{n}={\binom {2n}{n}}-\sum _{k=0}^{n-1}C_{k}{\binom {2n-2k-1}{ nk}}

Další rekurzivní vzorec :

C_{0}=1\quad

a . Pokud dáme , pak dostaneme pohodlnou rekurzi pro výpočty , .

\left(n+1\right){{C}_{n}}={{4}^{n}}-{\frac {1}{2}}\sum \limits _{k= 0}^{n-1}{{{4}^{nk}}{{C}_{k}}}

{\displaystyle c_{n}={\frac {C_{n}}{4^{n))))

c_{0}=1

c_{n}={\frac {1}{n+1}}-{\frac {1}{2\left(n+1\right)))\sum \limits _{k=0} ^{n-1}{c_{k}}

Odtud vyplývá: .

\sum \limits _{k=0}^{\infty }{{\frac {C_{k}}{4^{k}}}=}\sum \limits _{k=0}^{ \infty }{c_{k}}=2

Existuje také jednodušší vztah opakování: $C_{0}=1\quad$ a . $\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}$

Generující funkce katalánských čísel je: $\sum _{n=0}^{\infty }C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.$

Katalánská čísla lze vyjádřit pomocí binomických koeficientů : $C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {1}{2n+1}}{2n+1 \choose n}={\ binom {2n}{n}}-{\binom {2n}{n-1}}.$

Jinými slovy, katalánské číslo se rovná rozdílu mezi centrálním binomickým koeficientem a Pascalovým trojúhelníkem , který k němu sousedí ve stejné linii .

C_{n}

Asymptoticky $C_{n}\sim {\frac {4^{n}}{n^{{3/2}}{\sqrt {\pi }}}}.$

Viz také

Poznámky

↑ A. Spivák. Katalánská čísla. — MTsNMO.
↑ Youngovy diagramy, dráhy na mřížce a metoda odrazů M. A. Bershtein (ITF pojmenovaná po Landauovi, IPPI po Charkeviči, NMU), G. A. Merzon (MTsNMO). 2014 (článek s bibliografií)

Odkazy

S. K. Lando. Přednášky z kombinatoriky . — MTsNMO , 1994.
A. Shen. Sekce 2.6 a 2.7 // Programování: Věty a problémy . — M.: MTsNMO , 2017.
Stanley, Richard P. (2013), katalánský dodatek k Enumerativní kombinatorice, svazek 2 , < http://www-math.mit.edu/~rstan/ec/catadd.pdf >
Weisstein, Eric W. Catalan Number (anglicky) na webových stránkách Wolfram MathWorld .