Triunghiul lui Catalan
Î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:
- .
- .
- .
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ă
modificareFormula 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]
- kn
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
modificareTrapezele 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.
- kn
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.
- kn
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
modificarePrima demonstrație
modificareAceastă 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 .
Note
modificare- ^ 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.
- ^ fr Arbogast, L. F. A. (). Du Calcul des Derivations. Levrault. p. 214.
- ^ en Shapiro, L. W. (). „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 .
- ^ Șirul A009766 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
- ^ en Reuveni, Shlomi (). „Catalan's trapezoids”. Probability in the Engineering and Informational Sciences. 28 (3): 4391–4396. doi:10.1017/S0269964814000047.