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

Числа Уэддерберна-Этерингтона представляют собой целочисленную последовательность, названную в честь Айвора Малкольма Хэддона Этерингтона. ^{[ 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 ]} Пары такого турнира можно описать деревом Выдры.
Количество различных результатов, которые можно получить с помощью разных способов группировки выражения. $x^{n}$ для операции двоичного умножения, которая считается коммутативной , но не ассоциативной и не идемпотентной . ^{[ 4 ]} Например $x^{5}$ можно сгруппировать в двоичные умножения тремя способами: $x(x(x(xx)))$ , $x((xx)(xx))$ , или $(xx)(x(xx))$ . Именно эту интерпретацию первоначально рассматривали оба Этерингтона. ^{[ 1 ]}^{[ 2 ]} и Уэддерберн. ^{[ 3 ]} Дерево Выдры можно интерпретировать как сгруппированное выражение, в котором каждый листовой узел соответствует одной из копий дерева Выдры. $x$ и каждый нелистовой узел соответствует операции умножения. С другой стороны, набор всех деревьев Выдры с операцией двоичного умножения, которая объединяет два дерева, делая их двумя поддеревьями нового корневого узла, можно интерпретировать как свободную коммутативную магму на одном генераторе. $x$ (дерево с одним узлом). В этой алгебраической структуре каждая группа $x^{n}$ имеет в качестве значения одно из n -листных деревьев Выдры. ^{[ 10 ]}

Формула

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

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

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

начиная с базового случая $a_{1}=1$ . ^{[ 4 ]}

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

Темпы роста

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

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 ]}

См. также

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

Ссылки

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

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

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

[e37-1] Jump up to: ^а ^б Этерингтон, IMH (1937), «Неассоциированные степени и функциональное уравнение», Mathematical Gazette , 21 (242): 36–39, 153, doi : 10.2307/3605743 , JSTOR 3605743 , S2CID 126360684 .

[e39-2] Jump up to: ^а ^б Этерингтон, IMH (1939), «О неассоциативных сочетаниях», Proc. Р. Сок. Эдинбург , 59 (2): 153–162, номер документа : 10.1017/S0370164600012244 .

[w-3] Jump up to: ^а ^б Веддерберн, Дж. Х. М. (1923), «Функциональное уравнение $g(x^{2})=2ax+[g(x)]^{2}$ ", Annals of Mathematics , 24 (2): 121–140, doi : 10.2307/1967710 , JSTOR 1967710 .

[oeis-4] Jump up to: ^а ^б ^с ^д Слоан, Нью-Джерси (ред.). «Последовательность A001190» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС. .

[5] Бона, Миклош ; Флажоле, Филипп (2009), «Изоморфизм и симметрия в случайных филогенетических деревьях», Journal of Applied Probability , 46 (4): 1005–1019, arXiv : 0901.0696 , Bibcode : 2009arXiv0901.0696B , doi : 10.1239/jap/1261670685 , MR 2582703 , S2CID 5452364 .

[6] Оттер, Ричард (1948), «Число деревьев», Annals of Mathematics , Second Series, 49 (3): 583–599, doi : 10.2307/1969046 , JSTOR 1969046 , MR 0025715 .

[dendrogram-7] Jump up to: ^а ^б Мурта, Фионн (1984), «Подсчет дендрограмм: обзор», Discrete Applied Mathematics , 7 (2): 191–199, doi : 10.1016/0166-218X(84)90066-0 , MR 0727923 .

[8] Сайвин, С.Дж.; Брунволл, Дж.; Сайвин, Б.Н. (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. Почти бесконечно жесткие стержневые конструкции», Дискретная прикладная математика , 13 (1): 41–59, doi : 10.1016/0166-218X(86)90068-5 , MR 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, номер doi : 10.1007/978-3-540-69903-3_17 , ISBN. 978-3-540-69900-2 , МР 2497008 .

[14] Изерлес, А.; Норсетт, С.П. (1999), «О решении линейных дифференциальных уравнений в группах Ли» , «Философские труды Лондонского королевского общества». Серия A: Математические, физические и инженерные науки , 357 (1754): 983–1019, Bibcode : 1999RSPTA.357..983I , doi : 10.1098/rsta.1999.0362 , MR 1694700 , S2CID 90949835 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]