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

В математике 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), «Числа Каталана, Моцкина и Риордана», Discrete Mathematics , 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
• Гвиберт, О.; Пергола, Э.; Пинцани, Р. (2001), «Вексиллярные инволюции перечисляются числами Моцкина», Annals of Combinatorics , 5 (2): 153–174, doi : 10.1007/PL00001297, ISSN  0218-0006, MR  1904383, S2CID  123053532
• Моцкин, Т.С. (1948), «Отношения между перекрестными отношениями гиперповерхностей и комбинаторной формулой для разбиений многоугольника, для постоянного перевеса и для неассоциативных произведений», Бюллетень Американского математического общества , 54 (4): 352– 360, номер документа : 10.1090/S0002-9904-1948-09002-4

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

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