Числа Шрёдера — Гиппарха

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

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

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

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

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

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

Последовательность чисел Каталана и последовательность чисел Шрёдера — Гиппарха при рассмотрении как бесконечномерные вектора, являются единственными собственными векторами для первых двух из последовательности естественным образом определённых линейных операторов на последовательностях чисел[6][7]. Более обще, k-ая последовательность в этой последовательности целых последовательностей равна ${\displaystyle (x_{1},x_{2},x_{3},\dots )}$, где числа 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 S(n)={\frac {1}{n}}\left((6n-9)S(n-1)-(n-3)S(n-2)\right).}$

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

Диалог Плутарха (из книги «Застольные беседы») содержит строку:

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

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

Задача подсчёта расстановок скобок была представлена современной математики Шрёдером[11].

Вычисление Плутархом двух чисел Гиппарха обнаруживает разногласие между Гиппархом и более ранним греческим философом Хрисиппом, который утверждал, что число сложных утверждений, которые можно получить из десяти простых утверждений, достигает миллиона. Представитель современной философии Сюзанна Бобзин[12] возражала, что вычисление Хрисиппа было верно, основываясь на анализе стоической логики. Сюзанна Бобзин реконструировала вычисления как Хрисиппа, так и Гиппарха, и заявила, что метод, которым Гиппарх получил свои математически верные результаты при его неверной стоической логике, проливает новый свет на стоические понятия конъюнкции и утверждения[13].

• Weisstein, Eric W. Super Catalan Number (англ.) на сайте Wolfram MathWorld.
• The Hipparchus Operad, The n-Category Café, April 1, 2013