Katalāna skaitļi

Kombinatorikā Katalāna skaitļi veido naturālu skaitļu virkni, kas sastopama dažādās skaitīšanas problēmās, bieži ietverot rekursīvi definētus objektus. Tie nosaukti par godu beļģu matemātiķim Eiženam Šarlam Katalānam (Eugène Charles Catalan, 1814–1894).

n-to Katalāna skaitli var izteikt tieši, izmantojot binomiālos koeficientus:

C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}\qquad {\mbox{pie }}n\geq 0.

Pirmie Katalāna skaitļi pie n = 0, 1, 2, 3, ... ir

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...

Īpašības

Katalāna skaitļus C_n var aprēķināt arī pēc citas formulas:

C_{n}={2n \choose n}-{2n \choose n+1}\quad {\text{ ja }}n\geq 0,

kas ir ekvivalenti augstākminētai formulai, jo ${\tbinom {2n}{n+1}}={\tfrac {n}{n+1}}{\tbinom {2n}{n}}$ . Tas parāda, ka C_n ir vesels skaitlis, kas nav acīmredzams no pirmās dotās formulas.

Katalāna skaitļiem izpildās rekurenta sakarība

C_{0}=1\quad {\mbox{un}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{pie }}n\geq 0;

vēl vairāk,

C_{n}={\frac {1}{n+1}}\sum _{i=0}^{n}{n \choose i}^{2}.

Tas ir tāpēc, ka ${\tbinom {2n}{n}}=\sum _{i=0}^{n}{\tbinom {n}{i}}^{2},$ jo izvēloties n skaitļus no kopas ar 2n skaitļiem var vienā vienīgā veidā sadalīt 2 daļās: izvēloties i skaitļus no pirmiem n skaitļiem un tad izvēloties n-i skaitļus no atlikušajiem n skaitļiem.