Katalāna skaitļi

Vikipēdijas lapa
Pārlēkt uz: navigācija, meklēt

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:

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[labot šo sadaļu | labot pirmkodu]

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

kas ir ekvivalenti augstākminētai formulai, jo . Tas parāda, ka Cn ir vesels skaitlis, kas nav acīmredzams no pirmās dotās formulas.

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

vēl vairāk,

Tas ir tāpēc, ka 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.

Tie arī apmierina sakarības:

kas var būt efektīvāks veids, kā tos izrēķināt.

Asimptotiski Katalāna skaitļi aug kā

.

Skatīt arī[labot šo sadaļu | labot pirmkodu]