Число Шредера – Гиппарха - Schröder–Hipparchus number

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

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

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

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

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

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

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

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

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

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

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

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

Последовательность каталонских чисел и последовательность чисел Шредера – Гиппарха, рассматриваемая как бесконечномерная векторов, являются уникальными собственные векторы для первых двух в последовательности естественно определенных линейных операторов над числовыми последовательностями.^[6][7] В более общем плане k-я последовательность в этой последовательности целочисленных последовательностей равна (Икс₁, Икс₂, Икс₃, ...) где числа Икс_п рассчитываются как суммы Числа Нараяны умноженный на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]

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

Повторение

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

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

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

История

Плутарха диалог Застольный разговор содержит строку:

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

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

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

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

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

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

внешняя ссылка

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