Решетка Тамари

В математике решетка Тамари, введенная Дов Тамари (1962), представляет собой частично упорядоченное множество, в котором элементы состоят из различных способов группировки последовательности объектов в пары с помощью круглых скобок; например, для последовательности из четырех объектов abcd пять возможных группировок: ((ab) c) d, (ab) (cd), (a (bc)) d, a ((bc) d) и a ( б (кд)). Каждая группировка описывает различный порядок, в котором объекты могут быть объединены с помощью бинарной операции ; в решетке Тамари одна группировка упорядочена перед другой, если вторая группировка может быть получена из первой только правыми применениями закона ассоциации (xy) z = x (yz). Например, применение этого закона с x = a, y = bc и z = d дает разложение (a (bc)) d = a ((bc) d), поэтому в упорядочении решетки Тамари (a (bc))) d ≤ a ((bc) d).

В этом частичном порядке любые две группы g 1 и g 2 имеют наибольшего общего предшественника, встречаются g 1 ∧ g 2, и наименьший общий преемник, объединение g 1 ∨ g 2. Таким образом, решетка Тамари имеет структуру решетки. диаграмма Хассе этой решетки изоморфна графу вершин и ребер ассоциаэдра. Число элементов в решетке Тамари для последовательности из n + 1 объектов равно n-му каталонскому числу Cn.

Решетка Тамари также может быть описана несколькими другими эквивалентными способами:

• Это последовательность последовательностей n целых чисел a 1,..., a n, упорядоченных по координатам, так что i ≤ a i ≤ n и если i ≤ j ≤ a i, затем a j ≤ a i(Хуанг и Тамари 1972).
• Это последовательность двоичных деревьев с n листьями, упорядоченных по повороту дерева operations.
• Это набор упорядоченных лесов, в которых один лес находится раньше другого в частичном порядке, если для каждого j j-й узел в предварительный обход первого леса имеет по крайней мере столько же потомков, сколько j-й узел в предварительном обходе второго леса (Knuth 2005).
• Это позиция триангуляции выпуклый n-угольник, упорядоченный операциями переворота, которые заменяют одну диагональ многоугольника на другую.

Решетка Тамари групп Cn n + 1 объектов называется T n, но соответствующий ассоциаэдр называется K n + 1.

В The Art of Computer Programming T4назвал решетку Тамари порядка 4 и ее диаграмму Хассе K 5 ассоциэдром порядка 4.

• Chapoton, F. (2005), "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.
• Csar, Sebastian A.; Сенгупта, Рик; Суксомпонг, Варут (2014), «На подмножестве решетки Тамари», Order, 31(3): 337–363, arXiv : 1108.5690, doi : 10.1007 / s11083-013-9305-5, MR 3265974.
• Ранний, Эдвард (2004), «Длины цепей в решетке Тамари», Annals of Combinatorics, 8 (1): 37–43, doi : 10.1007 / s00026-004-0203-9, MR 2061375.
• Фридман, Хайя ; Тамари, Дов (1967), "Problèmes d'associativité: Une structure de treillis finis Induite par une loi demi-associative", Journal of Combinatorial Theory (на французском языке), 2 ( 3): 215–242, doi : 10.1016 / S0021-9800 (67) 80024-3, MR 0238984.
• Гейер, Винфрид (1994), «О решетках Тамари», Дискретная математика, 133 (1–3): 99–122, doi : 10.1016 / 0012-365X (94) 90019-1, MR 1298967.
• Хуанг, Самуил; Тамари, Дов (1972), «Проблемы ассоциативности: простое доказательство решетчатых свойств систем, упорядоченных полуассоциативным законом», Журнал комбинаторной теории, серия A, 13 : 7–13, doi : 10.1016 / 0097-3165 (72) 90003-9, MR 0306064.
• Кнут, Дональд Э. (2005), «Проект раздела 7.2.1.6: Создание всех деревьев», Искусство программирования, IV, стр. 34.
• Тамари, Дов (1962), "Алгебра скобок и их перечисление", Nieuw Archief voor Wiskunde, Ser. 3, 10 : 131–146, MR 0146227.