Числа Шрёдера

Числа Шрёдера (нем. Schröder) (точнее, большие числа Шрёдера) в комбинаторике описывают количества путей из левого нижнего угла квадратной решётки n×n в противоположный по диагонали угол, используя только ходы вверх, вправо или вверх-вправо («ходом короля»), с дополнительным условием, что пути не поднимаются выше упомянутой диагонали. Именно это дополнительное условие отличает эту последовательность от чисел Деланноя. Названы в честь немецкого математика Эрнеста Шрёдера.

Последовательность больших чисел Шрёдера начинается так:

1, 2, 6, 22, 90, 394, 1806, 8558, …. последовательность A006318 в OEIS.

Ричард Стэнли, профессор Массачусетского политехнического института, утверждает, что Гиппарх посчитал 10-е число Шрёдера 1037718, не упоминая способ, каким к нему пришёл.

Пример

На рисунке ниже приведены 6 путей Шрёдера на сетке 2 × 2:

Большие и малые числа Шрёдера

Большие числа Шрёдера $S_{n+1}$ считают количество путей из точки (0, 0) в (2 $n$ , 0), использующих только шаги вправо-вверх или вправо-вниз (шаги (1, 1) или (1, —1)) или двойные шаги вправо (2, 0), которые не опускаются ниже оси абсцисс.

Биекция для

n=3

Малые числа Шрёдера $s_{n}$ отличаются тем, что запрещены двойные шаги вправо, лежащие на оси абсцисс. Очевидно, $s_{0}=S_{0}=1$ . Остальные малые числа Шрёдера вдвое меньше соответствующих больших чисел: $S_{n}=2s_{n}$ при $n>0$ .

Для доказательства этого равенства построим биекцию между путями Шрёдера, в которых есть шаг, лежащий на оси абсцисс, и путями той же длины, в которых нет такого шага. Если в пути Шрёдера есть хотя бы один горизонтальный шаг, лежащий на одном уровне с началом пути, рассмотрим самый левый (красный) такой шаг и, не меняя предшествующую ему (зелёную) часть, поставим следующую за ним (синюю) часть на «ножки».

Эквивалентные определения

Большое число Шрёдера равно количеству способов разбить прямоугольник на n + 1 меньших прямоугольников, используя n разрезов, с ограничением, что есть n точек внутри прямоугольника, никакие две из которых не лежат на одной прямой, параллельной сторонам прямоугольника, и каждый разрез проходит через одну из этих точек и делит только один прямоугольник на два. Рисунок показывает 6 способов разрезания на 3 прямоугольника с помощью 2 разрезов:

Большие числа Шрёдера расположены по диагонали следующей таблицы: $S_{n}=T(n,n)$ , где $T(n,k)$ — число $n$ -го ряда $k$ -го столобца.

	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

Таблица заполнена по рекуррентному правилу $T(n,k)=T(n,k-1)+T(n-1,k-1)+T(n-1,k)$ для положительных $n$ и $k$ , причём $T(1,k)=1$ и $T(n,k)=0$ при $k>n$ . Можно доказать, что сумма $n$ -го ряда этой таблицы равна $(n+1)$ -му малому числу Шрёдера $\sum _{k=0}^{n}T(n,k)=s_{n+1}$ .

Свойства

Числа Шрёдера $S_{n}$ удовлетворяют рекуррентному соотношению:

S_{0}=1;\qquad S_{n}=S_{n-1}+\sum _{i=0}^{n-1}S_{i}S_{n-1-i},\quad n\geq 1\;.

Производящая функция:

\sum _{n=1}^{\infty }S_{n}x^{n}={\frac {1-x-{\sqrt {1-6x+x^{2}}}}{2x}}

Приложения

Числа Шрёдера могут быть использованы для вычисления количества разбиений ацтекского бриллианта.

См. также

Ссылки

Weisstein, Eric W. Schröder Number (англ.) на сайте Wolfram MathWorld.
Ричард П. Стэнли: Приложение про числа Каталана в Enumerative Combinatorics, Volume 2 (Перечислительная комбинаторика)