Решетка Юнга – Фибоначчи - Young–Fibonacci lattice

Граф Юнга – Фибоначчи, Диаграмма Хассе решетки Юнга – Фибоначчи.

В математика, то График Юнга – Фибоначчи и Решетка Юнга – Фибоначчи, названный в честь Альфред Янг и Леонардо Фибоначчи, являются двумя тесно связанными структурами, включающими последовательности цифр 1 и 2. Любой последовательности цифр этого типа можно присвоить классифицировать, сумма цифр: например, ранг 11212 равен 1 + 1 + 2 + 1 + 2 = 7. Как уже было известно в древней Индии, количество последовательностей с данным рангом равно Число Фибоначчи. Решетка Юнга – Фибоначчи представляет собой бесконечную модульная решетка имеющий эти последовательности цифр в качестве своих элементов, совместимых с этой ранговой структурой. Граф Юнга – Фибоначчи является графом этой решетки и имеет вершину для каждой последовательности цифр. Как граф модульной решетки, это модульный граф.

Граф Юнга – Фибоначчи и решетка Юнга – Фибоначчи были первоначально изучены в двух статьях автора. Фомин (1988) и Стэнли (1988). Они названы в честь близкородственных Решетка Юнга и после числа Фибоначчи их элементов в любом заданном ранге.

Последовательности цифр с заданным рангом

Последовательность цифр с рангом р может быть образован либо добавлением цифры 2 к последовательности с рангом р − 2, или добавив цифру 1 к последовательности с рангом р − 1. Если ж(р) функция, отображающая р к количеству различных последовательностей цифр этого ранга, следовательно, ж удовлетворяет отношение повторения ж(р) = ж(р − 2) + ж(р − 1) определение Фибоначчи числа, но с немного другими начальными условиями: ж(0) = ж(1) = 1 (есть одна строка ранга 0, пустой строкой, и одна строка ранга 1, состоящая из одной цифры 1). Эти начальные условия вызывают последовательность значений ж сдвигаться на одну позицию от чисел Фибоначчи: ж(р) = Fр + 1 где Fя обозначает я-е число Фибоначчи.

В древнеиндийском исследовании просодия числа Фибоначчи использовались для подсчета количества различных последовательностей коротких и длинных слогов с заданной общей длиной; если цифра 1 соответствует короткому слогу, а цифра 2 соответствует длинному слогу, ранг последовательности цифр измеряет общую длину соответствующей последовательности слогов. Увидеть Число Фибоначчи статью для подробностей.

Графики последовательностей цифр

Граф Юнга – Фибоначчи представляет собой бесконечную график, с вершиной для каждой строки цифр «1» и «2» (включая пустой строкой ). Соседи строки s струны сформированы из s одной из следующих операций:

  1. Вставьте «1» в s, перед самой левой цифрой "1" (или где-нибудь в s если он еще не содержит «1»).
  2. Измените крайнюю левую «1» из s в «2».
  3. Удалите крайнюю левую цифру «1» из s.
  4. Замените «2», слева от которого нет «1», на «1».

Несложно проверить, что каждая операция может быть инвертирована: операции 1 и 3 обратны друг другу, как и операции 2 и 4. Таким образом, полученный граф можно считать ненаправленный. Однако обычно считается ориентированный ациклический граф в котором каждое ребро соединяется от вершины более низкого ранга к вершине более высокого ранга.

Как оба Фомин (1988) и Стэнли (1988) Обратите внимание, этот граф обладает следующими свойствами:

  • Он связан: ранг любой непустой строки может быть понижен с помощью некоторой операции, поэтому существует последовательность операций, ведущих от нее к пустой строке, изменение направления на которое дает направленный путь в графе от пустой строки к каждой другой вершине.
  • Он совместим со структурой рангов: каждый направленный путь имеет длину, равную разнице рангов его конечных точек.
  • Для каждых двух различных узлов ты и v, число общих непосредственных предшественников ты и v равно количеству общих непосредственных преемников ты и v; это число равно нулю или единице.
  • Исходная степень каждой вершины равна единице плюс ее входная степень.

Фомин (1988) называет граф с этими свойствами Y-граф; Стэнли (1988) называет граф с более слабой версией этих свойств (в котором количество общих предшественников и общих наследников любой пары узлов должно быть равно, но может быть больше единицы) графом дифференциальное положение.

Частичный порядок и структура решетки

В переходное закрытие графа Юнга – Фибоначчи является частичный заказ. В качестве Стэнли (1988) показывает, любые две вершины Икс и у имеют уникального наибольшего общего предшественника в этом порядке (их встреча) и уникальный наименее общий преемник (их присоединиться); таким образом, этот заказ является решетка, называемую решеткой Юнга – Фибоначчи.

Чтобы найти встречу Икс и у, можно сначала проверить, действительно ли один из Икс и у является предшественником другого. Строка Икс является предшественником другой строки у именно в таком порядке, когда количество "2" цифр, оставшихся в у, после удаления самого длинного общего суффикса Икс и у, по крайней мере равно количеству всех оставшихся цифр в Икс после удаления общего суффикса. Если Икс является предшественником у согласно этому тесту, то их встреча Икс, и аналогично, если у является предшественником Икс тогда их встреча у. Во втором случае, если ни один Икс ни у является предшественником другого, но один или оба из них начинаются с цифры «1», совпадение не изменится, если эти начальные цифры удалить. И наконец, если оба Икс и у начинаются с цифры «2», совпадение Икс и у можно найти, удалив эту цифру из них обоих, найдя совпадение полученных суффиксов и добавив «2» обратно в начало.

Общий преемник Икс и у (хотя и не обязательно наименьший общий преемник) можно найти, взяв строку из «2» цифр с длиной, равной более длинной из Икс и у. Тогда наименьший общий преемник - это совпадение конечного числа строк, которые являются общими преемниками Икс и у и предшественники этой строки «2».

В качестве Стэнли (1988) Далее следует, что решетка Юнга – Фибоначчи имеет вид модульный. Фомин (1988) неверно утверждает, что это распределительный; однако подрешетка, образованная цепочками {21,22,121,211,221}, образует алмазную подрешетку, запрещенную в распределительных решетках.

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

  • Фомин, С. В. (1988), "Обобщенное соответствие Робинсона – Шенстеда – Кнута", Журнал математических наук, 41 (2): 979–991, Дои:10.1007 / BF01247093. Переведено с Записки научных семинаров Ленинградского отделения Математического института им. Стеклова АН СССР 155: 156–175, 1986.
  • Стэнли, Ричард П. (1988), "Дифференциальные посец", Журнал Американского математического общества, 1 (4): 919–961, Дои:10.2307/1990995, JSTOR  1990995.