WikiDer > Число Веддерберна – Этерингтона - Википедия

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

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

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

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

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

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

Формула

Числа Веддерберна – Этерингтона могут быть рассчитаны с использованием отношение повторения

${ 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}}$

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

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

Скорость роста

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

${ displaystyle a_ {n} приблизительно { 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]

Приложения

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

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

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

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

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

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

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

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