Triunghiul lui Catalan

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

1. ${\displaystyle C(n,0)=1{\text{ pentru }}n\geq 0}$.
2. ${\displaystyle C(n,1)=n{\text{ pentru }}n\geq 1}$.
3. ${\displaystyle C(n+1,k)=C(n+1,k-1)+C(n,k){\text{ pentru }}1<k<n+1}$
4. ${\displaystyle C(n+1,n+1)=C(n+1,n){\text{ pentru }}n\geq 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^[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ă pentru ${\displaystyle C(n,k)}$ este dată de:^[1][4]

${\displaystyle C(n,k)={\binom {n+k}{k}}-{\binom {n+k}{k-1}}}$

adică

${\displaystyle C(n,k)={\frac {n-k+1}{n+1}}{\binom {n+k}{k}}}$

Când ${\displaystyle k=n}$, 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 ${\displaystyle (n,k-1)}$ 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, ${\displaystyle (4,2)=9}$ enumeră:

${\displaystyle 1111,1112,1113,1122,1123,1133,1222,1223,1233}$

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 ${\displaystyle C_{m}(n,k)}$ 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ă ${\displaystyle C_{1}(n,k)=C(n,k)}$.

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 ${\displaystyle C_{m}(n,k)}$ este dată de:

${\displaystyle C_{m}(n,k)={\begin{cases}\left({\begin{array}{c}n+k\\k\end{array}}\right)&\,\,\,0\leq k<m\\\\\left({\begin{array}{c}n+k\\k\end{array}}\right)-\left({\begin{array}{c}n+k\\k-m\end{array}}\right)&\,\,\,m\leq k\leq n+m-1\\\\0&\,\,\,k>n+m-1\end{cases}}}$

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

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

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

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

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

(3) dacă ${\displaystyle m\leq k\leq n+m-1}$, atunci ${\displaystyle C_{m}(n,k)}$ este numărul de căi „roșii” ${\displaystyle \left({\begin{array}{c}n+k\\k\end{array}}\right)}$ minus numărul de căi „galbene” care traversează constrângerea, de exemplu ${\displaystyle \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 ${\displaystyle (0,0)}$ la ${\displaystyle (k,n)}$ care nu traversează constrângerea ${\displaystyle n-k+m-1=0}$ este așa cum este indicat în formula din secțiunea anterioară, Generalizare.

În primul rând, se confirmă validitatea relației de recurență ${\displaystyle C_{m}(n,k)=C_{m}(n-1,k)+C_{m}(n,k-1)}$ prin împărțirea ${\displaystyle 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 ${\displaystyle C_{m}(n-1,k)}$ combinații valide și a doua are ${\displaystyle 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 ${\displaystyle C_{m}(n,0)}$ și ${\displaystyle C_{m}(0,k)}$.

Portal Matematică