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

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

Назван в честь	Теодор Моцкин
Год публикации	1948
Автор публикации	Теодор Моцкин
Количество известных терминов	бесконечность
Формула	см . Свойства
Первые сроки	1, 1 , 2 , 4 , 9 , 21 , 51
ОЭИС Индекс	А001006 Моцкин

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

Числа Моцкина $M_{n}$ для $n=0,1,\dots$ сформировать последовательность:

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

Примеры

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

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

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

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

$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}.$

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

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

и наоборот,

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

Это дает

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

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

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

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

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

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

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

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

$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) показали, что вексиллярные инволюции нумеруются числами Моцкина.

См. также

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

Ссылки

• Бернхарт, Фрэнк Р. (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

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

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