슈뢰더 수

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않기 때문에 대체로 검증되지 않은 상태로 남아 있다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2016년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

슈뢰더 수

이름을 따서 명명됨	에른스트 슈뢰더
No. 알려진.	무한의
제1항	1, 2, 6, 22, 90, 394, 1806
OEIS 지수	A006318 라지 슈뢰더

In mathematics, the Schröder number ${\displaystyle S_{n},}$ also called a large Schröder number or big Schröder number, describes the number of lattice paths from the southwest corner ${\displaystyle (0,0)}$ of an ${\displaystyle n\times n}$ grid to the northeast corner ${\displaystyle ($$n,$${\displaystyle \mathrm{n}}$$)},$ 북쪽의 단일 단계만 사용$$, ( 0${\displaystyle ,}$ 1${\displaystyle );}$ ${\displaystyle (0,1);}$ 북동쪽$$,${\displaystyle }$(${\displaystyle 1}$,${\displaystyle }$1${\displaystyle (1,1);}$ 또는$$ 동쪽, (${\displaystyle 1},{\displaystyle 0}$)${\displaystyle }$, ${\displaystyle (1,0),$ SW–NE 대각선 위로 올라오지 않는$$ 것.^[1]

처음 몇 개의 슈뢰더 번호는

1, 2, 6, 22, 90, 394, 1806, 8558, ... (시퀀스 A006318 in OEIS).

여기서 $S{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle 1}$ ${\displaystyle S_{0}=1}$ 및$$ $S{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= 2${\displaystyle S_{1}=2.}$$$ 이들은 독일의 수학자 에른스트 슈뢰더의 이름을 따서 지어졌다.

예

다음 그림은 $2{\displaystyle \mathrm{}}$ ${\displaystyle \times }$ ${\displaystyle 2}$ ${\displaystyle 2\time 2}$ 그리드를$$ 통과하는 6개의 경로를 보여준다.

관련 구성

A Schröder path of length ${\displaystyle n}$ is a lattice path from ${\displaystyle (0,0)}$ to ${\displaystyle (2n,0)}$ with steps northeast, ${\displaystyle (1,1);}$ east, ${\displaystyle (2,0);}$ and southeast, ${\displaystyle (1,-1),}$ that do not$x{\displaystyle }$ ${\displaystyle x}$ -축$$ 아래로 이동하십시오.$n{\displaystyle }$ ${\displaystyle n}$ th$$ Schröder 번호는 길이 $n{\displaystyle }$ ${\displaystyle n}$의 슈뢰더 경로 수입니다$.$^[2]다음 그림은 길이 2의 6개의 슈뢰더 경로를 보여준다.

마찬가지로, 슈뢰더 수는 직사각형을 일반 $위치$에서 직사각형 내부에 주어진 $n{\displaystyle }$ ${\displaystyle n$$}$개의$$ 점을 통해 잘라낸$$ n ${\displaystyle$n}개의 점을 통해 직사각형을 n${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyn+1}$개의$$ 작은 직사각형으로 나누는 방법의 수를 계산한다.(즉, 구조적으로 분리된 단두대 파티션의 수).이는 직사각형 대신 형상을 비과대칭 삼각형으로 나누는 삼각형의 과정과 유사하다.다음 그림은 두 개의 절단을 사용하여 직사각형을 3개의 직사각형으로 6개 분포하는 것을 보여준다.

아래 그림은 세 개의 절단을 사용하여 직사각형을 네 개의 직사각형으로 22개 배포한 것이다.

슈뢰더$$ 번호 $S{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$ 또한 길이 $n{\displaystyle }$- 1${\displaystyle n-1$의 분리 가능한 순열을 계산한다$.$$}$

관련 시퀀스

슈뢰더 수는 슈뢰더-히파르쿠스 숫자 또는 슈퍼카탈란 숫자라고도 알려진 또 다른 슈뢰더 순서가 있기 때문에 크거나 큰 슈뢰더 숫자라고도 불린다.이러한 경로 사이의 연결은 다음과 같은 몇 가지 방법으로 볼 수 있다.

• 주$$ 대각선 위로 상승하지 않는$$${\displaystyle }$(${\displaystyle 0}$, ${\displaystyle 0}$) ${\$$displaystyle (0,0$${\displaystyle )\}}$부터 $({\displaystyle }$${\displaystyle \mathrm{n}}$${\displaystyle }$, ${\displaystyle n}$)$$${\$$displaystyle$${\displaystyle (}$$n$$,$n)까지의 경로를 고려하십시오$.$대각선을 따라 움직이는 경로와 그렇지 않은 경로의 두 종류가 있다.(큰) 슈뢰더 수는 두 가지 경로 유형을 모두 세고, 작은 슈뢰더 수는 대각선만 건드리지만 그 경로를 따라 이동하지 않는 경로만 세고 있다.^[3]
• (큰) 슈뢰더 경로가 있듯이, 작은 슈뢰더 경로는 $x{\displaystyle }$ ${\displaystyle x}$ -축에$$ 수평 단계가 없는 슈뢰더 경로다.^[4]
• 만약 Sn{\displaystyle S_{n}}은 n{n\displaystyle}th슈뢰더 번호와 친구의 n{\displaystyle s_{n}}은 n{n\displaystyle}n을을 빌리려 작은 슈뢰더 번호, Snx2sn{\displaystyle S_{n}=2s_{n}};0{\displaystyle n>0}(S 0s0=1).{\displaystyl.e(S_{$0}=s_{0}=1.$$}$^[4]

슈뢰더 경로는 다이크 경로와 유사하지만 대각선 단계 대신 수평 단계를 허용한다.또 다른 유사한 경로는 Motzkin 번호가 카운트하는 경로 유형이다. Motzkin 경로는 동일한 대각선 경로를 허용하지만 단 하나의 수평 단계(1,0)만 허용하고 (${\displaystyle 0},{\displaystyle }$ ${\displaystyle 0}$) ${\displaystyle (0,0)}$ ~${\displaystyle }$(${\displaystyle }$, ${\displaystyle 0}$) ${\displaystyle (n,0)}$ 사이의 경로를$$ 카운트한다$.$^[5]

슈뢰더 번호와 관련된 삼각 배열도 있어(슈뢰더 번호뿐 아니라) 재발 관계를^[6] 제공한다.처음 몇 가지 조건은

1, 1, 2, 1, 4, 6, 1, 6, 6, 16, 22, ....(OEIS에서 연속 A0338777)이다.

시퀀스가 삼각형 형태일 때 슈뢰더 번호와의 연결을 보다 쉽게 확인할 수 있다.

k n	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

그런 다음 Schröder 번호는 대각선 항목으로, 즉 ${\displaystyle S_{}}$ n${\displaystyle {}_{}}$= ${\displaystyle T(n,}$ ${\displaystyle n}$) ${\displaystyle S_{n}=T(n,$${\displaystyle n}$$)}$ 여기서$$ $T{\displaystyle (n,}$ k${\displaystyle }$) ${\displaystyle$ $T$$(n,k)}$은 $n행{\displaystyle }$ ${\displaystyle$ n$}$ 및 ${\displaystystystyle$ k$}$ 열의 $항목이다.$이 약정에 의해 주어진 재발관계는

${\displaystyle T(n,k)=T(n,k-1)+T(n-1,k-1)+T(n-1,k)}$

with ${\displaystyle T(1,k)=1}$ and ${\displaystyle T(n,k)=0}$ for ${\displaystyle k>n}$.^[6] Another interesting observation to make is that the sum of the ${\displaystyle n}$th row is the ${\displaystyle (n+1)}$st little Schröder number; that is,

${\displaystyle \sum _k^{}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}(n,}$ k${\displaystyle }$)${\displaystyle }$= ${\displaystyle {\mathrm{s}}_{}}$ ${\displaystyle {}_{}}$+ 1 ${\$

재발관계

$S{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle 1}$ ${\displaystyle S_{0}=1},$$$${\displaystyle \mathrm{S}}$ ${\displaystyle {1\mathrm{}}_{}}$= 2 ${\displaystyle S_{1$}=$2},$

${\displaystyle {}_{}}$${\displaystyle \mathrm{Sn<img\; alt="\{\backslash displaystyle\; S\_\{n\}=3S\_\{n-1\}+\backslash sum\; \_\{k=1\}^\{n-2\}S\_\{k\}S\_\{n-k-1\}\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/4c4f2626bbe1553989826dc10c8e0df89fc0ca53"\; style="vertical-align:\; -3.005ex;\; width:27.623ex;\; height:7.343ex;"\; papago-attr-id="179">}}$${\displaystyle {}_{}}$= ${\displaystyle 3}$$$${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle n_{}}$- 1${\displaystyle {}_{}}$+ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{k}}}$= ${\displaystyle \underset{}{\overset{}{1}}}$ n${\displaystyle \underset{}{\overset{}{}}}$- ${\displaystyle \underset{}{\overset{}{2}}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle n_{}}$- ${\displaystyle {\mathrm{k}}_{}}$- 1 ${\$$S_$${n-k-k-1$}$S_{n-k-1$$}:{$$n-k-1}:{$n-1}:{n-1}.

그리고 또한

${\displaystyle {Sn}_{}}$${\displaystyle {}_{}}$= ${\displaystyle \mathrm{6n}}$${\displaystyle \frac{}{}}$- ${\displaystyle \frac{}{}}$+ ${\displaystyle {1S}_{}}$- 1${\displaystyle \frac{}{}}$-${\displaystyle {}_{}\frac{}{}}$ - ${\displaystyle {\mathrm{1n}}_{}\frac{}{}}$+ ${\displaystyle {1S}_{}}$ - ${\displaystyle 2_{}}$ ${\$n-1}-{n-1}-{$n-$${\displaystyle \{}$$n-1$}-{$n-2$}}: nn$2 {\$$displaystyle n-n-n-n-n.$

생성함수

$Sn$) ${\displaystyle$($S_{$$n$})의$$ 생성 함수 $G{\displaystyle (x)}$ ${\displaystyle$$$G(x$)}$은(는$)$

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

사용하다

콤비네이터의 한 가지 주제는 타일링 모양이고, 이것의 한 가지 예는 도미노 기울임이다. 이 예에서 질문은 "도미노($즉{\displaystyle \mathrm{}}$, 1$[\displaystyle 1\time2}$ $또는$ 2${\displaystyle \times 1}$ ${\displaystyle 2\time1}$직사각형$$) 중 어느 것도 겹치지 않고 전체 모양도 코브 모양으로 배열할 수 있다.에레드, 그리고 도미노는 하나도 형체 밖으로 튀어나오지 않소?"슈뢰더 숫자가 연관되어 있는 모양은 아즈텍 다이아몬드다.아래는 도미노 타일링이 가능한 순서 4의 아즈텍 다이아몬드 입니다.

It turns out that the determinant of the ${\displaystyle (2n-1)\times (2n-1)}$ Hankel matrix of the Schröder numbers, that is, the square matrix whose ${\displaystyle (i,j)}$th entry is ${\displaystyle S_{i+j-1},}$ is the number of domino tilings of the order ${\displays$$tyle n}$ 아즈텍$$ 다이아몬드, ${\displaystyle {2n}^{}}$(${\displaystyle {\mathrm{n}}^{}}$+ 1${\displaystyle {}^{}}$)${\displaystyle {}^{}}$/ ${\displaystyle {2\mathrm{}}^{}}$. ${\displaystyle$ 2$^{n(n+1)/2}}}$즉$$^[8],

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

예를 들면 다음과 같다.

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

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

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

참고 항목

• 들라노이 수
• 모츠킨 수
• 나라야나 수
• 슈뢰더-히파르쿠스 수
• 카탈루냐 수

참조

추가 읽기

• Weisstein, Eric W. "Schröder Number". MathWorld.
• 스탠리, 리처드 P.:Enumerative Combinatorics에 대한 Catalan 부록, 2권