Katalonian numerot

Katalaaniluvut ovat lukujonoja , joita esiintyy monissa kombinatorisissa tehtävissä .

Sarja on nimetty belgialaisen matemaatikon Eugene Charles Catalanin mukaan, vaikka sen tunsi myös Leonhard Euler .

Katalonialaiset numerot muodostavat sarjan: $C_{n}$ $n = 0,1,2,\pisteet$

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, … (sekvenssi A000108 OEIS : ssä )

Määritelmät

Katalonian n: s luku voidaan määritellä useilla vastaavilla tavoilla, kuten [1] : $C_{n}$

Kuperan ( n +2)-kulmion laatoitusten määrä kolmioksi ei-leikkaavien diagonaalien avulla .
Kuinka monta tapaa yhdistää 2 n pistettä ympyrässä, jossa on n ei-leikkautuvaa jännettä .
Oikeiden 2 n pituisten hakasulkujen lukumäärä , eli sellaiset n vasemman ja n oikean hakasulkujen sekvenssit, joissa aloitussulkeiden lukumäärä on yhtä suuri kuin sulkevien sulujen lukumäärä ja missä tahansa sen etuliitteessä ei ole vähemmän aloitussulkuja kuin sulkumerkit.
- Esimerkiksi arvolle n = 3 on 5 tällaista sekvenssiä: ((())), ()(()), ()()(), (())(), (()()) eli . $C_{3}=5$

n luonnollisen luvun monikoiden määrä , kuten . _ $(x_{1},x_{2},\ldots ,x_{n})$ $x_1=1$ $x_{i}\leqslant x_{i-1}+1$ $2 \leqslant i \leqslant n$
Niiden ei- isomorfisten binääripuiden lukumäärä , joissa on juuri ja n + 1 lehtiä.
Mahdollisten tapojen lukumäärä linearisoida 2 lineaarisen järjestetyn joukon karteesinen tulo : 2:sta ja n :stä alkiosta.
Dick-polkujen määrä pisteestä (0,0) pisteeseen (n, n). [2]

Ominaisuudet

Katalonian luvut täyttävät rekursiivisen suhteen : $C_{0}=1\quad$ ja . _ ${\displaystyle \quad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i))$ $n\geqslant 1$

Tämä suhde on helppo saada siitä tosiasiasta, että mikä tahansa ei-tyhjä säännöllinen hakasulkusekvenssi voidaan esittää yksiselitteisesti muodossa w = ( w 1 ) w 2 , missä w 1 , w 2 ovat säännöllisiä hakasulkeiden sekvenssejä.

On toinenkin toistuvuussuhde:

C_{0}=1\quad

ja .

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

Toinen rekursiivinen kaava :

C_{0}=1\quad

ja . Jos laitamme , niin saadaan kätevä rekursio laskelmille , .

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

Se seuraa tästä: .

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

On myös yksinkertaisempi toistuvuussuhde: $C_{0}=1\quad$ ja . $\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}$

Katalonian lukujen generointifunktio on: $\sum _{n=0}^{\infty }C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.$

Katalonian luvut voidaan ilmaista binomiaalisilla kertoimilla : $C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {1}{2n+1}}{2n+1 \choose n}={\ binomi {2n}{n}}-{\binom {2n}{n-1}}.$

Toisin sanoen katalaaniluku on yhtä suuri kuin keskibinomikertoimen ja sen vieressä olevan Pascalin kolmion erotus samalla rivillä .

C_{n}

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

Katso myös

Muistiinpanot

↑ A. Spivak. Katalonian numerot. - MTsNMO.
↑ Nuoret kaaviot, polut hilassa ja heijastusmenetelmä M. A. Bershtein (ITF nimeltä Landau, IPPI nimetty Kharkevichin mukaan, NMU), G. A. Merzon (MTsNMO). 2014 (artikkeli bibliografialla)

Linkit

S. K. Lando. Luennot kombinatoriikasta . – MTsNMO , 1994.
A. Shen. Osat 2.6 ja 2.7 // Ohjelmointi: Lauseet ja tehtävät . — M.: MTsNMO , 2017.
Stanley, Richard P. (2013), katalaani lisäys Enumerative Combinatoricsin osaan 2 , < http://www-math.mit.edu/~rstan/ec/catadd.pdf >
Weisstein, Eric W. Catalan Number (englanniksi) Wolfram MathWorld -verkkosivustolla .