Krata Tamari
W matematyce krata Tamari , wprowadzona przez Dova Tamari ( 1962 ), jest częściowo uporządkowanym zbiorem , w którym elementy składają się z różnych sposobów grupowania sekwencji obiektów w pary za pomocą nawiasów; na przykład dla sekwencji czterech obiektów abcd pięć możliwych grup to (( ab ) c ) d , ( ab ) ( cd ), ( a ( bc )) d , a ( ( bc ) d ) i a ( b ( cd )). Każde grupowanie opisuje inną kolejność, w jakiej obiekty mogą być łączone za pomocą operacji binarnej ; w siatce Tamari jedno ugrupowanie jest uporządkowane przed drugim, jeśli drugie ugrupowanie można otrzymać z pierwszego tylko przez prawe zastosowanie prawa asocjacji ( xy ) z = x ( yz ) . Na przykład, stosując to prawo z x = a , y = bc i z = d daje rozwinięcie ( a ( bc )) d = a (( bc ) d ), więc w kolejności kraty Tamariego ( a ( bc )) d ≤ a (( bc ) d ).
W tym rzędzie częściowym dowolne dwa ugrupowania g 1 i g 2 mają największego wspólnego poprzednika, spotkanie g 1 ∧ g 2 , i najmniej wspólnego następcę, łączenie g 1 ∨ g 2 . Zatem krata Tamari ma strukturę kraty . Diagram Hassego tej sieci jest izomorficzny z wykresem wierzchołków i krawędzi asocjaścianu . Liczba elementów w siatce Tamariego dla ciągu n + 1 obiektów to n- ta liczba katalońska Cn .
Sieć Tamari można również opisać na kilka innych równoważnych sposobów:
- Jest to zbiór ciągów n liczb całkowitych a 1 , ..., a n , uporządkowanych współrzędnie tak, że i ≤ a i ≤ n oraz jeśli i ≤ j ≤ a i to a j ≤ a i ( Huang & Tamari 1972 ) .
- Jest to zestaw drzew binarnych z n liśćmi, uporządkowanych według operacji rotacji drzew .
- Jest to zbiór lasów uporządkowanych , w którym jeden las jest wcześniejszy niż inny w częściowym porządku, jeśli dla każdego j j - ty węzeł w przechodzeniu pierwszego lasu w kolejności wstępnej ma co najmniej tyle samo potomków, co j- ty węzeł w wstępna przeprawa przez drugi las ( Knuth 2005 ).
- Jest to zbiór triangulacji wypukłego n -gonu, uporządkowanych przez operacje odwracania, które zamieniają jedną przekątną wielokąta na inną.
Notacja
Sieć Tamariego zgrupowań Cn n + 1 obiektów nosi nazwę Tn , ale odpowiadający jej asocjaścian nazywa się Kn + 1 .
W The Art of Computer Programming T 4 nazywana jest siatką Tamariego rzędu 4 , a jej diagram Hassego K 5 – asociaedrem rzędu 4 .
- Chapoton, F. (2005), "Sur le nombre d'intervalles dans les treillis de Tamari", Séminaire Lotharingien de Combinatoire (po francusku), 55 (55): 2368, arXiv : math/0602368 , Bibcode : 2006math... ...2368C , MR 2264942 .
- Cesar, Sebastian A.; Sengupta, Rik; Suksompong, Warut (2014), „On a Subposet of the Tamari Lattice”, Order , 31 (3): 337–363, arXiv : 1108,5690 , doi : 10,1007/s11083-013-9305-5 , MR 3265974 .
- Wcześnie, Edward (2004), „Długości łańcuchów w sieci Tamari”, Annals of Combinatorics , 8 (1): 37–43, doi : 10.1007 / s00026-004-0203-9 , MR 2061375 .
- Friedman, Haya ; Tamari, Dov (1967), „Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative”, Journal of Combinatorial Theory (w języku francuskim), 2 (3): 215–242, doi : 10.1016 / S0021 -9800(67)80024-3 , MR 0238984 .
- Geyer, Winfried (1994), „O kratach Tamari”, Matematyka dyskretna , 133 (1–3): 99–122, doi : 10.1016/0012-365X (94) 90019-1 , MR 1298967 .
- Huang, Samuel; Tamari, Dov (1972), „Problemy asocjatywności: prosty dowód na właściwość sieci systemów uporządkowanych przez prawo półasocjacyjne”, Journal of Combinatorial Theory , Series A , 13 : 7–13, doi : 10.1016/0097- 3165(72)90003-9 , MR 0306064 .
- Knuth, Donald E. (2005), „Szkic sekcji 7.2.1.6: Generowanie wszystkich drzew” , The Art of Computer Programming , tom. IV, str. 34 .
- Tamari, Dov (1962), „Algebra nawiasów i ich wyliczanie”, Nieuw Archief voor Wiskunde , Series 3, 10 : 131–146, MR 0146227 .