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

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

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

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

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

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

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

Формула

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

начиная с базового случая .[4]

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

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

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

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

Приложения

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

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

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

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

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

  1. ^ а б Этерингтон, И. М. Х. (1937), «Неассоциированные степени и функциональное уравнение», Математический вестник, 21 (242): 36–39, 153, Дои:10.2307/3605743, JSTOR  3605743.
  2. ^ а б Этерингтон, И. М. Х. (1939), «О неассоциативных комбинациях», Proc. Royal Soc. Эдинбург, 59 (2): 153–162, Дои:10.1017 / S0370164600012244.
  3. ^ а б Веддерберн, Дж. Х. М. (1923), "Функциональное уравнение ", Анналы математики, 24 (2): 121–140, Дои:10.2307/1967710, JSTOR  1967710.
  4. ^ а б c d Слоан, Н. Дж. А. (ред.). «Последовательность A001190». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS..
  5. ^ Бона, Миклош; Флажоле, Филипп (2009), «Изоморфизм и симметрии в случайных филогенетических деревьях», Журнал прикладной теории вероятностей, 46 (4): 1005–1019, arXiv:0901.0696, Bibcode:2009arXiv0901.0696B, Дои:10.1239 / jap / 1261670685, МИСТЕР  2582703, S2CID  5452364.
  6. ^ Выдра, Ричард (1948), «Число деревьев», Анналы математики, Вторая серия, 49 (3): 583–599, Дои:10.2307/1969046, JSTOR  1969046, МИСТЕР  0025715.
  7. ^ а б Murtagh, Fionn (1984), "Подсчет дендрограмм: обзор", Дискретная прикладная математика, 7 (2): 191–199, Дои:10.1016 / 0166-218X (84) 90066-0, МИСТЕР  0727923.
  8. ^ Cyvin, S.J .; Brunvoll, J .; Цивин, Б. (1995), "Перечень конституциональных изомеров полиенов", Журнал молекулярной структуры: ТЕОХИМА, 357 (3): 255–261, Дои:10.1016/0166-1280(95)04329-6.
  9. ^ Маурер, Вилли (1975), «О наиболее эффективных планах турниров с меньшим количеством игр, чем у конкурентов», Анналы статистики, 3 (3): 717–727, Дои:10.1214 / aos / 1176343135, JSTOR  2958441, МИСТЕР  0371712.
  10. ^ Эта эквивалентность между деревьями и элементами свободной коммутативной магмы на одном генераторе утверждается как «хорошо известная и легко видимая». Розенберг, И. Г. (1986), "Структурная жесткость. II. Почти бесконечно жесткие стержневые каркасы", Дискретная прикладная математика, 13 (1): 41–59, Дои:10.1016 / 0166-218X (86) 90068-5, МИСТЕР  0829338.
  11. ^ Ландау, Б. В. (1977), "Асимптотическое разложение для последовательности Веддерберна-Этерингтона", Математика, 24 (2): 262–265, Дои:10.1112 / s0025579300009177, МИСТЕР  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, МИСТЕР  2497008.
  14. ^ Iserles, A .; Норсетт, С. П. (1999), «О решении линейных дифференциальных уравнений в группах Ли», Философские труды Лондонского королевского общества. Серия A: математические, физические и инженерные науки, 357 (1754): 983–1019, Bibcode:1999RSPTA.357..983I, Дои:10.1098 / rsta.1999.0362, МИСТЕР  1694700, S2CID  90949835.

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