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

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

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

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

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, включая сам ассоциаэдр как грань, но не включая пустое множество. Например, двумерный ассоциаэдр K ₄ является пятиугольником ; у него пять вершин, пять граней и один целый ассоциаэдр, всего 11 граней.

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

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

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

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

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

${\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. Stanley, Richard P. (1997, 1999), Enumerative Combinatorics , Cambridge University Press. Упражнение 1.45, т. I, стр. 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), «О структурах алгебры Хопфа над свободными операдами», Advances in Mathematics , 207 (2): 544–565, arXiv : math/0407074 , doi : 10.1016/j.aim.2005.12.004, MR  2271016, S2CID  15908662.
5. Чен, Уильям YC; Мансур, Туфик; Ян, Шерри HF (2006), «Сопоставления, избегающие частичных шаблонов», Electronic Journal of Combinatorics , 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. Coker, Curtis (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, MR  1485153, S2CID  537142.
10. Acerbi, F. (2003), «На плечах Гиппарха: переоценка древнегреческой комбинаторики» (PDF) , Архив для History of Exact Sciences , 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) , Oxford Studies in Ancient Philosophy , XL : 157–188.

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

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