число Шредера

Математическая целочисленная последовательность

В математике число Шредера , также называемое большим числом Шредера или большим числом Шредера , описывает количество путей решетки от юго-западного угла сетки до северо-восточного угла с использованием только отдельных шагов на север, северо-восток или восток, которые не поднимаются выше диагональ ЮЗ-СВ. ^[1] ${\displaystyle S_{n},}$ ${\displaystyle (0,0)}$ ${\displaystyle n\times n}$ ${\displaystyle (n,n),}$ ${\displaystyle (0,1);}$ ${\displaystyle (1,1);}$ ${\displaystyle (1,0),}$

Первые несколько чисел Шредера

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

где и Они были названы в честь немецкого математика Эрнста Шредера . ${\displaystyle S_{0}=1}$ ${\displaystyle S_{1}=2.}$

Примеры

На следующем рисунке показаны 6 таких путей через сетку: ${\displaystyle 2\times 2}$

Связанные конструкции

Путь Шредера длины представляет собой решетчатый путь от до с ступенями на северо-восток, восток и юго-восток, не идущими ниже оси -. Число Шредера — это число путей Шредера длины . ^[2] На следующем рисунке показаны 6 путей Шредера длины 2. ${\displaystyle n}$ ${\displaystyle (0,0)}$ ${\displaystyle (2n,0)}$ ${\displaystyle (1,1);}$ ${\displaystyle (2,0);}$ ${\displaystyle (1,-1),}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle n}$

Точно так же числа Шредера подсчитывают количество способов разделить прямоугольник на меньшие прямоугольники, используя разрезы через точки, заданные внутри прямоугольника в общем положении, причем каждый разрез пересекает одну из точек и делит только один прямоугольник на две части (т. е. количество конструктивно-различные гильотинные перегородки ). Это похоже на процесс триангуляции , при котором фигура делится на непересекающиеся треугольники вместо прямоугольников. На следующем рисунке показаны 6 таких разрезов прямоугольника на 3 прямоугольника с помощью двух разрезов: ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle n}$

На рисунке ниже показаны 22 разреза прямоугольника на 4 прямоугольника с помощью трех разрезов:

Число Шредера также учитывает сепарабельные перестановки длины ${\displaystyle S_{n}}$ ${\displaystyle n-1.}$

Связанные последовательности

Числа Шредера иногда называют большими или большими числами Шредера, потому что существует еще одна последовательность Шредера: маленькие числа Шредера , также известные как числа Шредера-Гиппарха или суперкаталонские числа . Связи между этими путями можно увидеть несколькими способами:

• Рассмотрим пути от до со ступеньками и не возвышающиеся над главной диагональю. Есть два типа путей: те, у которых есть движение по главной диагонали, и те, у которых его нет. (Большие) числа Шредера учитывают оба типа путей, а маленькие числа Шредера учитывают только пути, которые только касаются диагонали, но не совершают движений по ней. ^[3] ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$ ${\displaystyle (1,1),}$ ${\displaystyle (2,0),}$ ${\displaystyle (1,-1)}$
• Точно так же, как существуют (большие) пути Шредера, маленький путь Шредера — это путь Шредера, который не имеет горизонтальных ступеней на оси - . ^[4] ${\displaystyle x}$
• Если –-е число Шредера и –-е малое число Шредера, то для ^[4] ${\displaystyle S_{n}}$ ${\displaystyle n}$ ${\displaystyle s_{n}}$ ${\displaystyle n}$ ${\displaystyle S_{n}=2s_{n}}$ ${\displaystyle n>0}$ ${\displaystyle (S_{0}=s_{0}=1).}$

Пути Шредера похожи на пути Дейка , но допускают горизонтальный шаг, а не только диагональные шаги. Другой похожий путь — это путь, который учитывают числа Моцкина ; пути Моцкина допускают те же диагональные пути, но допускают только один горизонтальный шаг (1,0) и отсчитывают такие пути от до . ^[5] ${\displaystyle (0,0)}$ ${\displaystyle (n,0)}$

Существует также треугольный массив , связанный с числами Шредера, который обеспечивает рекуррентное соотношение ^[6] (хотя и не только с числами Шредера). Первые несколько терминов

1, 1, 2, 1, 4, 6, 1, 6, 16, 22, .... (последовательность A033877 в OEIS ).

Связь с числами Шредера легче увидеть, когда последовательность имеет треугольную форму:

Тогда числа Шредера — это диагональные элементы, т. е. где находится элемент в строке и столбце . Рекуррентное соотношение, заданное этим расположением, имеет вид ${\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)}$

с и для . ^[6] Еще одно интересное наблюдение: сумма четвертой строки представляет собой первое маленькое число Шредера ; то есть, ${\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}}$.

Рекуррентные отношения

С , , ^[7] ${\displaystyle S_{0}=1}$ ${\displaystyle S_{1}=2}$

${\displaystyle S_{n}=3S_{n-1}+\sum _{k=1}^{n-2}S_{k}S_{n-k-1}}$для ${\displaystyle n\geq 2}$

