Число Уэддерберна – Этерингтона

Числа Веддерберна -Этерингтона представляют собой целочисленную последовательность , названную в честь Айвора Малкольма Хэддона Этерингтона ^{[1] [2]} и Джозефа Веддерберна ^[3] , которую можно использовать для подсчета определенных видов бинарных деревьев . Первые несколько чисел в последовательности:

0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, ... ( OEIS : A001190 )

Комбинаторная интерпретация

Деревья выдры и слабо бинарные деревья, два типа корневых двоичных деревьев, подсчитываемых числами Веддерберна – Этерингтона.

Эти числа можно использовать для решения ряда задач комбинаторного перечисления . n - е число в последовательности (начиная с цифры 0 для n  = 0) считается

• Количество неупорядоченных корневых деревьев с n листьями, в которых все узлы, включая корень, имеют либо ноль, либо ровно два потомка. ^[4] Эти деревья были названы деревьями Выдры, ^[5] в честь работы Ричарда Оттера по их комбинаторному перечислению. ^[6] Их также можно интерпретировать как немаркированные и неранжированные дендрограммы с заданным количеством листьев. ^[7]
• Количество неупорядоченных корневых деревьев с n узлами, в которых корень имеет степень ноль или один, а все остальные узлы имеют не более двух дочерних элементов. ^[4] Деревья, в которых корень имеет не более одного дочернего элемента, называются посаженными деревьями, а дополнительное условие, согласно которому другие узлы имеют не более двух дочерних элементов, определяет слабо бинарные деревья. В химической теории графов эти деревья можно интерпретировать как изомеры полиенов с обозначенным атомом листа , выбранным в качестве корня. ^[8]
• Количество различных способов организации турнира на выбывание для n игроков (с оставлением имен игроков пустыми перед посевом игроков в турнир). ^[9] Пары такого турнира можно описать деревом Выдры.
• Число различных результатов, которые могут быть получены с помощью различных способов группировки выражения для операции двоичного умножения, которая считается коммутативной, но не ассоциативной и не идемпотентной . ^[4] Например, можно сгруппировать в двоичные умножения тремя способами: , или . Эту интерпретацию первоначально рассматривали как Этерингтон ^{[1] [2],} так и Веддерберн. ^[3] Дерево Выдры можно интерпретировать как сгруппированное выражение, в котором каждый листовой узел соответствует одной из копий, а каждый нелистовой узел соответствует операции умножения. С другой стороны, набор всех деревьев Выдры с операцией двоичного умножения, которая объединяет два дерева, делая их двумя поддеревьями нового корневого узла, можно интерпретировать как свободную коммутативную магму на одном генераторе (дерево с одним узлом ). В этой алгебраической структуре каждая группа имеет в качестве значения одно из n -листных деревьев Выдры. ^[10] ${\displaystyle x^{n}}$ ${\displaystyle x^{5}}$ ${\displaystyle x(x(x(xx)))}$ ${\displaystyle x((xx)(xx))}$ ${\displaystyle (xx)(x(xx))}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x^{n}}$

Формула

Числа Веддерберна – Этерингтона можно рассчитать с помощью рекуррентного соотношения

${\displaystyle a_{2n-1}=\sum _{i=1}^{n-1}a_{i}a_{2n-i-1}}$

${\displaystyle a_{2n}={\frac {a_{n}(a_{n}+1)}{2}}+\sum _{i=1}^{n-1}a_{i}a_{2n-i}}$

начиная с базового варианта . ^[4] ${\displaystyle a_{1}=1}$

С точки зрения интерпретации этих чисел как подсчета корневых бинарных деревьев с n листьями, суммирование в рекурсии учитывает различные способы разделения этих листьев на два подмножества и формирования поддерева, каждое подмножество которого является его листьями. Формула для четных значений n несколько сложнее, чем формула для нечетных значений, чтобы избежать двойного счета деревьев с одинаковым количеством листьев в обоих поддеревьях. ^[7]

Темпы роста

Числа Веддерберна–Этерингтона асимптотически растут как

