În combinatorică triunghiul lui Catalan este un tablou triunghiular ale cărui intrări dau numărul de șiruri format din n de X și k de Y astfel încât niciun segment inițial al șirului să aibă mai mulți Y decât X. Este o generalizare a numerelor Catalan și poartă numele lui Eugène Charles Catalan. Bailey[1] arată că are următoarele proprietăți:

  1. .
  2. .
  3. .

Formula 3 arată că intrarea în triunghi se obține recursiv prin adunarea numerelor de la stânga și de mai sus din triunghi. Cea mai veche apariție a triunghiului Catalan împreună cu formula recursivă este în pagina 214 a tratatului de calcul publicat în 1800[2] de Louis François Antoine Arbogast.

Shapiro[3] a introdus un alt triunghi pe care l-a numit „triunghi Catalan”, care este diferit de triunghiul discutat aici.

Formula generală

modificare

Formula generală pentru   este dată de:[1][4]

 

adică

 

Când  , diagonala C(n, n) este al n-lea număr Catalan.

Suma pe al n-lea rând este al (n + 1)-lea număr Catalan, folosind identitatea crosei de hochei și o expresie alternativă pentru numerele Catalan.

Tabelul următor prezintă câteva valori din triunghiul Catalan.[5]

 k
n 
0 1 2 3 4 5 6 7 8
0 1
1 1 1
2 1 2 2
3 1 3 5 5
4 1 4 9 14 14
5 1 5 14 28 42 42
6 1 6 20 48 90 132 132
7 1 7 27 75 165 297 429 429
8 1 8 35 110 275 572 1001 1430 1430

O interpretare combinatorică a celei de a   valori este numărul de partiții nedescrescătoare cu exact n părți cu partea maximă k astfel încât fiecare parte să fie mai mică sau egală cu indicele său. Deci, de exemplu,   enumeră:

 

Generalizare

modificare

Trapezele lui Catalan sunt o mulțime numărabilă de trapeze numerice care generalizează triunghiul lui Catalan. Trapezul lui Catalan de ordinul m = 1, 2, 3, ... este un trapez numeric ale cărui intrări   dau numărul de șiruri constând din n X și k Y astfel încât în fiecare segment inițial al șirului numărul de Y să nu depășească numărul de X cu m sau cu mai mult.[6] Prin definiție, trapezul lui Catalan de ordinul m = 1 este triunghiul lui Catalan, adică  .

Tabelul următor prezintă câteva valori din trapezul lui Catalan de ordinul m = 2.

 k
n 
0 1 2 3 4 5 6 7 8
0 1 1
1 1 2 2
2 1 3 5 5
3 1 4 9 14 14
4 1 5 14 28 42 42
5 1 6 20 48 90 132 132
6 1 7 27 75 165 297 429 429
7 1 8 35 110 275 572 1001 1430 1430

Tabelul următor prezintă câteva valori din trapezul lui Catalan de ordinul m = 3.

 k
n 
0 1 2 3 4 5 6 7 8 9
0 1 1 1
1 1 2 3 3
2 1 3 6 9 9
3 1 4 10 19 28 28
4 1 5 15 34 62 90 90
5 1 6 21 55 117 207 297 297
6 1 7 28 83 200 407 704 1001 1001
7 1 8 36 119 319 726 1430 2431 3432 3432

Din nou, fiecare element este suma celui de deasupra și a celui din stânga.

O formulă generală pentru   este dată de:

 

( n = 0, 1, 2, ..., k = 0, 1, 2, ..., m = 1, 2, 3, ...).

Demonstrații ale formulei generale pentru

modificare

Prima demonstrație

modificare

Această demonstrație implică o extensie a metodei reflexiei Andres așa cum este utilizată în a doua demonstrație pentru numărul Catalan la diferite diagonale. Următoarele arată cum fiecare cale de la   din stânga jos până la   din dreapta sus a diagramei care prezintă constrângerea   poate fi reflectată și în punctul final  .

 

Se consideră trei cazuri în care se determină numărul de căi de la   la   care nu traversează constrângerea:

(1) dacă   constrângerea nu poate fi traversată, deci toate căile de la   la   sunt valide, de exemplu  .

(2) dacă   este imposibil de a forma o cale care să nu traverseze constrângerea, de exemplu  .

(3) dacă  , atunci   este numărul de căi „roșii”   minus numărul de căi „galbene” care traversează constrângerea, de exemplu  .

Prin urmare, numărul de căi de la   la   care nu traversează constrângerea   este așa cum este indicat în formula din secțiunea anterioară, Generalizare.

A doua demonstrație

modificare

În primul rând, se confirmă validitatea relației de recurență   prin împărțirea   în două părți, prima pentru combinațiile XY care se termină în X și a doua pentru cele care se termină în Y. Prin urmare, primul grup are   combinații valide și a doua are  . Demonstrația este completată prin verificarea că soluția satisface relația de recurență și respectă condițiile inițiale pentru   și  .

  1. ^ a b en Bailey, D. F. (). „Counting Arrangements of 1's and -1's”. Mathematics Magazine. 69 (2): 128–131. doi:10.1080/0025570X.1996.11996408. 
  2. ^ fr Arbogast, L. F. A. (). Du Calcul des Derivations. Levrault. p. 214. 
  3. ^ en Shapiro, L. W. (). „A Catalan Triangle”. Discrete Mathematics. 14 (1): 83–90. doi:10.1016/0012-365x(76)90009-1 . 
  4. ^ en Eric W. Weisstein. „Catalan's Triangle”. MathWorld − A Wolfram Web Resource. Accesat în . 
  5. ^ Șirul A009766 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  6. ^ en Reuveni, Shlomi (). „Catalan's trapezoids”. Probability in the Engineering and Informational Sciences. 28 (3): 4391–4396. doi:10.1017/S0269964814000047.