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

Числа Шрёдера (нем. 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), которые не опускаются ниже оси абсцисс.

Малые числа Шрёдера $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}$ .