Triunghiul lui Catalan

În combinatorică triunghiul lui Catalan este un tablou triunghiular ale cărui intrări $C(n,k)$ 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ă $C(n,k)$ are următoarele proprietăți:

1. $C(n,0)=1\text{ pentru }n\ge 0$.
2. $C(n,1)=n\text{ pentru }n\ge 1$.
3. $C(n+1,k)=C(n+1,k-1)+C(n,k)\text{ pentru }1<k<n+1$
4. $C(n+1,n+1)=C(n+1,n)\text{ pentru }n\ge 1$.

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 $C(n,k)$ este dată de:

$C(n,k)=(\genfrac{}{}{0ex}{}{n+k}{k})-(\genfrac{}{}{0ex}{}{n+k}{k-1})$

adică

$C(n,k)=\frac{n-k+1}{n+1}(\genfrac{}{}{0ex}{}{n+k}{k})$

Când $k=n$, diagonala Format:Math este al Format:Mvar-lea număr Catalan.

Suma pe al Format:Mvar-lea rând este al Format:Math-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.

Format:Separator diagonal	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 $(n,k-1)$ valori este numărul de partiții nedescrescătoare cu exact Format:Mvar părți cu partea maximă Format:Mvar astfel încât fiecare parte să fie mai mică sau egală cu indicele său. Deci, de exemplu, $(4,2)=9$ enumeră:

$1111,1112,1113,1122,1123,1133,1222,1223,1233$

Generalizare

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

Tabelul următor prezintă câteva valori din trapezul lui Catalan de ordinul Format:Math.

Format:Separator diagonal	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 Format:Math.

Format:Separator diagonal	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 $C_m(n,k)$ este dată de:

$C_m(n,k)=\{\begin{array}{cc}\left(\begin{array}{c}n+k\\ k\end{array}\right)& 0\le k<m\\ \\ \left(\begin{array}{c}n+k\\ k\end{array}\right)-\left(\begin{array}{c}n+k\\ k-m\end{array}\right)& m\le k\le n+m-1\\ \\ 0& k>n+m-1\end{array}$

( Format:Math, Format:Math, Format:Math).

Demonstrații ale formulei generale pentru $C_m(n,k)$

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 $(0,0)$ din stânga jos până la $(k,n)$ din dreapta sus a diagramei care prezintă constrângerea $n-k+m-1=0$ poate fi reflectată și în punctul final $(n+m,k-m)$.

Se consideră trei cazuri în care se determină numărul de căi de la $(0,0)$ la $(k,n)$ care nu traversează constrângerea:

(1) dacă $m>k$ constrângerea nu poate fi traversată, deci toate căile de la $(0,0)$ la $(k,n)$ sunt valide, de exemplu $C_m(n,k)=\left(\begin{array}{c}n+k\\ k\end{array}\right)$.

(2) dacă $k-m+1>n$ este imposibil de a forma o cale care să nu traverseze constrângerea, de exemplu $C_m(n,k)=0$.

(3) dacă $m\le k\le n+m-1$, atunci $C_m(n,k)$ este numărul de căi „roșii” $\left(\begin{array}{c}n+k\\ k\end{array}\right)$ minus numărul de căi „galbene” care traversează constrângerea, de exemplu $\left(\begin{array}{c}(n+m)+(k-m)\\ k-m\end{array}\right)=\left(\begin{array}{c}n+k\\ k-m\end{array}\right)$.

Prin urmare, numărul de căi de la $(0,0)$ la $(k,n)$ care nu traversează constrângerea $n-k+m-1=0$ 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ță $C_m(n,k)=C_m(n-1,k)+C_m(n,k-1)$ prin împărțirea $C_m(n,k)$ î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 $C_m(n-1,k)$ combinații valide și a doua are $C_m(n,k-1)$. Demonstrația este completată prin verificarea că soluția satisface relația de recurență și respectă condițiile inițiale pentru $C_m(n,0)$ și $C_m(0,k)$.