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

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

Назван в честь	Эрнст Шредер
Количество известных терминов	бесконечность
Первые сроки	1 , 2 , 6 , 22 , 90 , 394 , 1806
ОЭИС Индекс	А006318 Большой Шредер

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

к н	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

Тогда числа Шредера являются диагональными элементами, т.е. $S_{n}=T(n,n)$ где $T(n,k)$ это запись в строке $n$ и столбец $k$. Рекуррентное соотношение, заданное этим расположением, имеет вид

$T(n,k)=T(n,k-1)+T(n-1,k-1)+T(n-1,k)$

с $T(1,k)=1$ и $T(n,k)=0$ для $k>n$. Еще одно интересное наблюдение: сумма $n$й ряд - это $(n+1)$маленькое число Шредера ; то есть,

$\sum _{k=0}^{n}T(n,k)=s_{n+1}$.

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

С $S_{0}=1$, $S_{1}=2$,

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

а также

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

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

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

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

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

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

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

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

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

${\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}.$

Например:

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

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

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

См. также

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

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

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