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^[1] arată că $C(n,k)$ are următoarele proprietăți:

$C(n,0)=1{\text{ pentru }}n\geq 0$ .
$C(n,1)=n{\text{ pentru }}n\geq 1$ .
$C(n+1,k)=C(n+1,k-1)+C(n,k){\text{ pentru }}1<k<n+1$
$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ă

Formula generală pentru $C(n,k)$ este dată de:^[1]^[4]

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

adică

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

Când $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 $(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, $(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 $m = 1, 2, 3, ...$ este un trapez numeric ale cărui intrări $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ă $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 $C_{m}(n,k)$ este dată de:

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

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\leq k\leq 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)$ .

Note

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

Portal Matematică

[Bailey1996-1] Bailey, D. F. (1996). „Counting Arrangements of 1's and -1's”. Mathematics Magazine. 69 (2): 128–131. doi:10.1080/0025570X.1996.11996408.

[arbogast-2] r Arbogast, L. F. A. (1800). Du Calcul des Derivations. Levrault. p. 214.

[Shapiro1976-3] Shapiro, L. W. (1976). „A Catalan Triangle”. Discrete Mathematics. 14 (1): 83–90. doi:10.1016/0012-365x(76)90009-1 .

[4] Eric W. Weisstein. „Catalan's Triangle”. MathWorld − A Wolfram Web Resource. Accesat în 28 martie 2012.

[5] Șirul A009766 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

[6] Reuveni, Shlomi (2014). „Catalan's trapezoids”. Probability in the Engineering and Informational Sciences. 28 (3): 4391–4396. doi:10.1017/S0269964814000047.

[1]

[2]

[3]

[4]

[5]

[6]