а также

${\displaystyle S_{n}={\frac {6n-3}{n+1}}S_{n-1}-{\frac {n-2}{n+1}}S_{n-2}}$для ${\displaystyle n\geq 2}$

Генерирующая функция

Производящая функция последовательности : ${\displaystyle G(x)}$ ${\displaystyle (S_{n})_{n\geq 0}}$

${\displaystyle G(x)={\frac {1-x-{\sqrt {1-6x+x^{2}}}}{2x}}=\sum _{n=0}^{\infty }S_{n}x^{n}}$. ^[7]

Это можно выразить через производящую функцию каталонских чисел как ${\displaystyle C(x)={\frac {1-{\sqrt {1-4x}}}{2x}}}$

${\displaystyle G(x)={\frac {1}{1-x}}C{\big (}{\frac {x}{(1-x)^{2}}}{\big )}.}$

Использование

Одна из тем комбинаторики — замощение фигур, а частный пример — замощение домино ; в данном случае вопрос заключается в следующем: «Сколько домино (то есть или прямоугольников) мы можем расположить на некоторой фигуре так, чтобы ни одно из домино не перекрывалось, вся форма была закрыта и ни одно из домино не торчало из формы?» Форма, с которой связаны числа Шредера, — это ацтекский алмаз . Ниже для справки показан ацтекский ромб 4-го порядка с возможной укладкой в ​​домино. ${\displaystyle 1\times 2}$ ${\displaystyle 2\times 1}$

Оказывается, что определитель ганкелевой матрицы чисел Шредера, то есть квадратная матрица, чей элемент является номером домино, представляет собой количество разбиений домино порядка ацтекского алмаза, что равно ^[8] То есть, ${\displaystyle (2n-1)\times (2n-1)}$ ${\displaystyle (i,j)}$ ${\displaystyle S_{i+j-1},}$ ${\displaystyle n}$ ${\displaystyle 2^{n(n+1)/2}.}$

${\displaystyle {\begin{vmatrix}S_{1}&S_{2}&\cdots &S_{n}\\S_{2}&S_{3}&\cdots &S_{n+1}\\\vdots &\vdots &\ddots &\vdots \\S_{n}&S_{n+1}&\cdots &S_{2n-1}\end{vmatrix}}=2^{n(n+1)/2}.}$

Например:

• ${\displaystyle {\begin{vmatrix}2\end{vmatrix}}=2=2^{1(2)/2}}$

• ${\displaystyle {\begin{vmatrix}2&6\\6&22\end{vmatrix}}=8=2^{2(3)/2}}$

• ${\displaystyle {\begin{vmatrix}2&6&22\\6&22&90\\22&90&394\end{vmatrix}}=64=2^{3(4)/2}}$

Смотрите также

• Число Деланной
• Число Моцкина
• Число Нараяны
• Полиномы Нараяны
• Число Шредера – Гиппарха
• Каталонский номер

Рекомендации

1. Слоан, Нью-Джерси (ред.). «Последовательность A006318 (Большие числа Шредера (или большие числа Шредера, или большие числа Шредера)).» Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС . Проверено 5 марта 2018 г.
2. Ардила, Федерико (2015). «Алгебраические и геометрические методы в перечислительной комбинаторике». Справочник по перечислительной комбинаторике . Бока-Ратон, Флорида: CRC Press. стр. 3–172.
3. Слоан, Нью-Джерси (ред.). «Последовательность A001003 (вторая проблема Шредера (обобщенные скобки); также называется суперкаталонскими числами или маленькими числами Шредера)». Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС . Проверено 5 марта 2018 г.
4. Дрейк, Дэн (2010). «Биекции от взвешенных путей Дика к путям Шредера». arXiv : 1006.1959 [math.CO].
5. Дэн, Ева Ю.П.; Ян, Вэй-Цзюнь (2008). «Некоторые тождества чисел Каталана, Моцкина и Шредера». Дискретная прикладная математика . 156 (166–218X): 2781–2789. дои : 10.1016/j.dam.2007.11.014 .
6. Слоан, NJA «Треугольный массив, связанный с числами Шредера». Электронная энциклопедия целочисленных последовательностей . Проверено 5 марта 2018 г.
7. Ой, Фэн; Го, Бай-Ни (2017). «Некоторые явные и рекурсивные формулы больших и малых чисел Шредера». Арабский журнал математических наук . 23 (1319–5166): 141–147. дои : 10.1016/j.ajmsc.2016.06.002 .
8. Ю, Сен-Пэн; Фу, Дун-Шань (2005). «Простое доказательство ацтекской теоремы об алмазе». Электронный журнал комбинаторики . 12 (1077–8926): Исследовательский документ 18, 8. doi : 10.37236/1915 . S2CID  5978643.

дальнейшее чтение

• Вайсштейн, Эрик В. «Число Шредера». Математический мир .
• Стэнли, Ричард П.: каталонское приложение к перечислительной комбинаторике, том 2