Решетка Тамари - Tamari lattice

Решетка Тамари порядка 4

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

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

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

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

Обозначение

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

В Искусство программирования Т4 называется Решетка Тамари порядка 4 и его диаграмма Хассе K5 то ассоциаэдр порядка 4.

Рекомендации

  • Чапотон, Ф. (2005), "Sur le nombre d'intervalles dans les treillis de Tamari", Séminaire Lotharingien de Combinatoire (На французском), 55 (55): 2368, arXiv:математика / 0602368, Bibcode:2006математика ...... 2368C, МИСТЕР  2264942.
  • Царь, Себастьян А .; Сенгупта, Рик; Суксомпонг, Варут (2014), «О подмножестве решетки Тамари», Заказ, 31 (3): 337–363, arXiv:1108.5690, Дои:10.1007 / s11083-013-9305-5, МИСТЕР  3265974.
  • Ранний, Эдвард (2004), «Длины цепей в решетке Тамари», Анналы комбинаторики, 8 (1): 37–43, Дои:10.1007 / s00026-004-0203-9, МИСТЕР  2061375.
  • Фридман, Хайя; Тамари, Дов (1967), "Problèmes d'associativité: Une structure de treillis finis Induite par une loi demi-associative", Журнал комбинаторной теории (На французском), 2 (3): 215–242, Дои:10.1016 / S0021-9800 (67) 80024-3, МИСТЕР  0238984.
  • Гейер, Винфрид (1994), "На решетках Тамари", Дискретная математика, 133 (1–3): 99–122, Дои:10.1016 / 0012-365X (94) 90019-1, МИСТЕР  1298967.
  • Хуанг, Самуэль; Тамари, Дов (1972), "Проблемы ассоциативности: простое доказательство решетчатого свойства систем, упорядоченных полуассоциативным законом", Журнал комбинаторной теории, серия А, 13: 7–13, Дои:10.1016/0097-3165(72)90003-9, МИСТЕР  0306064.
  • Кнут, Дональд Э. (2005), «Проект раздела 7.2.1.6: Создание всех деревьев», Искусство программирования, IV, п. 34.
  • Тамари, Дов (1962), «Алгебра скобок и их перечисление», Nieuw Archief voor Wiskunde, Ser. 3, 10: 131–146, МИСТЕР  0146227.