Войти
Граф Юнга – Фибоначчи, диаграмма Хассе решетки Юнга – Фибоначчи. В математике, граф Юнга – Фибоначчи и решетка Юнга – Фибоначчи, названная в честь Альфреда Янга и Леонардо Фибоначчи, являются двумя тесно связанными структурами, включающими последовательности цифр 1 и 2. Любой последовательности цифр этого типа может быть присвоен ранг, сумма его цифр: например, ранг 11212 равен 1 + 1 + 2 + 1 + 2 = 7. Как уже было известно в древней Индии, количество последовательностей с заданным рангом - это число Фибоначчи. Решетка Юнга – Фибоначчи представляет собой бесконечную модульную решетку, имеющую в качестве элементов эти последовательности цифр, совместимые с этой ранговой структурой. Граф Юнга – Фибоначчи является графом этой решетки и имеет вершину для каждой последовательности цифр. Как граф модульной решетки, это модульный граф.
Граф Юнга – Фибоначчи и решетка Юнга – Фибоначчи были первоначально изучены в двух работах Фомина (1988) и Стэнли (1988). Они названы в честь тесно связанной решетки Юнга и числа Фибоначчи их элементов в любом заданном ранге.
Последовательность цифр с рангом r может быть сформирована либо путем добавления цифры 2 к последовательности с рангом r - 2, либо путем добавления цифры 1 к последовательности с рангом r - 1. Если f (r) - функция, отображающая r к количеству различных последовательностей цифр этого ранга, следовательно, f удовлетворяет рекуррентному соотношению f (r) = f (r - 2) + f (r - 1), определяющему Fibonacci чисел, но с немного другими начальными условиями: f (0) = f (1) = 1 (есть одна строка с рангом 0, пустая строка и одна строка с рангом 1, состоящая из единственная цифра 1). Эти начальные условия приводят к смещению последовательности значений f на одну позицию относительно чисел Фибоначчи: f (r) = F r + 1, где F i обозначает i-е число Фибоначчи..
В древнеиндийском исследовании просодии числа Фибоначчи использовались для подсчета количества различных последовательностей коротких и длинных слогов с заданной общей длиной; если цифра 1 соответствует короткому слогу, а цифра 2 соответствует длинному слогу, ранг последовательности цифр измеряет общую длину соответствующей последовательности слогов. Подробнее см. В статье Число Фибоначчи.
Граф Янга – Фибоначчи представляет собой бесконечный граф, с вершиной для каждой строки цифр «1» и «2» (включая пустая строка ). Соседями строки s являются строки, сформированные из s с помощью одной из следующих операций:
Несложно проверить, что каждая операция может быть инвертирована: операции 1 и 3 являются обратными друг другу, как и операции 2 и 4 Следовательно, полученный граф можно рассматривать как неориентированный. Однако обычно считается направленным ациклическим графом, в котором каждое ребро соединяется от вершины более низкого ранга к вершине более высокого ранга.
Как отмечают оба Фомин (1988) и Стэнли (1988), этот граф имеет следующие свойства:
Фомин (1988) называет граф с этими свойствами Y-графом; Стэнли (1988) называет граф с более слабой версией этих свойств (в котором количество общих предшественников и общих наследников любой пары узлов должно быть равно, но может быть больше единицы) графом дифференциальный poset.
транзитивное замыкание графа Юнга – Фибоначчи является частичным порядком. Как показывает Stanley (1988), любые две вершины x и y имеют единственного наибольшего общего предшественника в этом порядке (их встреча) и уникального наименьшего общего преемника (их соединение); таким образом, этот порядок представляет собой решетку , называемую решеткой Юнга – Фибоначчи.
Чтобы найти пересечение x и y, можно сначала проверить, является ли один из x и y предшественником другого. Строка x является предшественницей другой строки y именно в этом порядке, когда количество «2» цифр, оставшихся в y, после удаления самого длинного общего суффикса x и y, по крайней мере, равно количеству всех оставшихся цифр в x после удаления общего суффикса. Если x является предшественником y в соответствии с этим тестом, то их встреча - это x, и аналогично, если y является предшественником x, то их встречей является y. Во втором случае, если ни x, ни y не являются предшественниками другого, но один или оба из них начинаются с цифры «1», совпадение не изменяется, если эти начальные цифры удалены. И, наконец, если и x, и y начинаются с цифры «2», совпадение x и y можно найти, удалив эту цифру из них обоих, найдя совпадение полученных суффиксов и добавив «2» обратно к начало.
Общий преемник x и y (хотя и не обязательно наименьший общий преемник) можно найти, взяв строку из «2» цифр с длиной, равной большей из x и y. Тогда наименьший общий преемник - это совпадение конечного числа строк, которые являются общими преемниками x и y и предшественниками этой строки из «2».
Как далее отмечает Стэнли (1988), решетка Юнга – Фибоначчи модульна. Фомин (1988) неверно утверждает, что это дистрибутив ; однако подрешетка, образованная цепочками {21,22,121,211,221}, образует алмазную подрешетку, запрещенную в распределительных решетках.
