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

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

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

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

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

Приложения для комбинаторных перечислений

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

Числа Шрёдера — Гиппарха можно использовать для подсчёта некоторых тесно связанных комбинаторных объектов[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].

Примечания

1. Stanley, 1999, с. Exercise 1.45, vI/51; vII, /176–178, 213.
2. Shapiro, Sulanke, 2000, с. 369–376.
3. Etherington, 1940, с. 1–6.
4. Holtkamp, 2006, с. 544–565.
5. Chen, Mansour, Yan, 2006, с. Research Paper 112, 17 pp.
6. Bernstein, Sloane, 1995, с. 57–72.
7. Coker, 2004, с. 249–250.
8. Stanley, 1997, с. 344–350.
9. Foata, Zeilberger, 1997, с. 380–384.
10. Acerbi, 2003, с. 465–502.
11. Schröder, 1870, с. 361–376.
12. Bobzien, 2011.
13. Bobzien, 2011, с. 157–188.

Литература

• Louis W. Shapiro, Robert A. Sulanke. Bijections for the Schröder numbers // Mathematics Magazine. — 2000. — Т. 73, вып. 5. — С. 369–376. — doi:10.2307/2690814.
• Etherington I. M. H. Some problems of non-associative combinations (I) // Edinburgh Mathematical Notes. — 1940. — Т. 32. — С. 1–6. — doi:10.1017/S0950184300002639.
• Ralf Holtkamp. On Hopf algebra structures over free operads // Advances in Mathematics. — 2006. — Т. 207, вып. 2. — С. 544–565. — doi:10.1016/j.aim.2005.12.004. — arXiv:math/0407074.
• William Y. C. Chen, Toufik Mansour, Sherry H. F. Yan. Matchings avoiding partial patterns // Electronic Journal of Combinatorics. — 2006. — Т. 13, вып. 1.
• Bernstein M., Sloane N. J. A. Some canonical sequences of integers // Linear Algebra and its Applications. — 1995. — Т. 226/228. — С. 57–72. — doi:10.1016/0024-3795(94)00245-9. — arXiv:math/0205301.
• Curtis Coker. A family of eigensequences // Discrete Mathematics. — 2004. — Т. 282, вып. 1-3. — С. 249–250. — doi:10.1016/j.disc.2003.12.008.
• Richard P. Stanley. Hipparchus, Plutarch, Schröder, and Hough // American Mathematical Monthly. — 1997. — Т. 104, вып. 4. — doi:10.2307/2974582.
• Dominique Foata, Doron Zeilberger. A classic proof of a recurrence for a very classical sequence // Journal of Combinatorial Theory. — 1997. — Т. 80, вып. 2. — doi:10.1006/jcta.1997.2814. — arXiv:math/9805015.
• Richard P. Stanley. Enumerative Combinatorics. — Cambridge University Press, 1999.
• Acerbi F. On the shoulders of Hipparchus: A reappraisal of ancient Greek combinatorics // Archive for History of Exact Sciences. — 2003. — Т. 57. — doi:10.1007/s00407-003-0067-0. Архивировано 21 июля 2011 года.
• Ernst Schröder. Vier kombinatorische Probleme // Zeitschrift für Mathematik und Physik. — 1870. — Т. 15.
• Susanne Bobzien. The Combinatorics of Stoic Conjunction: Hipparchus refuted, Chrysippus vindicated // Oxford Studies in Ancient Philosophy. — 2011. — Summer (т. XL).

Ссылки

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