Суетиться – каталонское число - Fuss–Catalan number

В комбинаторная математика и статистика, Суета – каталонский числа - это числа в форме

${\displaystyle 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)}}.}$

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

В некоторых публикациях это уравнение иногда называют Двухпараметрические числа Фусса – Каталонии. или же Числа Ренея. Подразумевается однопараметрические числа Фусса-Каталонии когда р= 1 и п=2.

Использует

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

Примеры с ${\displaystyle p=2}$:

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

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

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

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

Примеры с ${\displaystyle p=3}$:

${\displaystyle A_{m}(3,1)=1,1,3,12,55,273,1428,7752,43263,246675,\ldots }$ OEIS: A001764

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

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

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

Примеры с ${\displaystyle p=4}$:

${\displaystyle A_{m}(4,1)=1,1,4,22,140,969,7084,53820,420732,3362260,\ldots }$ OEIS: A002293

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

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

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

Алгебра

Повторение

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

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

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

и

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

можно получить все остальные числа Фусса – Каталонии, если п является целое число.

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

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

Производящая функция

Перефразируя Плотности распределений Ренея ^[2] бумага, пусть обычная производящая функция по индексу м определяется следующим образом:

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

Рассматривая уравнения (1) и (2), когда р= 1 следует, что

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

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

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

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

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

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

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

Рекурсивное представление

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

${\displaystyle 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)}$

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

${\displaystyle 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)}$

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

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

${\displaystyle 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}}}$

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

Смотрите также

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

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

1. Кларк, Дэвид (1996). «Компактные попытки». Компактные пэт-деревья (Тезис). п. 34.
2. Млотковский, Войцех; Пенсон, Кароль А .; Жичковский, Кароль (2013). «Плотности распределений Ренея». Documenta Mathematica. 18: 1593–1596. arXiv:1211.7259. Bibcode:2012arXiv1211.7259M.

• Фусс, Н. И. (1791). "Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi queat". Nova Acta Academiae Scientiarum Imperialis Petropolitanae. 9: 243–251.
• Риордан, Дж. (1968). Комбинаторные тождества. Вайли. ISBN  978-0471722755.
• Биш, Дитмар; Джонс, Воан (1997). «Алгебры, ассоциированные с промежуточными субфакторами». Inventiones Mathematicae. 128 (1): 89–157. Bibcode:1997InMat.128 ... 89J. Дои:10.1007 / s002220050137. S2CID  119372640.
• Przytycki, Jozef H .; Сикора, Адам С. (2000). «Многоугольные разрезы и числа Эйлера, Фусса, Киркмана и Кэли». Журнал комбинаторной теории, серия А. 92: 68–76. arXiv:математика / 9811086. Дои:10.1006 / jcta.1999.3042.
• Аваль, Жан-Кристоф (2008). «Многовариантные числа Фусса-Каталонии». Дискретная математика. 20 (308): 4660–4669. arXiv:0711.0906. Дои:10.1016 / j.disc.2007.08.100.
• Алексеев, Н .; Götze, F; Тихомиров, А. (2010). «Асимптотическое распределение сингулярных значений степеней случайных матриц». Литовский математический журнал. 50 (2): 121–132. arXiv:1012.2743. Дои:10.1007 / s10986-010-9074-4.
• Млотковский, Войцех (2010). "Суетливые числа Каталонии в некоммутативной вероятности". Documenta Mathematica. 15: 939–955.
• Пенсон, Кароль А .; Жичковский, Кароль (2011). «Произведение матриц Жинибра: распределения Фусса-Каталана и Ренея». Физический обзор E. 83 (6): 061118. arXiv:1103.3453. Bibcode:2011PhRvE..83f1118P. Дои:10.1103 / PhysRevE.83.061118. PMID  21797313.
• Гордон, Ян Дж .; Гриффет, Стивен (2012). «Каталонские числа для сложных групп отражений». Американский журнал математики. 134 (6): 1491–1502. arXiv:0912.1578. Дои:10.1353 / ajm.2012.0047.
• Mlotkowski, W .; Пенсон, К. А. (2015). «Семейство положительно определенных последовательностей типа Фусса». arXiv:1507.07312 [math.PR ].
• Хэ, Тянь-Сяо; Шапиро, Луи В. (2017). «Матрицы Фусса-Каталана, их весовые суммы и стабилизирующие подгруппы группы Риордана». Линейная алгебра и ее приложения. 532: 25–42. Дои:10.1016 / j.laa.2017.06.025.