Katalán számok

A katalán számok egy számsorozat , amely számos kombinatorikai feladatban előfordul .

A sorozat nevét Eugene Charles Catalan belga matematikusról kapta, bár Leonhard Euler is ismerte .

A sorozatot alkotó katalán számok : $C_{n}$ $n=0,1,2,\pontok$

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, … ( A000108 sorozat az OEIS -ben )

Definíciók

Az n- edik katalán szám többféle ekvivalens módon definiálható, például [1] : $C_{n}$

Egy konvex ( n +2)-szög háromszögekké alakított csempézéseinek száma nem metsző átlókkal .
Egy kör 2 n pontjának összekapcsolási módjainak száma n nem metsző akkorddal .
A 2 n hosszúságú helyes zárójelsorozatok száma , azaz olyan n bal és n jobb zárójelből álló sorozat, amelyben a nyitó zárójelek száma megegyezik a záró zárójelek számával, és bármelyik előtagjában nincs kevesebb nyitó zárójel mint a zárójelek.
- Például n = 3 esetén 5 ilyen sorozat létezik: ((())), ()(()), ()()(), (())(), (()()) vagyis . $C_{3}=5$

Az n természetes számból álló sorok száma , például : . $(x_{1},x_{2},\ldots ,x_{n})$ $x_1=1$ $x_{i}\leqslant x_{i-1}+1$ $2 \leqslant i \leqslant n$
A gyökérrel és n + 1 levelű , nem izomorf rendezett bináris fák száma.
2 lineárisan rendezett halmaz derékszögű szorzatának linearizálásának lehetséges módjainak száma : 2 és n elemből.
Dick-utak száma (0,0) ponttól (n, n) pontig. [2]

Tulajdonságok

A katalán számok kielégítik a rekurzív relációt : $C_{0}=1\quad$ és . _ ${\displaystyle \quad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i))$ $n\geqslant 1$

Ez az összefüggés könnyen megállapítható abból a tényből, hogy bármely nem üres szabályos zárójelsorozatot egyedileg ábrázolhatunk w = ( w 1 ) w 2 -ként , ahol w 1 , w 2 szabályos zárójelsorozatok.

Van még egy ismétlődő kapcsolat:

C_{0}=1\quad

és .

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

Egy másik rekurzív képlet :

C_{0}=1\quad

és . Ha feltesszük , akkor kényelmes rekurziót kapunk a számításokhoz , .

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

Innen következik: .

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

Van egy egyszerűbb ismétlődési összefüggés is: $C_{0}=1\quad$ és . $\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}$

A katalán számok generáló függvénye : $\sum _{n=0}^{\infty }C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.$

A katalán számok binomiális együtthatókkal fejezhetők ki : $C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {1}{2n+1}}{2n+1 \choose n}={\ binom {2n}{n}}-{\binom {2n}{n-1}}.$

Más szóval, a katalán szám egyenlő a középső binomiális együttható és az ugyanabban a sorban szomszédos Pascal-háromszög különbségével .

C_{n}

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

Lásd még

Jegyzetek

↑ A. Spivak. Katalán számok. — MTsNMO.
↑ Fiatal diagramok, pályák rácson és a reflexiók módszere M. A. Bershtein (ITF Landau, IPPI Harkevich, NMU), G. A. Merzon (MTsNMO). 2014 (cikk bibliográfiával)

Linkek

S. K. Lando. Előadások a kombinatorikáról . – MTsNMO , 1994.
A. Shen. 2.6 és 2.7 szakasz // Programozás: Tételek és feladatok . — M.: MTsNMO , 2017.
Stanley, Richard P. (2013), Katalán addendum to Enumerative Combinatorics, 2. kötet , < http://www-math.mit.edu/~rstan/ec/catadd.pdf >
Weisstein, Eric W. Katalán szám (angolul) a Wolfram MathWorld webhelyén .