Katalana nombro

La katalanaj nombroj estas entjeroj ofte trovataj en kombinatoriko. Ili konsistigas vicon, kies n-a elemento $C_{n}$ estas difinita jene:

$C_{n}={\frac {1}{n+1}}{2n \choose n}$ ,

kie ${2n \choose n}$ estas la binoma koeficiento. La unuaj katalanaj nombroj por n = 0, 1, 2, 3, ... estas

1, 1, 2, 5, 14, 42, 132, 429, 1430, ... — estas la sinsekvo A000108 en OEIS.

Kvankam la difino enhavas dividon, ĉiuj katalanaj nombroj estas naturaj nombroj (pozitivaj enteroj), ĉar eblas prezenti ilin en jena formo:

por n ≥ 1: $C_{n}={2n \choose n}-{2n \choose {n-1}}$

Aplikoj en kombinatoriko

• $C_{n}$ estas egala al la nombro de la vortoj de Dyck de longo $2n$. "Vorto de Dyck" estas vorto formita el n literoj X kaj n literoj Y tia, ke ĉiu komenca parto de la vorto enhavas ne pli la Y-oj ol da X-oj. Alivorte, kiam oni trairas tian vorton de maldekstre, la nombro de jam legitaj X-oj neniam malsuperas tiun de la jam legitaj Y-oj. Aŭ se X estas malferma kaj Y estas ferma krampoj, tiam la vortoj de Dyck estas la ĝustaj parentezaj esprimoj. Ekzemple la vortoj de Dyck de longo 6 estas jenaj:

XXXYYY, XYXXYY, XYXYXY, XXYYXY, XXYXYY.

Efektive $C_{3}=5$.

• $C_{n}$ estas ankaŭ la nombro de malsamaj manieroj meti krampojn inter $n+1$ faktoroj. Ekzemple por $n=3$ ekzistas kvin parentezaj strukturoj por kvar faktoroj: a(b(cd)), a((bc)d), (ab)(cd), (a(bc))d, ((ab)c)d. Ĉar tiaj esprimoj estas reprezenteblaj per ordigitaj duumaj arboj, $C_{n}$ egalas ankaŭ al la nombro de de tiaj arboj kun $n+1$ folioj.

Trianguligoj de kvinangulo

• $C_{n}$ estas ankaŭ la nombro de malsamaj manieroj por dispartigi plurlateron de $n+2$ lateroj al trianguloj, ligante ĝiajn verticojn per strekoj.

• $C_{n}$ estas ankaŭ la nombro de

Rikura rilato

La katalanaj nombroj obeas jenan rikuran rilaton:

$C_{0}=1\qquad$ kaj por $\quad n\geq 1\qquad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$

Tion kaŭzas la fakto, ke ĉiu vorto v de Dyck de longo pli ol 2 estas skribebla unumaniere en jena formo:

v = Xv₁Yv₂

per du aliaj, eble malplenaj vortoj de Dyck $v_{1}$, $v_{2}$.

Historio

La katalana vico estis unuafoje priskribita en la 18-a jarcento de Leonhard Euler, kiu okupiĝis pri la malsamaj manieroj dispartigi plurlateron al trianguloj. La unuan publikaĵon pri la temo faris Johann Andreas Segner, kaj la vico de tiam portis la nomon "segneraj nombroj". Eugène Charles Catalan faris ligon al la nombro de parentezaj esprimoj, kaj lia nomo anstataŭis tiun de Segner.