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

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

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

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

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

Пример

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

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

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

Биекция для n = 3 {displaystyle n=3}

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

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

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

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

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

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

Свойства

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

S 0 = 1 ; S n = S n − 1 + ∑ i = 0 n − 1 S i S n − 1 − i , n ≥ 1 . {displaystyle S_{0}=1;qquad S_{n}=S_{n-1}+sum _{i=0}^{n-1}S_{i}S_{n-1-i},quad ngeq 1;.}

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

∑ n = 1 ∞ S n x n = 1 − x − 1 − 6 x + x 2 2 x {displaystyle sum _{n=1}^{infty }S_{n}x^{n}={frac {1-x-{sqrt {1-6x+x^{2}}}}{2x}}}

Приложения

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