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

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

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

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

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

Пример

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

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

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

Файл:SchroederWalks2.svg

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

Файл:SchroederRectangulation.svg

Свойства

• Числа Шрёдера $S_n$ удовлетворяют рекуррентному соотношению:

$S_0 = 1; \qquad S_n=S_{n-1} + \sum_{i=0}^{n-1}S_i S_{n-1-i},\quad n\ge 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 (Перечислительная комбинаторика)