Katalanska siffror

Katalanska tal är en nummersekvens som förekommer i många kombinatoriska problem .

Sekvensen är uppkallad efter den belgiske matematikern Eugene Charles Catalan , även om den också var känd för Leonhard Euler .

De katalanska talen för bildar sekvensen: $C_{n}$ $n=0,1,2,\prickar$

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, … (sekvens A000108 i OEIS )

Definitioner

Det n:te katalanska numret kan definieras på flera likvärdiga sätt, såsom [1] : $C_{n}$

Antalet plattsättningar av en konvex ( n +2)-gon till trianglar genom icke-korsande diagonaler .
Antalet sätt att koppla samman 2 n punkter på en cirkel med n icke-skärande ackord .
Antalet korrekta parentessekvenser av längden 2 n , dvs sådana sekvenser av n vänstra och n högra parenteser, där antalet öppningsparenteser är lika med antalet avslutande parenteser, och i något av dess prefix finns det inte mindre öppningsparenteser än slutande parentes.
- Till exempel, för n = 3 finns det 5 sådana sekvenser: ((())), ()(()), ()()(), (())(), (()()) det vill säga . $C_{3}=5$

Antalet tuplar av n naturliga tal som för . $(x_{1},x_{2},\ldots ,x_{n})$ $x_1=1$ $x_{i}\leqslant x_{i-1}+1$ $2 \leqslant i \leqslant n$
Antalet icke- isomorfa ordnade binära träd med en rot och n + 1 blad.
Antalet möjliga sätt att linjärisera den kartesiska produkten av 2 linjärt ordnade mängder: från 2 och från n element.
Antal Dick-banor från punkt(0,0) till punkt (n, n). [2]

Egenskaper

De katalanska talen uppfyller det rekursiva förhållandet : $C_{0}=1\quad$ och för . ${\displaystyle \quad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i))$ $n\geqslant 1$

Denna relation erhålls lätt från det faktum att vilken som helst icke-tom regelbunden parentessekvens kan representeras unikt som w = ( w 1 ) w 2 , där w 1 , w 2 är reguljära parentessekvenser.

Det finns en annan återkommande relation:

C_{0}=1\quad

och .

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

En annan rekursiv formel :

C_{0}=1\quad

och . Om vi sätter , då får vi en bekväm rekursion för beräkningar , .

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

Det följer härifrån: .

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

Det finns också en enklare återfallsrelation: $C_{0}=1\quad$ och . $\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}$

Den genererande funktionen för de katalanska talen är: $\sum _{n=0}^{\infty }C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.$

Katalanska tal kan uttryckas i termer av binomialkoefficienter : $C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {1}{2n+1}}{2n+1 \choose n}={\ binom {2n}{n}}-{\binom {2n}{n-1}}.$

Med andra ord är det katalanska talet lika med skillnaden mellan den centrala binomialkoefficienten och Pascals triangel intill den på samma linje .

C_{n}

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

Se även

Anteckningar

↑ A. Spivak. Katalanska siffror. — MTsNMO.
↑ Unga diagram, banor på ett gitter och metoden för reflektioner M. A. Bershtein (ITF uppkallad efter Landau, IPPI uppkallad efter Kharkevich, NMU), G. A. Merzon (MTsNMO). 2014 (artikel med bibliografi)

Länkar

S. K. Lando. Föreläsningar om kombinatorik . — MTsNMO , 1994.
A. Shen. Avsnitt 2.6 och 2.7 // Programmering: Satser och problem . — M.: MTsNMO , 2017.
Stanley, Richard P. (2013), katalanskt tillägg till Enumerative Combinatorics, volym 2 , < http://www-math.mit.edu/~rstan/ec/catadd.pdf >
Weisstein, Eric W. Catalan Number (engelska) på Wolfram MathWorlds webbplats .