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

(перенаправлено с «Число Шрёдера»)

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

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

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

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

Пример

править

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

 

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

править

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

 
 
Биекция для  

Малые числа Шрёдера   отличаются тем, что запрещены двойные шаги вправо, лежащие на оси абсцисс. Очевидно,  . Остальные малые числа Шрёдера вдвое меньше соответствующих больших чисел:   при  .

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

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

править

Большое число Шрёдера равно количеству способов разбить прямоугольник на 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

Таблица заполнена по рекуррентному правилу   для положительных   и  , причём   и   при  . Можно доказать, что сумма  -го ряда этой таблицы равна  -му малому числу Шрёдера  .

Свойства

править
 
 

Приложения

править

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

См. также

править

Ссылки

править