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

Schröder–Hipparchus number
Одиннадцать делений пятиугольника

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

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

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

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

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

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

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

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

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

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

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

Последовательность каталонских чисел и последовательность чисел Шредера – Гиппарха, рассматриваемая как бесконечномерная векторов, являются уникальными собственные векторы для первых двух в последовательности естественно определенных линейных операторов над числовыми последовательностями.[6][7] В более общем плане k-я последовательность в этой последовательности целочисленных последовательностей равна (Икс1, Икс2, Икс3, ...) где числа Иксп рассчитываются как суммы Числа Нараяны умноженный наk. Это можно выразить как гипергеометрическая функция:

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

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

Повторение

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

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

История

Плутарха диалог Застольный разговор содержит строку:

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

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

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

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

Рекомендации

  1. ^ а б Стэнли, Ричард П. (1997, 1999), Перечислительная комбинаторика, Издательство Кембриджского университета. Упражнение 1.45, т. I, стр. 51; т. II, стр. 176–178 и с. 213.
  2. ^ а б Шапиро, Луи В.; Суланке, Роберт А. (2000), "Биекции для чисел Шредера", Математический журнал, 73 (5): 369–376, Дои:10.2307/2690814, МИСТЕР 1805263.
  3. ^ а б Этерингтон, И. М. Х. (1940), «Некоторые проблемы неассоциативных комбинаций (I)», Эдинбургские математические заметки, 32: 1–6, Дои:10.1017 / S0950184300002639.
  4. ^ Holtkamp, ​​Ральф (2006), "О структурах алгебры Хопфа над свободными операдами", Успехи в математике, 207 (2): 544–565, arXiv:математика / 0407074, Дои:10.1016 / j.aim.2005.12.004, МИСТЕР 2271016.
  5. ^ Chen, William Y.C .; Мансур, Туфик; Ян, Шерри Х. Ф. (2006), «Соответствия без частичных шаблонов», Электронный журнал комбинаторики, 13 (1): Research Paper 112, 17 стр. (В электронном виде), МИСТЕР 2274327.
  6. ^ Бернштейн, М .; Слоан, Н. Дж. А. (1995), "Некоторые канонические последовательности целых чисел", Линейная алгебра и ее приложения, 226/228: 57–72, arXiv:математика / 0205301, Дои:10.1016/0024-3795(94)00245-9, МИСТЕР 1344554.
  7. ^ а б Кокер, Кертис (2004), «Семейство собственных последовательностей», Дискретная математика, 282 (1–3): 249–250, Дои:10.1016 / j.disc.2003.12.008, МИСТЕР 2059525.
  8. ^ а б c Стэнли, Ричард П. (1997), «Гиппарх, Плутарх, Шредер и Хаф» (PDF), Американский математический ежемесячный журнал, 104 (4): 344–350, Дои:10.2307/2974582, МИСТЕР 1450667.
  9. ^ Фоата, Доминик; Зейлбергер, Дорон (1997), "Классическое доказательство рекуррентности очень классической последовательности", Журнал комбинаторной теории, Серия А, 80 (2): 380–384, arXiv:математика / 9805015, Дои:10.1006 / jcta.1997.2814, МИСТЕР 1485153.
  10. ^ а б Ачерби, Ф. (2003), «На плечах Гиппарха: переоценка древнегреческой комбинаторики» (PDF), Архив истории точных наук, 57: 465–502, Дои:10.1007 / s00407-003-0067-0, заархивировано из оригинал (PDF) на 2011-07-21.
  11. ^ Шредер, Эрнст (1870), "Vier kombinatorische Probleme", Zeitschrift für Mathematik und Physik, 15: 361–376.
  12. ^ Бобзен, Сюзанна (Лето 2011 г.), «Комбинаторика стоического соединения: Гиппарх опровергнут, Хрисипп подтвержден» (PDF), Оксфордские исследования в античной философии, XL: 157–188.

внешняя ссылка