Число Моцкина

В математике n -ое число Моцкина — это число различных способов провести непересекающиеся хорды между n точками окружности ( не обязательно касаясь каждой точки хордой). Числа Моцкина названы в честь Теодора Моцкина и имеют разнообразные приложения в геометрии , комбинаторике и теории чисел .

Числа Моцкина образуют последовательность: ${\displaystyle M_{n}}$ ${\displaystyle n=0,1,\dots }$

1, 1 , 2 , 4 , 9 , 21 , 51 , 127 , 323, 835, ... (последовательность A001006 в OEIS )

Примеры

На следующем рисунке показаны 9 способов проведения непересекающихся хорд между 4 точками окружности ( M ₄ = 9 ):

На следующем рисунке показаны 21 способ проведения непересекающихся хорд между 5 точками окружности ( M ₅ = 21 ):

Характеристики

Числа Моцкина удовлетворяют рекуррентным соотношениям

${\displaystyle M_{n}=M_{n-1}+\sum _{i=0}^{n-2}M_{i}M_{n-2-i}={\frac {2n+1}{n+2}}M_{n-1}+{\frac {3n-3}{n+2}}M_{n-2}.}$

Числа Моцкина можно выразить через биномиальные коэффициенты и числа Каталана :

${\displaystyle M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}C_{k},}$

и наоборот, ^[1]

${\displaystyle C_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}M_{k}}$

Это дает

${\displaystyle \sum _{k=0}^{n}C_{k}=1+\sum _{k=1}^{n}{\binom {n}{k}}M_{k-1}.}$

Производящая функция чисел Моцкина удовлетворяет ${\displaystyle m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}}$

${\displaystyle x^{2}m(x)^{2}+(x-1)m(x)+1=0}$

и явно выражено как

${\displaystyle m(x)={\frac {1-x-{\sqrt {1-2x-3x^{2}}}}{2x^{2}}}.}$

Интегральное представление чисел Моцкина имеет вид

${\displaystyle M_{n}={\frac {2}{\pi }}\int _{0}^{\pi }\sin(x)^{2}(2\cos(x)+1)^{n}dx}$.

Они имеют асимптотическое поведение

${\displaystyle M_{n}\sim {\frac {1}{2{\sqrt {\pi }}}}\left({\frac {3}{n}}\right)^{3/2}3^{n},~n\to \infty }$.

Простое число Моцкина — это число Моцкина, которое является простым . Известно четыре таких простых числа:

2, 127, 15511, 953467954114363 (последовательность A092832 в OEIS )

Комбинаторные интерпретации

Число Моцкина для n также является числом положительных целочисленных последовательностей длины n − 1, в которых начальный и конечный элементы равны 1 или 2, а разность между любыми двумя последовательными элементами равна −1, 0 или 1. Эквивалентно, число Моцкина для n является числом положительных целочисленных последовательностей длины n + 1, в которых начальный и конечный элементы равны 1, а разность между любыми двумя последовательными элементами равна −1, 0 или 1.

Кроме того, число Моцкина для n дает количество маршрутов в верхнем правом квадранте сетки от координаты (0, 0) до координаты ( n , 0) за n шагов, если на каждом шаге разрешено двигаться только вправо (вверх, вниз или прямо), но запрещено опускаться ниже оси y = 0.

Например, на следующем рисунке показаны 9 допустимых путей Моцкина от (0, 0) до (4, 0):

Существует по крайней мере четырнадцать различных проявлений чисел Моцкина в различных областях математики, как перечислили Донахи и Шапиро (1977) в своем обзоре чисел Моцкина. Гвиберт, Пергола и Пинзани (2001) показали, что вексиллярные инволюции перечисляются числами Моцкина.

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

• Номер телефона , представляющий количество способов проведения хорд, если разрешены пересечения
• Число Деланнуа
• Число Нараяны
• Число Шредера

Ссылки

1. И Ван и Чжи-Хай Чжан (2015). "Комбинаторика обобщенных чисел Моцкина" (PDF) . Журнал целочисленных последовательностей (18).

• Бернхарт, Фрэнк Р. (1999), «Числа Каталана, Моцкина и Риордана», Дискретная математика , 204 (1–3): 73–112, doi : 10.1016/S0012-365X(99)00054-0
• Донахи, Р.; Шапиро, Л. В. (1977), «Числа Моцкина», Журнал комбинаторной теории , Серия A, 23 (3): 291–301, doi : 10.1016/0097-3165(77)90020-6 , MR  0505544
• Guibert, O.; Pergola, E.; Pinzani, R. (2001), «Вексиллярные инволюции перечисляются числами Моцкина», Annals of Combinatorics , 5 (2): 153–174, doi :10.1007/PL00001297, ISSN  0218-0006, MR  1904383, S2CID  123053532
• Motzkin, TS (1948), «Соотношения между гиперповерхностными поперечными отношениями и комбинаторная формула для разбиений многоугольника, для постоянного преобладания и для неассоциативных произведений», Бюллетень Американского математического общества , 54 (4): 352–360, doi : 10.1090/S0002-9904-1948-09002-4

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

• Вайсштейн, Эрик В. «Число Моцкина». MathWorld .