Katalana nombro

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

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, ...

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[redakti | redakti fonton]

  • 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

Rikura rilato[redakti | redakti fonton]

La katalanaj nombroj obeas jenan rikuran rilaton:

C_0 = 1 \qquad kaj por \quad n\ge 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 = Xv1Yv2

per du aliaj, eble malplenaj vortoj de Dyck v_1, v_2.

Historio[redakti | redakti fonton]

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.