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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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 (Перечислительная комбинаторика)