Решетка Юнга–Фибоначчи

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

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

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

В древнеиндийском исследовании просодии числа Фибоначчи использовались для подсчета количества различных последовательностей коротких и длинных слогов с заданной общей длиной; если цифра 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), этот граф обладает следующими свойствами:

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

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

Транзитивное замыкание графа Юнга–Фибоначчи является частичным порядком . Как показывает Стэнли (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}, образует алмазную подрешетку, запрещенную в дистрибутивных решетках.

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