Числа Шрёдера — Гиппарха (Cnvlg Oj~;yjg — Inhhgj]g)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/27/Pentagon_subdivisions.svg/280px-Pentagon_subdivisions.svg.png)
Числа Шрёдера — Гиппарха образуют последовательность целых чисел[англ.], которую можно использовать для подсчёта числа плоских деревьев с заданным числом листьев, числа способов вставки скобок в последовательность и числа способов разбиения выпуклого многоугольника на меньшие многоугольники путём проведения диагоналей. Эта последовательность начинается с
Эти числа называются также суперкаталановыми числами, малыми числами Шрёдера, или числами Гиппарха (Эжен Шарль Каталан и его числа Каталана, Эрнст Шрёдер и тесно связанные Числа Шрёдера, древнегреческий математик Гиппарх, который по свидетельству Плутарха знал эти числа).
Приложения для комбинаторных перечислений
[править | править код]![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/32/Tree-polygon-paren_equivalence.svg/240px-Tree-polygon-paren_equivalence.svg.png)
Числа Шрёдера — Гиппарха можно использовать для подсчёта некоторых тесно связанных комбинаторных объектов[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 2 Stanley, 1999, с. Exercise 1.45, vI/51; vII, /176–178, 213.
- ↑ 1 2 Shapiro, Sulanke, 2000, с. 369–376.
- ↑ 1 2 Etherington, 1940, с. 1–6.
- ↑ Holtkamp, 2006, с. 544–565.
- ↑ Chen, Mansour, Yan, 2006, с. Research Paper 112, 17 pp.
- ↑ Bernstein, Sloane, 1995, с. 57–72.
- ↑ 1 2 Coker, 2004, с. 249–250.
- ↑ 1 2 3 Stanley, 1997, с. 344–350.
- ↑ Foata, Zeilberger, 1997, с. 380–384.
- ↑ 1 2 Acerbi, 2003, с. 465–502.
- ↑ Schröder, 1870, с. 361–376.
- ↑ Bobzien, 2011.
- ↑ 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
Для улучшения этой статьи желательно:
|