Число Шредера – Гиппарха

Число в комбинаторике

Одиннадцать подразделений пятиугольника

В комбинаторике числа Шредера -Гиппарха образуют целочисленную последовательность , которую можно использовать для подсчета плоских деревьев с заданным набором листьев, способов вставки круглых скобок в последовательность и способов разделения выпуклого многоугольника на меньшие многоугольники путем вставки диагонали. Эти цифры начинаются

1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ... (последовательность A001003 в OEIS ).

Их также называют суперкаталонскими числами , маленькими числами Шредера или числами Гиппарха , в честь Эжена Шарля Каталана и его каталонских чисел , Эрнста Шредера и тесно связанных чисел Шредера , а также древнегреческого математика Гиппарха , который появляется в свидетельствах Плутарха. знать об этих числах.

Приложения комбинаторного перечисления

Комбинаторная эквивалентность между подразделениями многоугольника, плоскими деревьями и скобками.

Числа Шредера – Гиппархуса можно использовать для подсчета нескольких тесно связанных комбинаторных объектов: ^{[1] [2] [3] [4]}

• n - е число в последовательности подсчитывает различные способы разделения многоугольника с n  + 1 сторонами на меньшие многоугольники путем добавления диагоналей исходного многоугольника.
• n - е число учитывает различные плоские деревья с n листьями и всеми внутренними вершинами, имеющими двух или более дочерних элементов.
• n - е число учитывает различные способы вставки круглых скобок в последовательность из n  + 1 символов, при этом каждая пара круглых скобок окружает два или более символов или группы в скобках и без каких-либо круглых скобок, окружающих всю последовательность.
• n- е число подсчитывает грани всех измерений ассоциэдра K n _{+  1} размерности n  − 1, включая сам ассоциэдр как грань, но не включая пустое множество. Например, двумерный ассоциэдр К ₄ представляет собой пятиугольник ; у него пять вершин, пять граней и один целый ассоциэдр, всего 11 граней.

Как видно из рисунка, между этими объектами существует простая комбинаторная эквивалентность: подразделение многоугольника имеет плоское дерево как форму своего двойственного графа , листья дерева соответствуют символам в скобках, а внутренние узлы дерево, отличное от корня, соответствует группам в скобках. Сама последовательность в скобках может быть записана по периметру многоугольника с ее символами на сторонах многоугольника и скобками на концах выбранных диагоналей. Эта эквивалентность обеспечивает взаимно однозначное доказательство того, что все эти виды объектов учитываются одной целочисленной последовательностью. ^[2]

Те же числа также учитывают двойные перестановки (последовательности чисел от 1 до n , каждое число появляется дважды, причем первые вхождения каждого числа отсортированы), которые позволяют избежать шаблонов перестановок 12312 и 121323. ^[5]

Связанные последовательности

Тесно связанные большие числа Шредера равны удвоенным числам Шредера-Гиппарха и могут также использоваться для подсчета нескольких типов комбинаторных объектов, включая определенные виды путей решетки, разбиения прямоугольника на меньшие прямоугольники путем рекурсивного разрезания и заключения в круглые скобки, в которых допускается также пара круглых скобок, заключающих всю последовательность элементов. Каталонские числа также учитывают тесно связанные наборы объектов, включая подразделения многоугольника на треугольники, плоские деревья, в которых все внутренние узлы имеют ровно два дочерних узла, и круглые скобки, в которых каждая пара круглых скобок окружает ровно два символа или группы в скобках. ^[3]

Последовательность каталонских чисел и последовательность чисел Шредера – Гиппарха, рассматриваемые как бесконечномерные векторы , являются уникальными собственными векторами для первых двух в последовательности естественно определенных линейных операторов на числовых последовательностях. ^{[6] [7]} В более общем смысле, k -я последовательность в этой последовательности целочисленных последовательностей равна ( x ₁ , x ₂ , x ₃ , ...), где числа x _n вычисляются как суммы чисел Нараяны , умноженные на степени. из  к . Это можно выразить в виде гипергеометрической функции :

${\displaystyle x_{n}=\sum _{i=1}^{n}N(n,i)\,k^{i-1}=\sum _{i=1}^{n}{\frac {1}{n}}{n \choose i}{n \choose i-1}k^{i-1}={}_{2}F_{1}(1-n,-n;2;k).}$

Подстановка k  = 1 в эту формулу дает числа Каталана, а подстановка k  = 2 в эту формулу дает числа Шредера – Гиппарха. ^[7]

В связи со свойством чисел Шрёдера–Гиппарха считающих граней ассоциаэдра число вершин ассоциэдра задается каталонскими числами. Соответствующие числа для пермутоэдра — это соответственно упорядоченные числа Белла и факториалы .

Повторение

Как и приведенная выше формула суммирования, числа Шредера – Гиппархуса могут быть определены рекуррентным соотношением :

${\displaystyle x_{n}={\frac {1}{n}}\left((6n-9)x_{n-1}-(n-3)x_{n-2}\right).}$

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

