Î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 arată că are următoarele proprietăți: . .

.

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 de Louis François Antoine Arbogast.

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

Formula generală Formula generală pentru este dată de:

adică

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

Suma pe al -lea rând este al -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. {| class="wikitable" style="text-align:right;" |- ! ! width="50" | 0 ! width="50" | 1 ! width="50" | 2 ! width="50" | 3 ! width="50" | 4 ! width="50" | 5 ! width="50" | 6 ! width="50" | 7 ! width="50" | 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 părți cu partea maximă astfel încât fiecare parte să fie mai mică sau egală cu indicele său. Deci, de exemplu, enumeră:

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

Tabelul următor prezintă câteva valori din trapezul lui Catalan de ordinul . {| class="wikitable" style="text-align:right;" |- ! ! width="50" | 0 ! width="50" | 1 ! width="50" | 2 ! width="50" | 3 ! width="50" | 4 ! width="50" | 5 ! width="50" | 6 ! width="50" | 7 ! width="50" | 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 . {| class="wikitable" style="text-align:right;" |- ! ! width="50" | 0 ! width="50" | 1 ! width="50" | 2 ! width="50" | 3 ! width="50" | 4 ! width="50" | 5 ! width="50" | 6 ! width="50" | 7 ! width="50" | 8 ! width="50" | 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:

( , , ).

Demonstrații ale formulei generale pentru Prima demonstrație 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 . center|600px

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

Note

Catalan Categorie:Subiecte factoriale și binomiale