Русская Википедия:Числа Шрёдера — Гиппарха
Числа Шрёдера — Гиппарха образуют Шаблон:Не переведено 5, которую можно использовать для подсчёта числа плоских деревьев с заданным числом листьев, числа способов вставки скобок в последовательность и числа способов разбиения выпуклого многоугольника на меньшие многоугольники путём проведения диагоналей. Эта последовательность начинается с
- 1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ... Шаблон:OEIS.
Эти числа называются также суперкаталановыми числами, малыми числами Шрёдера, или числами Гиппарха (Эжен Шарль Каталан и его числа Каталана, Эрнст Шрёдер и тесно связанные Числа Шрёдера, древнегреческий математик Гиппарх, который по свидетельству Плутарха знал эти числа).
Приложения для комбинаторных перечислений
Числа Шрёдера — Гиппарха можно использовать для подсчёта некоторых тесно связанных комбинаторных объектовШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn:
- n-ое число в последовательности подсчитывает число различных способов разбиения многоугольника с n + 1 сторонами на меньшие многоугольники путём добавления диагоналей в исходный многоугольник.
- n-ое число подсчитывает число различных плоских деревьев с n листьями и с внутренними вершинами, имеющими два и более детей.
- n-ое число подсчитывает число различных способов вставки скобок в последовательность n символов, где каждая пара скобок окружает два и более символов или скобочных групп, но полная последовательность в скобки не заключается.
- n-ое число подсчитывает число граней всех размерностей Шаблон:Не переведено 5 <math>K_{n+1}</math> размерности <math>n - 1</math>, включая сам ассоциэдр как грань, но не включая пустое множество. Например, двумерный ассоциэдр K4 является пятиугольником. Он имеет пять вершин, пять граней и один полный ассоциэдр, в общей сложности 11 граней.
Как показывает рисунок, имеется простая комбинаторная эквивалентность между этими объектами — разбиение многоугольника имеет плоское дерево как двойственный граф, листья этого дерева соответствуют символам в последовательности при расстановке скобок, а внутренние вершины дерева, отличные от корня, соответствуют скобочным группам. Последовательность с расставленными скобками может быть записана вокруг периметра многоугольника с символами на сторонах и скобками на концах выбранных диагоналей. Эта эквивалентность даёт биективное доказательство, что все эти виды объектов подсчитываются одной целочисленной последовательностьюШаблон:Sfn.
Те же числа также подсчитывают число двойных перестановок (последовательностей чисел от 1 до n, каждое число появляется дважды, при этом каждое число первый раз появляется в отсортированном порядке), которые избегают Шаблон:Не переведено 5 12312 и 121323Шаблон:Sfn.
Связанные последовательности
Тесно связанные большие числа Шрёдера равны удвоенным числам Шрёдера — Гиппарха и могут также быть использованы для подсчёта некоторых типов комбинаторных объектов, включая некоторые виды путей в решётке, разбиение прямоугольника на более мелкие прямоугольники путём рекурсивного деления, и расстановки скобок, когда разрешается также пара скобок, включающих всю последовательность элементов. Числа Каталана также подсчитывают тесно связанные множества объектов, включая подразбиения многоугольника на треугольники, плоские деревья, в которых все внутренние вершины имеют в точности две дочерние вершины, и расстановку скобок, при которой каждая пара скобок окружает в точности два символа или группы скобокШаблон:Sfn.
Последовательность чисел Каталана и последовательность чисел Шрёдера — Гиппарха при рассмотрении как бесконечномерные вектора, являются единственными собственными векторами для первых двух из последовательности естественным образом определённых линейных операторов на последовательностях чиселШаблон:SfnШаблон:Sfn. Более обще, k-ая последовательность в этой последовательности целых последовательностей равна <math>(x_1, x_2, x_3,\dots)</math>, где числа xn вычисляются как суммы чисел Нараяны, умноженных на степени k. Это можно представить как гипергеометрическую функцию:
- <math>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}={}_2F_1(1-n,-n;2;k).</math>
Подстановка k = 1 в этой формуле даёт числа Каталана, а подстановка k = 2 в эту формулу даёт числа Шрёдера — ГиппархаШаблон:Sfn.
Если подсчёт граней ассоциэдра задаётся числами Шрёдера — Гиппарха, то число вершин ассоциэдра задаётся числами Каталана. Соответствующие числа для перестановочного многогранника являются соответственно Шаблон:Не переведено 5 и факториалами.
Рекурсия
Как и в формуле суммирования выше, числа Шрёдера — Гиппарха могут быть определены по рекуррентной формуле:
- <math>S(n)=\frac{1}{n}\left((6n-9)S(n-1)-(n-3)S(n-2)\right).</math>
Стенли доказал этот факт с помощью производящих функции последовательностиШаблон:Sfn, а Фоата и Цайльбергер дали прямое комбинаторное доказательствоШаблон:Sfn.
История
Диалог Плутарха (из книги «Застольные беседы») содержит строку:
- Хрисипп говорит, что число составных высказываний, которые можно составить всего из десяти простых высказываний, достигает миллиона. (Гиппарх, несомненно, опроверг это, показав, что утвердительных сложных утверждений имеется 103.049, а отрицательных 310.952)Шаблон:Sfn.
Это утверждение оставалось необъяснённым до 1994 года, когда Дэвид Хаф, студент магистратуры Университета Джорджа Вашингтона, заметил, что имеется 103049 способов вставить скобки в строку из десяти элементовШаблон:SfnШаблон:SfnШаблон:Sfn. Аналогичное объяснение может быть дано для другого числа — оно очень близко к среднему десяти чисел Шрёдера — Гиппарха 310954, и перечисляет все расстановки скобок для десяти элементов вместе с отрицательной частицейШаблон:Sfn.
Задача подсчёта расстановок скобок была представлена современной математики ШрёдеромШаблон:Sfn.
Вычисление Плутархом двух чисел Гиппарха обнаруживает разногласие между Гиппархом и более ранним греческим философом Хрисиппом, который утверждал, что число сложных утверждений, которые можно получить из десяти простых утверждений, достигает миллиона. Представитель современной философии Сюзанна БобзинШаблон:Sfn возражала, что вычисление Хрисиппа было верно, основываясь на анализе стоической логики. Сюзанна Бобзин реконструировала вычисления как Хрисиппа, так и Гиппарха, и заявила, что метод, которым Гиппарх получил свои математически верные результаты при его неверной стоической логике, проливает новый свет на стоические понятия конъюнкции и утвержденияШаблон:Sfn.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
Ссылки
- Шаблон:Mathworld
- The Hipparchus Operad, The n-Category Café, April 1, 2013
Шаблон:Классы натуральных чисел Шаблон:Rq
