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

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

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

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

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

• 1 Приложения комбинаторного перечисления
• 2 Связанные последовательности
• 3 Повторяемость
• 4 История
• 5 Ссылки
• 6 Внешние ссылки

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

Числа Шредера – Гиппарха могут использоваться для подсчета нескольких тесно связанных комбинаторных объектов:

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

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

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

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

Последовательность каталонских чисел и последовательность чисел Шредера – Гиппарха, рассматриваемая как бесконечномерные векторы, являются уникальными собственными векторами для первых двух в последовательность естественно определенных линейных операторов над числовыми последовательностями. В более общем смысле, k-я последовательность в этой последовательности целочисленных последовательностей имеет вид (x 1, x 2, x 3,...), где числа x n вычисляются как сумма чисел Нараяны, умноженных на степени k. Это может быть выражено как гипергеометрическая функция :

$xn\; =\; \sum \; i\; =\; 1\; n\; N\; (n,\; i)\; ki\; -\; 1\; =\; \sum \; i\; =\; 1\; n\; 1\; n\; (ni)\; (ni\; -\; 1)\; ki\; -\; 1\; =\; 2\; F\; 1\; (1\; -\; n,\; -\; n;\; 2;\; k).\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; N\; (n,\; i)\; \backslash ,\; k\; ^\; \{i-1\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; \{n\; \backslash \; choose\; i\}\; \{n\; \backslash \; choose\; i-1\}\; k\; ^\; \{i-1\}\; =\; \{\}\; \_\; \{2\}\; F\_\; \{1\}\; (1-n,\; -n;\; 2;\; k).\}$

Подстановка k = 1 в эту формулу дает каталонские числа, а замена k = 2 в эту формулу дает числа Шредера-Гиппарха.

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

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

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

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

Диалог Плутарха Застольная беседа содержит line:

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

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

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

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

• Вайсштейн, Эрик У. «Супер каталонский номер». MathWorld.
• The Hipparchus Operad, The n-Category Café, 1 апреля 2013 г.