Число Моцкіна
Число Моцкіна для даного числа n — це кількість можливих варіантів з'єднання n різних точок на колі хордами, які не перетинаються (хорди можуть виходити не з кожної точки). Числа Моцкіна названі на честь Шаблон:Нп і мають багато проявів у геометрії, комбінаториці і теорії чисел.
Числа Моцкіна для формують послідовність:
- 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, … Шаблон:OEIS
Приклади
Малюнки демонструють 9 способів поєднати 4 точки на колі хордами, які не перетинаються:
А ці показують 21 спосіб з'єднати 5 точок:
Властивості
Числа Моцкіна задовольняють рекурентним співвідношенням
Числа Моцкіна можуть бути виражені через біноміальні коефіцієнти і числа Каталана:
Просте число Моцкіна — це число Моцкіна, яке є простим, таких відомо чотири:
- 2, 127, 15511, 953467954114363... Шаблон:OEIS
Інтерпретації в комбінаториці
Число Моцкіна для n також є кількістю додатних цілих послідовностей довжини n-1, у яких початковий і кінцевий елементи дорівнюють 1 або 2, а різниця між будь-якими двома послідовними елементами дорівнює -1, 0 або 1.
Також число Моцкіна для n задає кількість маршрутів з точки (0, 0) до точки (n, 0) за n кроків, якщо дозволено переміщуватися лише вправо (вгору, вниз або прямо) на кожному кроці, і забороняється опускатися нижче осі y = 0.
Наприклад, на рисунку показано 9 можливих шляхів Моцкіна від (0, 0) до (4, 0):
Існує щонайменше чотирнадцять різних проявів чисел Моцкіна в різних галузях математики, які перерахували Донагі та Шапіро 1977 року в своєму огляді чисел Моцкіна.[1]
Гвіберт, Пергола та Пінзані 2001 року показали, що Шаблон:Прояснити перераховані числами Моцкіна.[2]