Katalana nombro

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

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

kie ${\displaystyle {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 entjeroj), ĉar eblas prezenti ilin en jena formo:

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

Aplikoj en kombinatoriko

• ${\displaystyle C_{n}}$ estas egala al la nombro de la vortoj de Dyck de longo ${\displaystyle 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 ${\displaystyle C_{3}=5}$.

• ${\displaystyle C_{n}}$ estas ankaŭ la nombro de malsamaj manieroj meti krampojn inter ${\displaystyle n+1}$ faktoroj. Ekzemple por ${\displaystyle 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, ${\displaystyle C_{n}}$ egalas ankaŭ al la nombro de de tiaj arboj kun ${\displaystyle n+1}$ folioj.

Trianguligoj de kvinangulo

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

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

Rikura rilato

La katalanaj nombroj obeas jenan rikuran rilaton:

${\displaystyle C_{0}=1\qquad }$ kaj por ${\displaystyle \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 ${\displaystyle v_{1}}$, ${\displaystyle 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.

• Kategorio Katalana nombro en la Vikimedia Komunejo (Multrimedaj datumoj)