Фусс – каталонский номер

В комбинаторной математике и статистике числа Фусса – Каталана представляют собой числа вида

$A_{m}(p,r)\equiv {\frac {r}{mp+r}}{\binom {mp+r}{m}}={\frac {r}{m!}}\prod _{i=1}^{m-1}(mp+r-i)=r{\frac {\Gamma (mp+r)}{\Gamma (1+m)\Gamma (m(p-1)+r+1)}}.$

Они названы в честь Н. И. Фусса и Эжена Шарля Каталана .

В некоторых публикациях это уравнение иногда называют двухпараметрическими числами Фусса – Каталана или числами Рени . Отсюда следует, что однопараметрические числа Фусса-Каталана имеют место, когда $\,r=1\,$ и $\,p=2\,$.

Использование

Fuss-Catalan представляет собой количество законных перестановок или разрешенных способов расположения ряда статей, которые каким-то образом ограничены. Это означает, что они связаны с биномиальным коэффициентом . Ключевое различие между Фусс-Каталанским и Биномиальным коэффициентом заключается в том, что внутри Биномиального коэффициента нет «незаконных» перестановок расположения, но они есть в Фусс-Каталанском. Пример законных и незаконных перестановок можно лучше продемонстрировать на конкретной проблеме, такой как сбалансированные скобки (см. Язык Дика ).

Общая проблема состоит в том, чтобы подсчитать количество сбалансированных скобок (или допустимых перестановок), которые образует строка из m открытых и m закрытых скобок (всего 2m скобок). По законодательству действуют следующие правила:

• Для последовательности в целом количество открытых скобок должно равняться количеству закрытых скобок.
• При работе по последовательности количество открытых скобок должно быть больше количества закрытых скобок.

