Число Шредера – Гиппарха

Число Шредера – Гиппарха

Назван в честь	Эрнст Шредер , Гиппарх , Эжен Шарль Каталан
Год публикации	1870 (Шредер)
Количество известных терминов	бесконечность
Формула	$x_{n}=\sum _{i=1}^{n}{\frac {1}{n}}{n \choose i}{n \choose i-1}k^{i-1}$
Первые сроки	1 , 1 , 3 , 11 , 45 , 197 , 903
ОЭИС Индекс	А001003 Маленькие числа Шредера, Супер каталанский

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

В комбинаторике числа Шредера -Гиппарха образуют целочисленную последовательность , которую можно использовать для подсчета плоских деревьев с заданным набором листьев, способов вставки круглых скобок в последовательность и способов разделения выпуклого многоугольника на меньшие многоугольники путем вставки диагонали. Эти цифры начинаются

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

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

Приложения комбинаторного перечисления

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

Числа Шредера-Гиппарха можно использовать для подсчета нескольких тесно связанных комбинаторных объектов:

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

Как видно из рисунка, между этими объектами существует простая комбинаторная эквивалентность: подразделение многоугольника имеет плоское дерево как форму своего двойственного графа , листья дерева соответствуют символам в скобках, а внутренние узлы дерево, отличное от корня, соответствует группам в скобках. Сама последовательность в скобках может быть записана по периметру многоугольника с ее символами на сторонах многоугольника и скобками на концах выбранных диагоналей. Эта эквивалентность обеспечивает взаимно однозначное доказательство того, что все эти виды объектов учитываются одной целочисленной последовательностью.

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

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

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

Последовательность каталонских чисел и последовательность чисел Шредера – Гиппарха, рассматриваемые как бесконечномерные векторы , являются уникальными собственными векторами для первых двух в последовательности естественно определенных линейных операторов на числовых последовательностях. В более общем смысле, k -я последовательность в этой последовательности целочисленных последовательностей — это ( x ₁ , x ₂ , x ₃ , ...), где числа x _n вычисляются как суммы чисел Нараяны, умноженные на степени k . Это можно выразить в виде гипергеометрической функции :

$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 в эту формулу дает числа Шредера – Гиппарха.

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

Повторение

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

$x_{n}={\frac {1}{n}}\left((6n-9)x_{n-1}-(n-3)x_{n-2}\right).$

Стэнли доказывает этот факт с помощью производящих функций в то время как Фоата и Зейлбергер предоставляют прямое комбинаторное доказательство.

История

Плутарха В диалоге «Застольная беседа» есть строчка:

Хрисипп говорит, что число сложных предложений, которые можно составить только из десяти простых предложений, превышает миллион. (Гиппарх, правда, опроверг это, показав, что в утвердительной части имеется 103 049 сложных высказываний, а в отрицательной — 310 952.)

Это утверждение оставалось необъяснимым до 1994 года, когда Дэвид Хаф, аспирант Университета Джорджа Вашингтона , заметил, что существует 103049 способов вставить круглые скобки в последовательность из десяти элементов. Историк математики Фабио Ачерби ( CNRS ) показал, что аналогичное объяснение можно дать и для другого числа: оно очень близко к среднему десятому и одиннадцатому числам Шредера-Гиппарха, 310954, и учитывает заключения в скобки десяти членов вместе с отрицательная частица.

Проблема подсчета скобок была введена в современную математику Шредером (1870) .

Пересказ Плутархом двух чисел Гиппарха фиксирует разногласия между Гиппархом и более ранним философом-стоиком Хрисиппом , который утверждал, что количество сложных предложений, которые можно составить из 10 простых предложений, превышает миллион. Современный философ Сюзанна Бобзиен ( 2011 ) утверждала, что расчет Хрисиппа был правильным, основываясь на ее анализе стоической логики . Бобзиен реконструирует расчеты Хрисиппа и Гиппарха и говорит, что показ того, как Гиппарх правильно выполнил свою математику, но неправильная стоическая логика, может пролить новый свет на стоические представления о соединениях и утверждениях.

Внешние ссылки

• Вайсштейн, Эрик В. , «Суперкаталонское число» , MathWorld
• Операда «Гиппарх» , Кафе n-Category, 1 апреля 2013 г.