что эквивалентно приведенному выше выражению, поскольку . Это выражение показывает, что C n — целое число , что не сразу очевидно из первой приведенной формулы. Это выражение составляет основу доказательства правильности формулы.
Другое альтернативное выражение:
что можно непосредственно интерпретировать в терминах леммы о цикле ; см. ниже.
Более точный асимптотический анализ показывает, что числа Каталана аппроксимируются приближением четвертого порядка .
.
Нечетными каталонскими числами C n являются только те, для которых n = 2 k − 1 ; все остальные четные. Единственными простыми каталонскими числами являются C 2 = 2 и C 3 = 5 . [1]
Каталанские числа имеют целочисленные представления [2] [3]
что сразу дает .
Это имеет простую вероятностную интерпретацию. Рассмотрим случайное блуждание по целочисленной строке, начиная с 0. Пусть -1 будет состоянием «ловушки», так что если ходок достигнет -1, он останется там. Ходок может прийти в состояние ловушки в моменты времени 1, 3, 5, 7..., и число способов, которыми он может прийти в состояние ловушки за раз, равно . Поскольку одномерное случайное блуждание является повторяющимся, вероятность того, что ходок в конечном итоге достигнет -1, равна .
Приложения в комбинаторике
В комбинаторике существует множество задач о счете , решение которых дают числа Каталана. Книга комбинаториста Ричарда П. Стэнли «Перечислительная комбинаторика: Том 2 » содержит набор упражнений, которые описывают 66 различных интерпретаций каталонских чисел. Ниже приведены несколько примеров с иллюстрациями случаев C 3 = 5 и C 4 = 14 .
Решетка из 14 слов Дейка длиной 8 – ( и ) , интерпретируемых как вверх и вниз.
C n — количество слов Дика [4] длины 2 n . Слово Дайка — это строка , состоящая из n символов X и n Y, такая, что ни в одном начальном сегменте строки Y не превышает числа X. Например, ниже приведены слова Дика длиной до 6:
XY
XXYY XYXY
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
Переинтерпретируя символ X как открывающую скобку и Y как закрывающую скобку, C n подсчитывает количество выражений, содержащих n пар скобок, которые правильно сопоставлены:
((())) (()()) (())() ()(()) ()()()
C n — это количество различных способов, которыми n + 1 фактор может быть полностью заключен в круглые скобки (или количество способов связать n применений бинарного оператора , как в задаче умножения цепочки матриц ). Например, для n = 3 у нас есть следующие пять различных заключений четырех факторов в круглые скобки:
((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
Последовательные применения бинарного оператора можно представить в виде полного двоичного дерева , пометив каждый лист a,b,c,d . Отсюда следует, что C n — это количество полных бинарных деревьев с n + 1 листьями или, что то же самое, с n внутренними узлами:
Ассоциэдр 4- го порядка с C 4 =14 полными двоичными деревьями с 5 листьями
C n — количество монотонных путей решетки по краям сетки с n × n квадратными ячейками, не выходящим за пределы диагонали. Монотонный путь — это путь, который начинается в левом нижнем углу, заканчивается в правом верхнем углу и полностью состоит из ребер, направленных вправо или вверх. Подсчет таких путей эквивалентен подсчету слов Дика: X означает «движение вправо», а Y означает «движение вверх».
На следующих диаграммах показан случай n = 4:
Это можно представить, перечислив каталонские элементы по высоте столбца: [6]
Темный треугольник — это корневой узел, светлые треугольники соответствуют внутренним узлам бинарных деревьев, а зеленые полосы — листьям.
Выпуклый многоугольник с n + 2 сторонами можно разрезать на треугольники , соединяя вершины непересекающимися отрезками линий (разновидность триангуляции многоугольника ). Число образованных треугольников равно n , а количество различных способов, которыми это можно сделать, равно C n . Следующие шестиугольники иллюстрируют случай n = 4:
C n — количество сортируемых по стеку перестановок {1, ..., n }. Перестановка w называется сортируемой стеком, если S ( w ) = (1,..., n ), где S ( w ) определяется рекурсивно следующим образом: напишите w = unv , где n — наибольший элемент в w и u , а v — более короткие последовательности, и установите S ( w ) = S ( u ) S ( v ) n , где S — тождество для одноэлементных последовательностей.
C n — количество перестановок {1, ..., n }, которые избегают шаблона перестановки 123 (или, альтернативно, любого другого шаблона длины 3); то есть количество перестановок без трехчленной возрастающей подпоследовательности. Для n = 3 это 132, 213, 231, 312 и 321. Для n = 4 это 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312. и 4321.
C n — количество непересекающихся разбиений множества {1, ..., n }. Тем более , C n никогда не превышает n -го числа Белла . C n — это также количество непересекающихся разделов набора {1, ..., 2 n }, в которых каждый блок имеет размер 2.
C n — количество способов замостить ступеньку высоты n n прямоугольниками . Разрезание антидиагонали и просмотр только краев дает полные бинарные деревья. Следующий рисунок иллюстрирует случай n = 4:
C n — это количество способов сформировать «горный хребет» с n движениями вверх и n движениями вниз, которые все остаются выше горизонтальной линии. Интерпретация горного хребта заключается в том, что горы никогда не уйдут за горизонт.
C n — количество стандартных таблиц Юнга , диаграмма которых представляет собой прямоугольник размером 2× n . Другими словами, это количество способов, которыми числа 1, 2, ..., 2 n можно расположить в прямоугольнике размером 2 на n так, чтобы каждая строка и каждый столбец увеличивались. Таким образом, формула может быть выведена как частный случай формулы длины крючка .
123 124 125 134 135456 356 346 256 246
— это количество последовательностей длины n , которые начинаются с , и могут увеличиваться либо на , либо уменьшаться на любое число (по крайней мере до ). Ибо это . По пути Дика начните счетчик с 0 . X увеличивает счетчик на 1 , а Y уменьшает его на 1 . Запишите значения только в точках X. По сравнению с аналогичным представлением чисел Белла отсутствует только .
Доказательство формулы
Есть несколько способов объяснить, почему формула
решает комбинаторные задачи, перечисленные выше. Первое доказательство ниже использует производящую функцию . Остальные доказательства являются примерами биективных доказательств ; они включают в себя буквально подсчет совокупности каких-то объектов, чтобы прийти к правильной формуле.
Например, каждое слово Дика w длины ≥ 2 можно единственным образом записать в виде
ш = Х ш 1 Y ш 2
с (возможно, пустыми) словами Дика w 1 и w 2 .
Производящая функция каталонских чисел определяется формулой
Приведенное выше рекуррентное соотношение затем можно резюмировать в виде производящей функции соотношением
другими словами, это уравнение следует из рекуррентного соотношения путем разложения обеих частей в степенные ряды . С одной стороны, рекуррентное соотношение однозначно определяет числа Каталана; с другой стороны, интерпретируя xc 2 − c + 1 = 0 как квадратное уравнение для c и используя квадратичную формулу , соотношение производящей функции можно алгебраически решить, чтобы получить две возможности решения
или .
Из двух возможностей следует выбрать вторую, поскольку только вторая дает
.
Член квадратного корня можно разложить в степенной ряд, используя биномиальный ряд.
Второе доказательство
Рисунок 1. Недопустимая часть пути (красный пунктир) перевернута (сплошной красный). Плохие пути (после переворота) достигают ( n – 1, n + 1) вместо ( n , n ).
Мы подсчитываем количество путей, которые начинаются и заканчиваются на диагонали сетки n × n . Все такие пути имеют n ступеней вправо и n ступеней вверх. Поскольку мы можем выбирать, какой из 2n шагов является верхним или правым, в целом существует монотонные пути этого типа. Плохой путь пересекает главную диагональ и касается следующей, более высокой диагонали (красный на рисунке) .
Часть пути после более высокой диагонали затем переворачивается вокруг этой диагонали, как показано красной пунктирной линией. Это поменяет местами все правильные шаги на шаги вверх и наоборот. На участке пути, который не отражен, на один шаг вверх больше, чем на шаги вправо, поэтому оставшийся участок плохого пути имеет на один шаг вправо больше, чем шаги вверх. Когда эта часть пути будет отражена, она будет иметь на один шаг вверх больше, чем шаги вправо.
Поскольку шагов по-прежнему 2n , теперь есть n + 1 шагов вверх и n − 1 шагов вправо. Таким образом, вместо того, чтобы достичь ( n , n ), все плохие пути после отражения заканчиваются в ( n − 1, n + 1). Поскольку каждый монотонный путь в сетке ( n − 1) × ( n + 1) пересекает более высокую диагональ, и поскольку процесс отражения обратим, отражение, следовательно, представляет собой биекцию между плохими путями в исходной сетке и монотонными путями в новой. сетка.
Таким образом, количество плохих путей равно:
а количество каталонских путей (т.е. хороших путей) получается удалением количества плохих путей из общего количества монотонных путей исходной сетки,
С точки зрения слов Дика, мы начинаем с (не-Дейка) последовательности из n X и n Y и меняем местами все X и Y после первого Y, который нарушает условие Дика. После этого Y заметьте, что Y ровно на один больше, чем X.
Третье доказательство
Это биективное доказательство дает естественное объяснение слагаемому n + 1, появляющемуся в знаменателе формулы для C n . Обобщенную версию этого доказательства можно найти в статье Рукавицкой Йозефа (2011). [8]
Рисунок 2. Путь с превышением 5.
Учитывая монотонный путь, превышение пути определяется как количество вертикальных ребер над диагональю. Например, на рисунке 2 ребра над диагональю отмечены красным, поэтому превышение этого пути равно 5.
Учитывая монотонный путь, превышение которого не равно нулю, мы применяем следующий алгоритм для построения нового пути, превышение которого на 1 меньше того, с которого мы начали.
Начиная с левого нижнего угла, следуйте по пути, пока он не пройдет выше диагонали.
Продолжайте идти по пути, пока он снова не коснется диагонали. Обозначим через X первое достигнутое такое ребро.
Поменяйте местами часть пути, происходящую до X, на часть, происходящую после X.
На рисунке 3 черная точка указывает точку, где путь впервые пересекает диагональ. Черный край — это X , и мы помещаем последнюю точку решетки красной части в верхний правый угол, а первую точку решетки зеленой части в нижний левый угол и размещаем X соответственно, чтобы создать новый путь. , показанный на второй диаграмме.
Рисунок 3. Зеленая и красная части меняются местами.
Превышение снизилось с 3 до 2 . Фактически, алгоритм заставляет превышение уменьшаться на 1 для любого пути, который мы ему подаем, потому что первый вертикальный шаг, начинающийся по диагонали (в точке, отмеченной черной точкой), является единственным вертикальным ребром, который не находится над диагональ ниже нее, когда мы применяем алгоритм - все остальные вертикальные ребра остаются на той же стороне диагонали.
Рисунок 4. Все монотонные пути в сетке 3×3, иллюстрирующие алгоритм уменьшения превышения.
Можно видеть, что этот процесс обратим : для любого пути P , превышение которого меньше n , существует ровно один путь, который дает P , когда к нему применяется алгоритм. Действительно, (черное) ребро X , которое изначально было первым горизонтальным шагом, заканчивающимся на диагонали, стало последним горизонтальным шагом, начинающимся на диагонали. Альтернативно, измените исходный алгоритм, чтобы найти первое ребро, проходящее ниже диагонали.
Это означает, что количество путей превышения n равно количеству путей превышения n - 1, которое равно количеству путей превышения n - 2, и так далее, вплоть до нуля. Другими словами, мы разбили набор всех монотонных путей на n + 1 класс одинакового размера, что соответствует возможным превышениям между 0 и n . Поскольку существуют монотонные пути, получаем искомую формулу
Рисунок 4 иллюстрирует ситуацию для n = 3. Каждый из 20 возможных монотонных путей появляется где-то в таблице. В первом столбце показаны все пути превышения три, которые полностью лежат выше диагонали. Столбцы справа показывают результат последовательных применений алгоритма с уменьшением превышения на одну единицу за раз. Строок пять, то есть C 3 = 5, а в последнем столбце отображаются все пути не выше диагонали.
Используя слова Дайка, начните с последовательности от . Позвольте быть первым X , который приводит начальную подпоследовательность к равенству, и настройте последовательность как . Новая последовательность .
Четвертое доказательство
Это доказательство использует определение триангуляции каталонских чисел, чтобы установить связь между C n и C n +1 .
Дан многоугольник P с n + 2 сторонами и триангуляцией. Отметьте одну из его сторон как основание, а также сориентируйте одно из его 2 n + 1 ребер. Таких отмеченных триангуляций для данной базы имеется (4 n + 2) C n .
Дан многоугольник Q с n + 3 сторонами и (разной) триангуляцией. Снова отметьте одну из его сторон как основу. Отметьте одну из сторон, кроме базовой стороны (а не внутреннего края треугольника). Таких отмеченных триангуляций для данной базы существует ( n + 2) C n + 1 .
Между этими двумя отмеченными триангуляциями существует простая биекция: мы можем либо свернуть треугольник в Q , сторона которого отмечена (двумя способами, и вычесть те два, которые не могут свернуть основание), либо, наоборот, расширить ориентированное ребро в P. к треугольнику и отметьте его новую сторону.
Таким образом
.
Писать
Потому что
у нас есть
Применение рекурсии с дает результат.
Пятое доказательство
Это доказательство основано на интерпретации каталонских чисел словами Дейка , а также на количестве способов правильно сопоставить n пар скобок. Мы обозначаем правильную строку (возможно, пустую) через c , а обратную ей — через c' . Поскольку любой c можно однозначно разложить на , суммирование по возможным длинам сразу дает рекурсивное определение
.
Пусть b — сбалансированная строка длины 2n , т.е. b содержит равное количество и , поэтому . Сбалансированную строку также можно однозначно разложить на или , поэтому
Любая неверная (не каталонская) сбалансированная строка начинается с , а оставшаяся строка имеет на единицу больше , поэтому
Последовательность X и Y назовем доминирующей , если при чтении слева направо число X всегда строго больше числа Y. Лемма о цикле [11] утверждает, что любая последовательность X и Y, где , имеет в точности доминирующие круговые сдвиги . Чтобы убедиться в этом, расположите заданную последовательность X и Y по кругу. Повторное удаление пар XY оставляет ровно X. Каждый из этих крестиков был началом доминирующего кругового сдвига, прежде чем что-либо было удалено. Например, рассмотрим . Эта последовательность является доминирующей, но ни один из ее круговых сдвигов , , и не является.
Строка является словом Дайка, состоящим из X и Y, тогда и только тогда, когда добавление X к слову Дайка дает доминирующую последовательность с X и Y, поэтому мы можем посчитать первое, вместо этого посчитав второе. В частности, при , имеется ровно один доминирующий круговой сдвиг. Существуют последовательности, в которых ровно X и Y. Для каждого из них доминирует только один из круговых сдвигов. Следовательно, существуют различные доминирующие последовательности X и Y, каждая из которых соответствует ровно одному слову Дика.
Матрица Ханкеля
Матрица Ханкеля размера n × n, элементом ( i , j ) которого является каталонское число C i + j −2, имеет определитель 1, независимо от значения n . Например, для n = 4 имеем
Более того, если индексация «сдвинута» так, что запись ( i , j ) заполнена каталонским числом C i + j −1 , тогда определитель по-прежнему равен 1, независимо от значения n . Например, для n = 4 имеем
В совокупности эти два условия однозначно определяют каталонские числа.
Еще одна особенность, уникальная для матрицы Каталана – Ханкеля, заключается в том, что подматрица размера n × n , начинающаяся с 2 , имеет определитель n + 1.
и так далее.
История
Каталонские числа в книге Минганту «Быстрый метод получения точного отношения деления круга», том III
Каталонская последовательность была описана в XVIII веке Леонардом Эйлером , которого интересовало количество различных способов деления многоугольника на треугольники. Последовательность названа в честь Эжена Шарля Каталана , который обнаружил связь с выражениями в скобках во время исследования загадки Ханойских башен . Трюк подсчета отражений (второе доказательство) для слов Дейка был найден Дезире Андре в 1887 году.
Название «каталонские числа» произошло от Джона Риордана . [12]
В 1988 году выяснилось, что каталонская числовая последовательность использовалась в Китае монгольским математиком Минганту к 1730 году. [13] [14] Именно тогда он начал писать свою книгу «Гэ Юань Ми Лу Цзе Фа» («Быстрый метод»). для получения точного отношения деления круга] , который был завершен его учеником Чэнь Цзисинь в 1774 году, но опубликован шестьдесят лет спустя. Питер Дж. Ларкомб (1999) обрисовал некоторые особенности творчества Минганту, в том числе стимул Пьера Жарту, который привез в Китай три бесконечные серии в начале 1700-х годов.
Например, Минг использовал каталонскую последовательность для выражения разложения ряда и через .
Обобщения
Каталонские числа можно интерпретировать как частный случай теоремы Бертрана о голосовании . В частности, это количество способов, которыми кандидат A с n+1 голосами может опередить кандидата B с n голосами.
Двухпараметрическая последовательность неотрицательных целых чисел
является обобщением каталонских чисел. По словам Иры Гессель , это так называемые суперкаталонские числа . Их не следует путать с числами Шредера – Гиппарха , которые иногда также называют суперкаталанскими числами.
Для это всего лишь в два раза больше обычных каталонских чисел, а для числа имеют простое комбинаторное описание. Однако другие комбинаторные описания известны только [15]
для и , [16]
и найти общую комбинаторную интерпретацию остается открытой проблемой.
Сергей Фомин и Натан Ридинг дали обобщенное число Каталана, связанное с любой конечной кристаллографической группой Кокстера , а именно количество полностью коммутативных элементов группы; с точки зрения связанной корневой системы это количество антицепей (или идеалов порядка) в частично упорядоченном множестве положительных корней. Классическое каталонское число соответствует корневой системе типа . Классическое рекуррентное соотношение обобщает: число Каталана диаграммы Кокстера равно сумме чисел Каталана всех ее максимальных собственных поддиаграмм. [17]
^ Чхве, Хаёнг; Да, Ён-Нан; Ю, Сонгук (2020), «Каталонские числовые последовательности и последовательности моментов Хаусдорфа», Discrete Mathematics , 343 (5): 111808, 11, arXiv : 1809.07523 , doi : 10.1016/j.disc.2019.111808, MR 4052255, S2CID 21 4165563, Пример 3.1
^ Фэн, Ци; Бай-Ни, Го (2017), «Интегральные представления каталонских чисел и их приложения», Mathematics , 5 (3): 40, doi : 10.3390/math5030040,Теорема 1
^ Пути Дика
^ Стэнли, стр. 221, пример (д)
^ Черпиншек, Матей; Мерник, Лука (2009). «Эффективное представление для решения проблем, связанных с каталонскими числами» (PDF) . Международный журнал чистой и прикладной математики . 56 (4): 589–604.
^ А. де Сегнер, Enumeratio modorum, quibus figurae planaerectilineae per диагонали dividuntur в треугольнике. Novi commentarii academiae scientiarum Petropolitanae 7 (1758/59) 203–209.
^ Рукавицка Йозеф (2011), Об обобщенных путях Дика, Электронный журнал комбинаторики онлайн
^ Дворецкий, Арье; Моцкин, Теодор (1947), «Проблема расположения», Duke Mathematical Journal , 14 (2): 305–313, doi : 10.1215/s0012-7094-47-01423-3
^ Дершовиц, Нахум; Закс, Шмуэль (январь 1990 г.). «Лемма о цикле и некоторые приложения» (PDF) . Европейский журнал комбинаторики . 11 (1): 35–40. дои : 10.1016/S0195-6698(13)80053-4.
^ Стэнли, Ричард П. (2021). «Исчислительная и алгебраическая комбинаторика в 1960-х и 1970-х годах». arXiv : 2105.07884 [math.HO].
^ Ларкомб, Питер Дж. «Китайское открытие каталонских чисел в XVIII веке» (PDF) .
^ «Минг Анту, первый изобретатель каталонских чисел в мире» . Архивировано из оригинала 31 января 2020 г. Проверено 24 июня 2014 г.
^ Чен, Синь; Ван, Джейн (2012). «Суперкаталонские числа S(m, m + s) для s ≤ 4». arXiv : 1208.4196 [math.CO].
^ Георгичук, Ирина; Ореловиц, Гидон (2020). «Суперкаталанские числа третьего и четвертого рода». arXiv : 2008.00133 [math.CO].
^ Сергей Фомин и Натан Ридинг, «Корневые системы и обобщенные ассоциэдры», Геометрическая комбинаторика, IAS/Park City Math. Сер. 13 , Американское математическое общество , Провиденс, Род-Айленд, 2007, стр. 63–131. arXiv : math/0505518
Стэнли, Ричард П. (2015), Каталонские числа . Издательство Кембриджского университета, ISBN 978-1-107-42774-7 .
Конвей и Гай (1996) Книга чисел . Нью-Йорк: Коперник, стр. 96–106.
Гарднер, Мартин (1988), Путешествие во времени и другие математические недоумения, Нью-Йорк: WH Freeman and Company, стр. 253–266 (гл. 20), Bibcode : 1988ttom.book.....G, ISBN 0-7167-1924-Х
Коши, Томас (2008), каталонские числа с приложениями, Oxford University Press, ISBN 978-0-19-533454-8
Коши, Томас и Чжэньгуан Гао (2011) «Некоторые свойства делимости каталонских чисел», Mathematical Gazette 95:96–102.
Ларкомб, П.Дж. (1999). «Китайское открытие каталонских чисел в XVIII веке» (PDF) . Математический спектр . 32 : 5–7.