Numere catalane

Numerele catalane sunt o secvență de numere care apare în multe probleme de combinatorie .

Secvența este numită după matematicianul belgian Eugene Charles Catalan , deși era cunoscută și de Leonhard Euler .

Numerele catalane pentru formează șirul: $C_{n}$ $n=0,1,2,\puncte$

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, … (secvența A000108 în OEIS )

Definiții

Al n-lea număr catalan poate fi definit în mai multe moduri echivalente, cum ar fi [1] : $C_{n}$

Numărul de plăci ale unui convex ( n +2)-gon în triunghiuri prin diagonale care nu se intersectează .
Numărul de moduri de a conecta 2 n puncte dintr-un cerc cu n coarde care nu se intersectează .
Numărul de secvențe corecte de paranteze de lungime 2 n , adică astfel de secvențe de n paranteze stânga și n dreapta, în care numărul de paranteze de deschidere este egal cu numărul de paranteze de închidere și în oricare dintre parantezele sale nu există mai puțin paranteze de deschidere decât închiderea parantezelor.
- De exemplu, pentru n = 3 există 5 astfel de secvențe: ((())), ()(()), ()()(), (())(), (()()) adică . $C_{3}=5$

Numărul de tupluri ale n numere naturale , cum ar fi pentru . $(x_{1},x_{2},\ldots,x_{n})$ $x_1=1$ $x_{i}\leqslant x_{i-1}+1$ $2 \leqslant i \leqslant n$
Numărul de arbori binari ordonați neizomorfi cu o rădăcină și n + 1 frunze.
Numărul de moduri posibile de liniarizare a produsului cartezian a 2 mulțimi ordonate liniare: din 2 și din n elemente.
Numărul de căi Dick de la punctul (0,0) la punctul (n, n). [2]

Proprietăți

Numerele catalane satisfac relația recursivă : $C_{0}=1\quad$ iar pentru . $\quad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i)$ $n\geqslant 1$

Această relație este ușor de obținut din faptul că orice secvență de paranteze regulată nevide poate fi reprezentată în mod unic ca w = ( w 1 ) w 2 , unde w 1 , w 2 sunt secvențe regulate de paranteze.

Există o altă relație de recurență:

C_{0}=1\quad

și .

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

O altă formulă recursivă :

C_{0}=1\quad

și . Dacă punem , atunci obținem o recursivitate convenabilă pentru calcule , .

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

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}}

De aici rezultă: .

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

Există, de asemenea, o relație de recurență mai simplă: $C_{0}=1\quad$ și . $\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}$

Funcția generatoare a numerelor catalane este: $\sum _{n=0}^{\infty }C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.$

Numerele catalane pot fi exprimate în termeni de coeficienți binomi : $C_{n}={\frac {1}{n+1}}{2n \alegeți n}={\frac {1}{2n+1}}{2n+1 \alegeți n}={\ binom {2n}{n}}-{\binom {2n}{n-1}}.$

Cu alte cuvinte, numărul catalan este egal cu diferența dintre coeficientul binom central și triunghiul lui Pascal adiacent acestuia pe aceeași linie .

C_{n}

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

Vezi și

Note

↑ A. Spivak. numere catalane. — MTsNMO.
↑ Diagrame tinere, trasee pe o rețea și metoda reflexiilor M. A. Bershtein (ITF numit după Landau, IPPI numit după Kharkevich, NMU), G. A. Merzon (MTsNMO). 2014 (articol cu bibliografie)

Link -uri

S. K. Lando. Prelegeri despre combinatorică . - MTsNMO , 1994.
A. Shen. Secțiunile 2.6 și 2.7 // Programare: teoreme și probleme . — M.: MTsNMO , 2017.
Stanley, Richard P. (2013), addendum catalan la combinatorică enumerativă, volumul 2 , < http://www-math.mit.edu/~rstan/ec/catadd.pdf >
Weisstein, Eric W. Catalan Number (engleză) pe site-ul Wolfram MathWorld .