Catalanske tal

Catalanske tal er en talrække , der forekommer i mange kombinatoriske problemer .

Sekvensen er opkaldt efter den belgiske matematiker Eugene Charles Catalan , selvom den også var kendt af Leonhard Euler .

De catalanske tal for danner sekvensen: $C_{n}$ $n=0,1,2,\prikker$

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 catalanske tal kan defineres på flere ækvivalente måder, såsom [1] : $C_{n}$

Antallet af fliser af en konveks ( n +2)-gon i trekanter ved ikke-skærende diagonaler .
Antallet af måder at forbinde 2 n punkter på en cirkel med n ikke-skærende akkorder .
Antallet af korrekte parentessekvenser af længden 2 n , dvs. sådanne sekvenser af n venstre og n højre parenteser, hvor antallet af åbne parenteser er lig med antallet af afsluttende parenteser, og i et hvilket som helst af dets præfikser er der ikke mindre åbningsparenteser end lukkebeslag.
- For eksempel, for n = 3 er der 5 sådanne sekvenser: ((())), ()(()), ()()(), (())(), (()()) altså . $C_{3}=5$

Antallet af tupler af n naturlige tal såsom for . $(x_{1},x_{2},\ldots ,x_{n})$ $x_1=1$ $x_{i}\leqslant x_{i-1}+1$ $2 \leqslant i \leqslant n$
Antallet af ikke -isomorfe ordnede binære træer med en rod og n + 1 blade.
Antallet af mulige måder at linearisere det kartesiske produkt af 2 lineære ordnede sæt: fra 2 og fra n elementer.
Antal pikstier fra punkt(0,0) til punkt (n, n). [2]

Egenskaber

De catalanske tal opfylder den rekursive relation : $C_{0}=1\quad$ og for . ${\displaystyle \quad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i))$ $n\geqslant 1$

Denne relation opnås let ud fra det faktum, at enhver ikke-tom regulær parentessekvens entydigt kan repræsenteres som w = ( w 1 ) w 2 , hvor w 1 , w 2 er regulære parentessekvenser.

Der er en anden gentagelsesrelation:

C_{0}=1\quad

og .

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

En anden rekursiv formel :

C_{0}=1\quad

og . Hvis vi sætter , så får vi en bekvem rekursion til beregninger , .

\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ølger herfra :.

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

Der er også en enklere gentagelsesrelation: $C_{0}=1\quad$ og . $\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}$

Den genererende funktion af de catalanske tal er: $\sum _{n=0}^{\infty}C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.$

Catalanske tal kan udtrykkes i form af binomiale koefficienter : $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 andre ord er det catalanske tal lig med forskellen mellem den centrale binomiale koefficient og Pascals trekant ved siden af den på samme linje .

C_{n}

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

Se også

Noter

↑ A. Spivak. catalanske tal. — MTsNMO.
↑ Unge diagrammer, stier på et gitter og metoden til refleksioner M. A. Bershtein (ITF opkaldt efter Landau, IPPI opkaldt efter Kharkevich, NMU), G. A. Merzon (MTsNMO). 2014 (artikel med bibliografi)

Catalanske tal

Definitioner

Egenskaber

Se også

Noter

Links