Latice Tamari
În matematică o latice Tamari, introdusă de Dov Tamari,[1] este o mulțime parțial ordonată(d) în care elementele constau în diferitele moduri de grupare ale elementelor unui șir de obiecte în perechi folosind paranteze; de exemplu, pentru o secvență de patru obiecte abcd, cele cinci grupări posibile sunt ((ab)c)d, (ab)(cd), (a(bc))d, a((bc)d) și a(b(cd)). Fiecare grupare descrie o ordine diferită în care obiectele pot fi combinate printr-o operație binară. În laticea Tamari, o grupare este ordonată înaintea alteia dacă a doua grupare poate fi obținută din prima numai prin aplicații spre dreapta ale asociativității (xy)z = x(yz). De exemplu, aplicarea acestei legi cu x = a, y = bc și z = d dă extinderea (a(bc))d = a((bc)d), deci în ordinea laticei Tamari (a(bc))d ≤ a((bc)d).
În această ordonare parțială, oricare două grupări g1 și g2 au cel mai mare predecesor comun (minorant) expresia g1 ∧ g2 și cel mai mic succesor comun (majorant) expresia g1 ∨ g2. Astfel, laticea Tamari are structura unei latice(d). Diagrama Hasse(d) a acestei latice este izomorfă față de graful vârfurilor și laturilor(d) unui asociaedru. Numărul de elemente dintr-o latice Tamari pentru o secvență de n + 1 obiecte este al n-lea număr Catalan Cn.
Laticea Tamari poate fi descrisă și în alte moduri, echivalente:
- Este mulțimea parțial ordonată de secvențe de n întregi a1, ..., an, ordonate în funcție de coordonate, astfel încât i ≤ ai ≤ n, iar dacă i ≤ j ≤ ai atunci aj ≤ ai.[2]
- Este mulțimea parțial ordonată a arborilor binari cu n noduri terminale, ordonată prin operații de rotație a unui arbore.
- Este mulțimea parțial ordonată a pădurilor ordonate, în care o pădure este anterioară alteia în ordinea parțială dacă, pentru fiecare j, al j-lea nod din ordinea traversării primei păduri are cel puțin la fel de mulți descendenți ca și nodul j dintr-o traversare în ordinea celei de-a doua păduri.[3]
- Este mulțimea parțial ordonată a tringulărilor unui n-gon convex, ordonat prin operații de inversare care înlocuiesc o diagonală a poligonului cu alta.
Notații
modificareLaticea Tamari a grupărilor Cn de n+1 obiecte este notată Tn, dar asociaedrul corespunzător este notat Kn+1.
În Arta programării calculatoarelor T4 este numită laticea Tamari de ordinul 4, iar diagrama sa Hasse, K5, asociaedrul de ordinul 4.[3]
Note
modificare- ^ en Tamari, Dov (), „The algebra of bracketings and their enumeration”, Nieuw Archief voor Wiskunde, Series 3, 10: 131–146, MR 0146227
- ^ en Huang, Samuel; Tamari, Dov (), „Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law”, Journal of Combinatorial Theory, Series A, 13: 7–13, doi:10.1016/0097-3165(72)90003-9
, MR 0306064
- ^ a b en Knuth, Donald E. (), „Draft of Section 7.2.1.6: Generating All Trees”, The Art of Computer Programming (în română Arta programării calculatoarelor), IV, p. 34, arhivat din original la , accesat în (Knuth 2005)
Bibliografie
modificare- fr Chapoton, F. (), „Sur le nombre d'intervalles dans les treillis de Tamari”, Séminaire Lotharingien de Combinatoire, 55 (55): 2368, arXiv:math/0602368 , Bibcode:2006math......2368C, MR 2264942
- en Csar, Sebastian A.; Sengupta, Rik; Suksompong, Warut (), „On a Subposet of the Tamari Lattice”, Order, 31 (3): 337–363, arXiv:1108.5690 , doi:10.1007/s11083-013-9305-5, MR 3265974
- en Early, Edward (), „Chain lengths in the Tamari lattice”, Annals of Combinatorics, 8 (1): 37–43, doi:10.1007/s00026-004-0203-9, MR 2061375
- en Friedman, Haya; Tamari, Dov (), „Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative”, Journal of Combinatorial Theory (în French), 2 (3): 215–242, doi:10.1016/S0021-9800(67)80024-3 , MR 0238984
- en Geyer, Winfried (), „On Tamari lattices”, Discrete Mathematics, 133 (1–3): 99–122, doi:10.1016/0012-365X(94)90019-1 , MR 1298967
