Числа Деланоя: відмінності між версіями
[перевірена версія] | [очікує на перевірку] |
Немає опису редагування |
Функція пропозицій посилань: додано 1 посилання. |
||
Рядок 1: | Рядок 1: | ||
'''Числа Делануа'''<ref>''Смирнов Е. Ю.'' [https://www.mccme.ru/dubna/2014/notes/smirnov-notes-v2.pdf#page=38 Три взгляда на ацтекский бриллиант]</ref> або '''числа Деланоя'''<ref>''Кохась К.'' [http://www.mathnet.ru/php/getFT.phtml?jrnid=znsl&paperid=2165&what=fullt&option_lang=rus#page=30 Разбиение ацтекских диамантов и квадратов на домино]</ref> ({{Lang-fr|Delannoy}}<span lang="fr" style="font-style:italic;">)</span> '''D (a, b)''' в комбінаториці описують кількості шляхів з лівого нижнього кута прямокутної решітки ''(a,'' ''b)'' в протилежний по діагоналі кут, використовуючи тільки ходи вгору, вправо або вгору-вправо («ходом [[Король (шахи)|короля]]<nowiki/>»). В ''a''-вимірному [[Клітинний автомат|клітинному автоматі]] ''D (a, b)'' задають кількість клітинок в [[Окіл фон Неймана|околиці фон Неймана]] радіусом ''b'' ({{OEIS|A008288}}); кількість клітинок на поверхні околиці задає {{OEIS|A266213}}. Названі на честь французького математика {{Нп|Анрі Оґюст Делануа|Анрі Оґюста Делануа|fr|Henri Auguste Delannoy}}<ref>{{Citation|last1=Banderier|first1=Cyril|last2=Schwer|first2=Sylviane|title=Why Delannoy numbers?|year=2005|journal=Journal of Statistical Planning and Inference|volume=135|issue=1|pages=40–54|arxiv=math/0411128|doi=10.1016/j.jspi.2005.02.004}}</ref>. |
'''Числа Делануа'''<ref>''Смирнов Е. Ю.'' [https://www.mccme.ru/dubna/2014/notes/smirnov-notes-v2.pdf#page=38 Три взгляда на ацтекский бриллиант]</ref> або '''числа Деланоя'''<ref>''Кохась К.'' [http://www.mathnet.ru/php/getFT.phtml?jrnid=znsl&paperid=2165&what=fullt&option_lang=rus#page=30 Разбиение ацтекских диамантов и квадратов на домино]</ref> ({{Lang-fr|Delannoy}}<span lang="fr" style="font-style:italic;">)</span> '''D (a, b)''' в [[Комбінаторика|комбінаториці]] описують кількості шляхів з лівого нижнього кута прямокутної решітки ''(a,'' ''b)'' в протилежний по діагоналі кут, використовуючи тільки ходи вгору, вправо або вгору-вправо («ходом [[Король (шахи)|короля]]<nowiki/>»). В ''a''-вимірному [[Клітинний автомат|клітинному автоматі]] ''D (a, b)'' задають кількість клітинок в [[Окіл фон Неймана|околиці фон Неймана]] радіусом ''b'' ({{OEIS|A008288}}); кількість клітинок на поверхні околиці задає {{OEIS|A266213}}. Названі на честь французького математика {{Нп|Анрі Оґюст Делануа|Анрі Оґюста Делануа|fr|Henri Auguste Delannoy}}<ref>{{Citation|last1=Banderier|first1=Cyril|last2=Schwer|first2=Sylviane|title=Why Delannoy numbers?|year=2005|journal=Journal of Statistical Planning and Inference|volume=135|issue=1|pages=40–54|arxiv=math/0411128|doi=10.1016/j.jspi.2005.02.004}}</ref>. |
||
== Деякі значення == |
== Деякі значення == |
Поточна версія на 08:52, 2 серпня 2022
Числа Делануа[1] або числа Деланоя[2] (фр. Delannoy) D (a, b) в комбінаториці описують кількості шляхів з лівого нижнього кута прямокутної решітки (a, b) в протилежний по діагоналі кут, використовуючи тільки ходи вгору, вправо або вгору-вправо («ходом короля»). В a-вимірному клітинному автоматі D (a, b) задають кількість клітинок в околиці фон Неймана радіусом b (послідовність A008288 з Онлайн енциклопедії послідовностей цілих чисел, OEIS); кількість клітинок на поверхні околиці задає послідовність A266213 з Онлайн енциклопедії послідовностей цілих чисел, OEIS. Названі на честь французького математика Анрі Оґюста Делануа[fr][3].
Для квадратної сітки n×n перші числа Делануа (починаючи з n=0) (послідовність A001850 з Онлайн енциклопедії послідовностей цілих чисел, OEIS):
- 1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, …
Наприклад, D (3,3) = 63, оскільки в квадраті 3 × 3 існує 63 різних шляхи Делануа:
Шляхи, які не піднімаються вище від діагоналі, описують числа Шредера[ru].
Числа Делануа утворюють нескінченну матрицю Делануа, частину якої наведено в таблиці:
k\n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 |
2 | 1 | 5 | 13 | 25 | 41 | 61 | 85 | 113 | 145 | 181 | 221 |
Числа Делануа задовольняють рекурентному співвідношенню: , за початкові умови можна взяти D (0, k) = D (k, 0) = 1.
Це рівняння аналогічне трикутнику Паскаля для біноміальних коефіцієнтів C(m, n):
яке стосується кількості шляхів між тими ж вершинами, але за умови, що допустимі тільки ходи по сторонам клітин.[прояснити]
Якщо врахувати місця, в яких шляхи перетинають діагональ, то можна вивести зв'язок між числами Делануа і біноміальними коефіцієнтами[4] :
де позначено послідовність A266213 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.
Твірна функція для чисел:
Коли розглядаються шляхи в квадраті, числа Делануа рівні:
- , де — поліном Лежандра.
Інші їх властивості:
- ↑ Смирнов Е. Ю. Три взгляда на ацтекский бриллиант
- ↑ Кохась К. Разбиение ацтекских диамантов и квадратов на домино
- ↑ Banderier, Cyril; Schwer, Sylviane (2005), Why Delannoy numbers?, Journal of Statistical Planning and Inference, 135 (1): 40—54, arXiv:math/0411128, doi:10.1016/j.jspi.2005.02.004
- ↑ Martin Aigner. A course in enumeration. — Springer, 2007. — С. 19. — ISBN 978-3-540-39032-4.
- Weisstein, Eric W. Delannoy Number(англ.) на сайті Wolfram MathWorld.
- Richard P. Stanley. Enumerative Combinatorics. — Cambridge University Press, 1999. — Т. 2. — С. 185. — ISBN 0-521-56069-1.