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

Числа Веддерберна–Этерингтона — это целочисленная последовательность, названная в честь Айвора Малкольма Хэддона Этерингтона ^{[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]

Farzan & Munro (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. R. Soc. Эдинбург , 59 (2): 153–162, doi :10.1017/S0370164600012244.
3. Wedderburn, JHM (1923), "Функциональное уравнение ", Annals of Mathematics , 24 (2): 121–140, doi :10.2307/1967710, JSTOR  1967710 ${\displaystyle g(x^{2})=2ax+[g(x)]^{2}}$.
4. Sloane, N. J. A. (ред.). "Последовательность A001190". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS..
5. Бона, Миклош ; Флажоле, Филипп (2009), «Изоморфизм и симметрии в случайных филогенетических деревьях», Журнал прикладной теории вероятностей , 46 (4): 1005–1019, arXiv : 0901.0696 , Bibcode : 2009arXiv0901.0696B, doi : 10.1239/jap/1261670685, MR  2582703, S2CID  5452364.
6. Оттер, Ричард (1948), «Число деревьев», Annals of Mathematics , Вторая серия, 49 (3): 583–599, doi :10.2307/1969046, JSTOR  1969046, MR  0025715.
7. Murtagh, Fionn (1984), «Подсчет дендрограмм: обзор», Discrete Applied Mathematics , 7 (2): 191–199, doi : 10.1016/0166-218X(84)90066-0 , MR  0727923.
8. Cyvin, SJ; Brunvoll, J.; Cyvin, BN (1995), «Перечисление конституционных изомеров полиенов», Журнал молекулярной структуры: THEOCHEM , 357 (3): 255–261, doi :10.1016/0166-1280(95)04329-6.
9. Маурер, Вилли (1975), «О наиболее эффективных планах турниров с меньшим количеством игр, чем у конкурентов», The Annals of Statistics , 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) , Lecture Notes in Computer Science , т. 2727, Springer, стр. 297–311, doi :10.1007/3-540-45067-X_26, ISBN 978-3-540-40515-3.
13. Фарзан, Араш; Манро, Дж. Ян (2008), «Единый подход к краткому представлению деревьев», Теория алгоритмов — SWAT 2008 , Lecture Notes in Computer Science, т. 5124, Springer, стр. 173–184, doi :10.1007/978-3-540-69903-3_17, ISBN 978-3-540-69900-2, МР  2497008.
14. Iserles, A.; Nørsett, SP (1999), "О решении линейных дифференциальных уравнений в группах Ли", Philosophical Transactions of the Royal Society of London. Серия A: Математические, физические и инженерные науки , 357 (1754): 983–1019, Bibcode : 1999RSPTA.357..983I, doi : 10.1098/rsta.1999.0362, MR  1694700, S2CID  90949835.

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

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