История

В диалоге Плутарха « Застольная беседа» есть строчка:

Хрисипп говорит, что число сложных предложений, которые можно составить всего из десяти простых предложений, превышает миллион. (Гиппарх, правда, опроверг это, показав, что в утвердительной стороне имеется 103 049 сложных высказываний, а в отрицательной — 310 952.) ^[8]

Это утверждение оставалось необъяснимым до 1994 года, когда Дэвид Хаф, аспирант Университета Джорджа Вашингтона , заметил, что существует 103049 способов вставить круглые скобки в последовательность из десяти элементов. ^{[1] [8] [10]} Историк математики Фабио Ачерби ( CNRS ) показал, что аналогичное объяснение можно дать и для другого числа: оно очень близко к среднему десятому и одиннадцатому числам Шредера – Гиппарха, 310954. , и считает скобки из десяти терминов вместе с отрицательной частицей. ^[10]

Проблема подсчета скобок была введена в современную математику Шредером (1870). ^[11]

Пересказ Плутархом двух чисел Гиппарха фиксирует разногласия между Гиппархом и более ранним философом-стоиком Хрисиппом , который утверждал, что количество сложных предложений, которые можно составить из 10 простых предложений, превышает миллион. Современный философ Сюзанна Бобзиен  (2011) утверждала, что расчет Хрисиппа был правильным, основываясь на ее анализе стоической логики . Бобзиен реконструирует расчеты Хрисиппа и Гиппарха и говорит, что показ того, как Гиппарх правильно выполнил свою математику, но неправильная стоическая логика, может пролить новый свет на стоические представления о соединениях и утверждениях. ^[12]

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

1. Стэнли, Ричард П. (1997, 1999), Исчислительная комбинаторика , Издательство Кембриджского университета. Упражнение 1.45, вып. я, с. 51; том. II, стр. 176–178 и с. 213.
2. Шапиро, Луи В .; Суланке, Роберт А. (2000), «Биекции для чисел Шредера», Mathematics Magazine , 73 (5): 369–376, doi : 10.2307/2690814, JSTOR  2690814, MR  1805263.
3. Etherington, IMH (1940), «Некоторые проблемы неассоциативных комбинаций (I)», Edinburgh Mathematical Notes , 32 : 1–6, doi : 10.1017/S0950184300002639.
4. Холткамп, Ральф (2006), «О структурах алгебры Хопфа над свободными операдами», Успехи в математике , 207 (2): 544–565, arXiv : math/0407074 , doi : 10.1016/j.aim.2005.12.004, MR  2271016, S2CID  15908662.
5. Чен, Уильям Ю.К.; Мансур, Туфик; Ян, Шерри Х.Ф. (2006), «Сопоставления, избегающие частичных шаблонов», Электронный журнал комбинаторики , 13 (1): Research Paper 112, 17 стр. (электронный), doi : 10.37236/1138 , MR  2274327.
6. Бернштейн, М.; Слоан, NJA (1995), «Некоторые канонические последовательности целых чисел», Линейная алгебра и ее приложения , 226/228: 57–72, arXiv : math/0205301 , doi : 10.1016/0024-3795(94)00245-9, MR  1344554, S2CID  14672360.
7. Кокер, Кертис (2004), «Семейство собственных последовательностей», Discrete Mathematics , 282 (1–3): 249–250, doi : 10.1016/j.disc.2003.12.008 , MR  2059525.
8. Стэнли, Ричард П. (1997), «Гиппарх, Плутарх, Шредер и Хаф» (PDF) , American Mathematical Monthly , 104 (4): 344–350, doi : 10.2307/2974582, JSTOR  2974582, MR  1450667.
9. Фоата, Доминик ; Зейлбергер, Дорон (1997), «Классическое доказательство повторения очень классической последовательности», Журнал комбинаторной теории , серия A, 80 (2): 380–384, arXiv : math/9805015 , doi : 10.1006/jcta. 1997.2814, МР  1485153, S2CID  537142.
10. Ачерби, Ф. (2003), «На плечах Гиппарха: переоценка древнегреческой комбинаторики» (PDF) , Архив истории точных наук , 57 : 465–502, doi : 10.1007/s00407-003-0067 -0, S2CID  122758966, заархивировано из оригинала (PDF) 21 июля 2011 г..
11. Шредер, Эрнст (1870), "Vier kombinatorische Issuee", Zeitschrift für Mathematik und Physik , 15 : 361–376.
12. Бобзиен, Сюзанна (лето 2011 г.), «Комбинаторика стоического соединения: Гиппарх опровергнут, Хрисипп подтвержден» (PDF) , Оксфордские исследования по древней философии , XL : 157–188.

Внешние ссылки

• Вайсштейн, Эрик В. , «Суперкаталонское число», MathWorld
• Операда «Гиппарх», кафе n-Category, 1 апреля 2013 г.