Числа Шрёдера
Числа Шрёдера (нем. Schröder) (точнее, большие числа Шрёдера) в комбинаторике описывают количества путей из левого нижнего угла квадратной решётки n×n в противоположный по диагонали угол, используя только ходы вверх, вправо или вверх-вправо («ходом короля»), с дополнительным условием, что пути не поднимаются выше упомянутой диагонали. Именно это дополнительное условие отличает эту последовательность от чисел Деланноя. Названы в честь немецкого математика Эрнеста Шрёдера.
Последовательность больших чисел Шрёдера начинается так:
Ричард Стэнли, профессор Массачусетского политехнического института, утверждает, что Гиппарх посчитал 10-е число Шрёдера 1037718, не упоминая способ, каким к нему пришёл.
Пример
[править | править код]На рисунке ниже приведены 6 путей Шрёдера на сетке 2 × 2:
Большие и малые числа Шрёдера
[править | править код]Большие числа Шрёдера считают количество путей из точки (0, 0) в (2, 0), использующих только шаги вправо-вверх или вправо-вниз (шаги (1, 1) или (1, —1)) или двойные шаги вправо (2, 0), которые не опускаются ниже оси абсцисс.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/%D0%91%D0%B8%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%D0%A8%D1%80%D1%91%D0%B4%D0%B5%D1%80%D0%B0.jpg/220px-%D0%91%D0%B8%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%D0%A8%D1%80%D1%91%D0%B4%D0%B5%D1%80%D0%B0.jpg)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/%D0%91%D0%B8%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%D0%A8%D1%80%D1%91%D0%B4%D0%B5%D1%80%D0%B0_%D0%B4%D0%BB%D1%8F_%D1%82%D1%80%D1%91%D1%85.jpg/220px-%D0%91%D0%B8%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%D0%A8%D1%80%D1%91%D0%B4%D0%B5%D1%80%D0%B0_%D0%B4%D0%BB%D1%8F_%D1%82%D1%80%D1%91%D1%85.jpg)
Малые числа Шрёдера отличаются тем, что запрещены двойные шаги вправо, лежащие на оси абсцисс. Очевидно, . Остальные малые числа Шрёдера вдвое меньше соответствующих больших чисел: при .
Для доказательства этого равенства построим биекцию между путями Шрёдера, в которых есть шаг, лежащий на оси абсцисс, и путями той же длины, в которых нет такого шага. Если в пути Шрёдера есть хотя бы один горизонтальный шаг, лежащий на одном уровне с началом пути, рассмотрим самый левый (красный) такой шаг и, не меняя предшествующую ему (зелёную) часть, поставим следующую за ним (синюю) часть на «ножки».
Эквивалентные определения
[править | править код]Большое число Шрёдера равно количеству способов разбить прямоугольник на n + 1 меньших прямоугольников, используя n разрезов, с ограничением, что есть n точек внутри прямоугольника, никакие две из которых не лежат на одной прямой, параллельной сторонам прямоугольника, и каждый разрез проходит через одну из этих точек и делит только один прямоугольник на два. Рисунок показывает 6 способов разрезания на 3 прямоугольника с помощью 2 разрезов:
Большие числа Шрёдера расположены по диагонали следующей таблицы: , где — число -го ряда -го столобца.
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|---|
0 | 1 | ||||||
1 | 1 | 2 | |||||
2 | 1 | 4 | 6 | ||||
3 | 1 | 6 | 16 | 22 | |||
4 | 1 | 8 | 30 | 68 | 90 | ||
5 | 1 | 10 | 48 | 146 | 304 | 394 | |
6 | 1 | 12 | 70 | 264 | 714 | 1412 | 1806 |
Таблица заполнена по рекуррентному правилу для положительных и , причём и при . Можно доказать, что сумма -го ряда этой таблицы равна -му малому числу Шрёдера .
Свойства
[править | править код]- Числа Шрёдера удовлетворяют рекуррентному соотношению:
Приложения
[править | править код]Числа Шрёдера могут быть использованы для вычисления количества разбиений ацтекского бриллианта.
См. также
[править | править код]Ссылки
[править | править код]- Weisstein, Eric W. Schröder Number (англ.) на сайте Wolfram MathWorld.
- Ричард П. Стэнли: Приложение про числа Каталана в Enumerative Combinatorics, Volume 2 (Перечислительная комбинаторика)