Числа Шрёдера — Гиппарха (Cnvlg Oj~;yjg — Inhhgj]g)

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

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

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

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

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

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

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

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

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

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

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

[править | править код]

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

Последовательность чисел Каталана и последовательность чисел Шрёдера — Гиппарха при рассмотрении как бесконечномерные вектора, являются единственными собственными векторами для первых двух из последовательности естественным образом определённых линейных операторов на последовательностях чисел[6][7]. Более обще, k-ая последовательность в этой последовательности целых последовательностей равна , где числа xn вычисляются как суммы чисел Нараяны, умноженных на степени k. Это можно представить как гипергеометрическую функцию:

Подстановка k = 1 в этой формуле даёт числа Каталана, а подстановка k = 2 в эту формулу даёт числа Шрёдера — Гиппарха[7].

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

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

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

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

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

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

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

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

Примечания

[править | править код]
  1. 1 2 Stanley, 1999, с. Exercise 1.45, vI/51; vII, /176–178, 213.
  2. 1 2 Shapiro, Sulanke, 2000, с. 369–376.
  3. 1 2 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. 1 2 Coker, 2004, с. 249–250.
  8. 1 2 3 Stanley, 1997, с. 344–350.
  9. Foata, Zeilberger, 1997, с. 380–384.
  10. 1 2 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).