В качестве числового примера, сколько комбинаций можно правильно составить из 3 пар скобок? Из биномиальной интерпретации есть ${\tbinom {2m}{m}}$ или численно ${\tbinom {6}{3}}$ = 20 способов расстановки 3 открытых и 3 закрытых скобок. комбинаций меньше законных Однако при применении всех вышеперечисленных ограничений . Если оценить их вручную, то получится 5 допустимых комбинаций, а именно: ()()(); (())(); ()(()); (()()); ((())). Это соответствует формуле Фусса-Каталана, когда p=2, r=1, что является каталонского числа . формулой ${\tfrac {1}{2m+1}}{\tbinom {2m}{m}}$ или ${\tfrac {1}{4}}{\tbinom {6}{3}}$=5. Путем простого вычитания есть ${\tfrac {m}{m+1}}{\tbinom {2m}{m}}$ или ${\tfrac {3}{4}}{\tbinom {6}{3}}$ =15 незаконных комбинаций. Чтобы еще больше проиллюстрировать тонкость проблемы, если бы кто-то упорствовал в решении проблемы, используя только биномиальную формулу, было бы понятно, что два правила подразумевают, что последовательность должна начинаться с открытой скобки и заканчиваться закрытой скобкой. Это подразумевает, что существуют ${\tbinom {2m-2}{m-1}}$ или ${\tbinom {4}{2}}$=6 комбинаций. Это несовместимо с приведенным выше ответом 5, а недостающая комбинация: ())((), что является незаконным и завершает биномиальную интерпретацию.

Хотя приведенное выше является конкретным примером каталонских чисел, аналогичные проблемы можно оценить с помощью формулы Фусса-Каталана:

• Компьютерный стек : способы организации и завершения компьютерного стека инструкций, каждый раз, когда обрабатывается инструкция шага 1, и p новых инструкций поступают случайным образом. Если в начале последовательности осталось r инструкций.
• Ставки : способы потерять все деньги при ставке. У игрока есть общий банк ставок, который позволяет ему делать r ставок, и он играет в азартную игру, в которой выплачивается p раз больше ставки.
• Попытки : расчет количества попыток порядка m на n узлах.

Особые случаи

Ниже перечислено несколько формул, а также несколько примечательных особых случаев.

Общая форма	Особый случай
$A_{0}(p,r)=1$	$A_{0}(p,p)=A_{1}(p,1)=1$
$A_{1}(p,r)=r$	$A_{1}(p,p)=A_{2}(p,1)=p$
$A_{2}(p,r)=r(2p+r-1)/2$	$A_{2}(p,p)=A_{3}(p,1)=p(3p-1)/2$
$A_{3}(p,r)=r(3p+r-1)(3p+r-2)/6$	$A_{3}(p,p)=A_{4}(p,1)=p(4p-1)(4p-2)/6$
$A_{4}(p,r)=r(4p+r-1)(4p+r-2)(4p+r-3)/24$	$A_{4}(p,p)=A_{5}(p,1)=p(5p-1)(5p-2)(5p-3)/24$

Если $p=0$, мы восстанавливаем биномиальные коэффициенты $A_{m}(0,r){=}{\binom {r}{m}}$

$A_{m}(0,1)=1,1$;

$A_{m}(0,2)=1,2,1$;

$A_{m}(0,3)=1,3,3,1$;

$A_{m}(0,4)=1,4,6,4,1$.

Если $p=1$, появляется Треугольник Паскаля , читаем по диагоналям:

$A_{m}(1,1)=1,1,1,1,1,1,1,1,1,1,\ldots$;

$A_{m}(1,2)=1,2,3,4,5,6,7,8,9,10,\ldots$;

$A_{m}(1,3)=1,3,6,10,15,21,28,35,45,55,\ldots$;

$A_{m}(1,4)=1,4,10,20,35,56,84,120,165,220,\ldots$;

$A_{m}(1,5)=1,5,15,35,70,126,210,330,495,715,\ldots$;

$A_{m}(1,6)=1,6,21,56,126,252,462,792,1287,2002,\ldots$.

Примеры

Для субиндекса $m\geq 0$ цифры:

Примеры с $p=2$:

$A_{m}(2,1)=1,1,2,5,14,42,132,429,1430,4862,\ldots$ OEIS : A000108 , известный как каталонские номера.

$A_{m}(2,2)=1,2,5,14,42,132,429,1430,4862,16796,\ldots =A_{m+1}(2,1)$

$A_{m}(2,3)=1,3,9,28,90,297,1001,3432,11934,41990,\ldots$ ОЭИС : A000245

$A_{m}(2,4)=1,4,14,48,165,572,2002,7072,25194,90440,\ldots$ ОЭИС : A002057

Примеры с $p=3$:

$A_{m}(3,1)=1,1,3,12,55,273,1428,7752,43263,246675,\ldots$ ОЭИС : A001764

$A_{m}(3,2)=1,2,7,30,143,728,3876,21318,120175,690690,\ldots$ ОЭИС : A006013

$A_{m}(3,3)=1,3,12,55,273,1428,7752,43263,246675,1430715,\ldots =A_{m+1}(3,1)$

$A_{m}(3,4)=1,4,18,88,455,2448,13566,76912,444015,2601300,\ldots$ ОЭИС : A006629

Примеры с $p=4$:

$A_{m}(4,1)=1,1,4,22,140,969,7084,53820,420732,3362260,\ldots$ ОЭИС : A002293

$A_{m}(4,2)=1,2,9,52,340,2394,17710,135720,1068012,8579560,\ldots$ ОЭИС : A069271

$A_{m}(4,3)=1,3,15,91,612,4389,32890,254475,2017356,16301164,\ldots$ ОЭИС : A006632

$A_{m}(4,4)=1,4,22,140,969,7084,53820,420732,3362260,27343888,\ldots =A_{m+1}(4,1)$

Алгебра

Повторение

$A_{m}(p,r)=A_{m}(p,r-1)+A_{m-1}(p,p+r-1)$ уравнение (1)

Это означает, в частности, что из

$A_{m}(p,0)=0$ уравнение (2)

и

$A_{0}(p,r)=1$ уравнение (3)

можно сгенерировать все остальные числа Фусса–Каталана, если p — целое число .

Риордан (см. ссылки) получает повторение типа свертки:

$A_{m}(p,s+r)=\sum _{k=0}^{m}A_{k}(p,r)A_{m-k}(p,s)$ уравнение(4)

Генерирующая функция

Перефразируя плотности распределений Ренея В статье пусть обычная производящая функция по индексу m определяется следующим образом:

$B_{p,r}(z):=\sum _{m=0}^{\infty }A_{m}(p,r)z^{m}$ уравнение (5) .

Глядя на уравнения (1) и (2), при r =1 следует, что

$A_{m}(p,p)=A_{m+1}(p,1)$ уравнение (6) .

Также обратите внимание, что этот результат может быть получен путем аналогичных замен в других представлениях формул, таких как представление отношения гаммы в верхней части этой статьи. Используя (6) и подставив в (5), эквивалентное представление, выраженное в виде производящей функции, можно сформулировать как

$B_{p,1}(z)=1+zB_{p,p}(z)$.

Наконец, расширив этот результат с помощью эквивалентности Ламберта

$B_{p,1}(z)^{r}=B_{p,r}(z)$.

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

$B_{p,r}(z)=[1+zB_{p,r}(z)^{p/r}]^{r}$.

Представление рекурсии

Рекурсивные формы этого следующие: Наиболее очевидная форма:

$A_{m}(p,r)={\frac {m-1}{m}}{\frac {\binom {mp+r-1}{m-1}}{\binom {(m-1)p+r-1}{m-2}}}A_{m-1}(p,r)$

Кроме того, менее очевидная форма:

$A_{m}(p,r)={\frac {(m-1)p+r}{m}}{\frac {\binom {mp+r-1}{p-1}}{\binom {m(p-1)+r}{p-1}}}A_{m-1}(p,r)$

Альтернативные представления

В некоторых задачах проще использовать различные конфигурации или варианты формул. Ниже приведены два примера использования только биномиальной функции:

$A_{m}(p,r)\equiv {\frac {r}{mp+r}}{\binom {mp+r}{m}}={\frac {r}{m(p-1)+r}}{\binom {mp+r-1}{m}}={\frac {r}{m}}{\binom {mp+r-1}{m-1}}$

Эти варианты также можно преобразовать в произведение, гамма-представление или факториал.

См. также

• Комбинаторика
• Статистика
• Биномиальный коэффициент
• Биномиальное распределение
• Каталонский номер
• язык Дейка
• Треугольник Паскаля

Ссылки

• Фусс, Н. И. (1791). «Решение вопроса, сколькими способами многоугольник с n сторонами можно разложить на многоугольник с m сторон по диагоналям». Новые известия Императорской Петропавловской Академии Наук . 9 : 243–251.
• Риордан, Дж. (1968). Комбинаторные тождества . Уайли. ISBN  978-0471722755 .
• Биш, Дитмар; Джонс, Воган (1997). «Алгебры, связанные с промежуточными подфакторами». Математические изобретения . 128 (1): 89–157. Бибкод : 1997InMat.128...89J . дои : 10.1007/s002220050137 . S2CID   119372640 .
• Пшитицкий, Йозеф Х.; Сикора, Адам С. (2000). «Разрезы многоугольников и числа Эйлера, Фусса, Киркмана и Кэли». Журнал комбинаторной теории, серия А. 92 : 68–76. arXiv : math/9811086 . дои : 10.1006/jcta.1999.3042 . S2CID   15724561 .
• Аваль, Жан-Кристоф (2008). «Многомерные числа Фусса-Каталона». Дискретная математика . 20 (308): 4660–4669. arXiv : 0711.0906 . дои : 10.1016/j.disc.2007.08.100 . S2CID   509695 .
• Алексеев Н.; Гетце, Ф; Тихомиров, А. (2010). «Асимптотическое распределение сингулярных значений степеней случайных матриц». Литовский математический журнал . 50 (2): 121–132. arXiv : 1012.2743 . дои : 10.1007/s10986-010-9074-4 . S2CID   3799186 .
• Млотковский, Войцех (2010). «Числа Фусса-Каталона в некоммутативной вероятности» . Документа Математика . 15 : 939–955. дои : 10.4171/дм/318 . S2CID   8083529 .
• Пенсон, Карол А.; Зичковский, Кароль (2011). «Произведение матриц Джинибре: распределения Фусса-Каталана и Ренея». Физический обзор E . 83 (6): 061118. arXiv : 1103.3453 . Бибкод : 2011PhRvE..83f1118P . дои : 10.1103/PhysRevE.83.061118 . ПМИД   21797313 . S2CID   15289531 .
• Гордон, Ян Г.; Гриффет, Стивен (2012). «Каталонские числа для групп комплексных отражений». Американский журнал математики . 134 (6): 1491–1502. arXiv : 0912.1578 . дои : 10.1353/ajm.2012.0047 . S2CID   2654664 .
• Млотковски, В.; Пенсон, Калифорния (2015). «Семейство положительно определенных последовательностей типа Фусса». arXiv : 1507.07312 [ мат.PR ].
• Он, Тянь-Сяо; Шапиро, Луи В. (2017). «Матрицы Фусса-Каталана, их взвешенные суммы и подгруппы стабилизаторов группы Риордана» . Линейная алгебра и ее приложения . 532 : 25–42. дои : 10.1016/j.laa.2017.06.025 .