${\displaystyle a_{n}\approx {\sqrt {\frac {\rho +\rho ^{2}B'(\rho ^{2})}{2\pi }}}{\frac {\rho ^{-n}}{n^{3/2}}},}$

где B — производящая функция чисел, а ρ — ее радиус сходимости , примерно 0,4027 (последовательность A240943 в OEIS ), и где константа, заданная частью выражения в квадратном корне, равна примерно 0,3188 (последовательность A245651 в OEIS ). ОЭИС ). ^[11]

Приложения

Young & Yung (2003) используют числа Веддерберна-Этерингтона как часть конструкции системы шифрования , содержащей скрытый бэкдор . Когда ввод, который должен быть зашифрован их системой, может быть достаточно сжат с помощью кодирования Хаффмана , он заменяется сжатой формой вместе с дополнительной информацией, которая передает ключевые данные злоумышленнику. В этой системе форма дерева кодирования Хаффмана описывается как дерево Оттера и кодируется двоичным числом в интервале от 0 до числа Уэддерберна–Этерингтона для количества символов в коде. Таким образом, при кодировании используется очень небольшое количество битов — логарифм по основанию 2 числа Веддерберна-Этерингтона. ^[12]

Фарзан и Манро (2008) описывают аналогичную технику кодирования корневых неупорядоченных двоичных деревьев, основанную на разбиении деревьев на небольшие поддеревья и кодировании каждого поддерева как числа, ограниченного числом Веддерберна-Этерингтона для его размера. Их схема позволяет закодировать эти деревья в количестве битов, близком к нижней границе теории информации (логарифму по основанию 2 числа Веддерберна – Этерингтона), при этом позволяя выполнять операции навигации внутри дерева с постоянным временем. ^[13]

Изерлес и Норсетт (1999) используют неупорядоченные двоичные деревья, а также тот факт, что числа Веддерберна – Этерингтона значительно меньше, чем числа, которые подсчитывают упорядоченные двоичные деревья, чтобы значительно уменьшить количество членов в последовательном представлении решения некоторых дифференциальных уравнений. . ^[14]

Смотрите также

• Каталонский номер

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

1. Etherington, IMH (1937), «Неассоциированные степени и функциональное уравнение», Mathematical Gazette , 21 (242): 36–39, 153, doi : 10.2307/3605743, JSTOR  3605743, S2CID  126360684.
2. Etherington, IMH (1939), «О неассоциативных комбинациях», Proc. Р. Сок. Эдинбург , 59 (2): 153–162, номер документа : 10.1017/S0370164600012244..
3. Веддерберн, JHM (1923), «Функциональное уравнение », Annals of Mathematics , 24 (2): 121–140, doi : 10.2307/1967710, JSTOR  1967710 ${\displaystyle g(x^{2})=2ax+[g(x)]^{2}}$.
4. Слоан, Нью-Джерси (ред.). «Последовательность A001190». Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС..
5. Бона, Миклош ; Флажоле, Филипп (2009), «Изоморфизм и симметрии в случайных филогенетических деревьях», Journal of Applied Probability , 46 (4): 1005–1019, arXiv : 0901.0696 , Bibcode : 2009arXiv0901.0696B, doi : 10.1239/jap/1261670685 , МР  2582703, S2CID  5452364.
6. Оттер, Ричард (1948), «Число деревьев», Анналы математики , вторая серия, 49 (3): 583–599, doi : 10.2307/1969046, JSTOR  1969046, MR  0025715.
7. Мурта, Фионн (1984), «Подсчет дендрограмм: обзор», Discrete Applied Mathematics , 7 (2): 191–199, doi : 10.1016/0166-218X(84)90066-0 , MR  0727923.
8. Сайвин, SJ; Брунволл, Дж.; Сайвин, Б.Н. (1995), «Перечень конституционных изомеров полиенов», Журнал молекулярной структуры: THEOCHEM , 357 (3): 255–261, doi : 10.1016/0166-1280(95)04329-6.
9. Маурер, Вилли (1975), «О наиболее эффективных турнирных планах с меньшим количеством игр, чем у конкурентов», The Annals ofStatistics , 3 (3): 717–727, doi : 10.1214/aos/1176343135 , JSTOR  2958441, MR  0371712.
10. Эта эквивалентность между деревьями и элементами свободной коммутативной магмы на одном генераторе заявлена ​​как «хорошо известная и легко видимая» Розенбергом , И.Г. (1986), «Структурная жесткость. II. Почти бесконечно жесткие стержневые каркасы», Discrete Applied Математика , 13 (1): 41–59, doi : 10.1016/0166-218X(86)90068-5 , МР  0829338.
11. Ландау, Б.В. (1977), «Асимптотическое разложение последовательности Веддерберна-Этерингтона», Mathematika , 24 (2): 262–265, doi : 10.1112/s0025579300009177, MR  0498168.
12. Янг, Адам; Юнг, Моти (2003), «Черные атаки на шифры черного ящика с использованием открытых текстов с низкой энтропией», Труды 8-й Австралазийской конференции по информационной безопасности и конфиденциальности (ACISP'03) , Конспекты лекций по информатике , том. 2727, Springer, стр. 297–311, номер документа : 10.1007/3-540-45067-X_26, ISBN. 978-3-540-40515-3.
13. Фарзан, Араш; Манро, Дж. Ян (2008), «Единый подход к краткому представлению деревьев», Теория алгоритмов - SWAT 2008 , Конспекты лекций по информатике, том. 5124, Springer, стр. 173–184, номер документа : 10.1007/978-3-540-69903-3_17, ISBN. 978-3-540-69900-2, МР  2497008.
14. Изерлес, А.; Норсетт, С.П. (1999), «О решении линейных дифференциальных уравнений в группах Ли», Философские труды Лондонского королевского общества. Серия A: Математические, физические и инженерные науки , 357 (1754): 983–1019, Бибкод : 1999RSPTA.357..983I, doi : 10.1098/rsta.1999.0362, MR  1694700, S2CID  90949835.

дальнейшее чтение

• Финч, Стивен Р. (2003), Математические константы, Энциклопедия математики и ее приложений, том. 94, Кембридж: Издательство Кембриджского университета, стр. 295–316, номер документа : 10.1017/CBO9780511550447, ISBN. 978-0-521-81805-6, МР  2003519.