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

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

 1, 2, 6, 22, 90, 394, 1806, 8558, \ldots. .
 Ричард Стэнли, профессор Массачусетского политехнического института,утверждает, что Гиппарх посчитал 10-е число Шрёдера 1037718, не упоминаяправда способ, каким к нему пришёл.

Пример


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

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


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

Свойства



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


S0=1;Sn=Sn1+i=0n1SiSn1i,n1.

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


n=1Snxn=1x16x+x22x