모츠킨 수

수학에서 모츠킨 수(영어: Motzkin number)는 원 위의 주어진 개수의 점들 사이에서 교차하지 않는 현들을 그리는 방법의 가짓수이다. 기하학·조합론·수론에서 다양하게 응용된다.

정의

(0, 0)부터 (4, 0)까지의 경로 가운데, y축 밑으로 떨어지지 않으며 →·↗·↘와 같은 경로만으로 이루어진 경우는 총 9가지이다. 따라서 4번째 모츠킨 수는 9이다.

음이 아닌 정수 $n$에 대하여, $n$번째 모츠킨 수 $M_{n}$은 다음과 같은 조합론 문제들의 답이다.

• $n$개의 공원점의 일부를 잇는 서로 교차하지 않는 현들을 그리는 방법의 수
• 시작점 $(0,0)$, 끝점 $(n,0)$, 보폭 $(1,-1),(1,0),(1,1)$의 $\mathbb {Z} \times \{0,1,2,\dots ,\}$ 속의 격자 경로의 수
• $n$개의 변을 갖는 이진 트리의 수 (단, 하나뿐인 자식 노드의 경우 왼쪽과 오른쪽을 구분하지 않아야 한다)

처음 몇 모츠킨 수는 다음과 같다.

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, ... (OEIS의 수열 A001006)

모츠킨 소수(영어: prime Motzkin numbers)의 열은 다음과 같다.

2, 127, 15511, 953467954114363 (OEIS의 수열 A092832)

성질

점화식

모츠킨 수에 대하여 다음과 같은 점화식이 성립한다.

$M_{n}=M_{n-1}+\sum _{k=0}^{n-2}M_{k}M_{n-k-2}={\frac {2n+1}{n+2}}M_{n-1}+{\frac {3n-3}{n+2}}M_{n-2}$

항등식

모츠킨 수는 바닥 함수 및 이항 계수 및 카탈랑 수를 사용하여 다음과 같이 나타낼 수 있다.

$M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}C_{k}$

생성 함수

모츠킨 수의 생성 함수는 다음과 같다.

$\sum _{n=0}^{n}M_{n}x^{n}={\frac {1-x-{\sqrt {1-2x-3x^{2}}}}{2x^{2}}}={\frac {1}{1-x-{\dfrac {x^{2}}{1-x-{\dfrac {x^{2}}{1-x-{\dfrac {x^{2}}{\ddots }}}}}}}}$

수론적 성질

소인수 $p\geq 5$를 갖는 모츠킨 수의 점근 밀도는 다음과 같은 하계를 갖는다.

${\frac {2}{p(p-1)}}$

예

4개의 공원점을 잇는 교차하지 않는 현을 그리는 방법에는 다음과 같은 9가지가 있다. 따라서 $M_{4}=9$이다.

5개의 공원점을 잇는 교차하지 않는 현을 그리는 방법에는 다음과 같은 21가지가 있다. 따라서 $M_{5}=21$이다.

역사

시어도어 모츠킨(영어: Theodore Motzkin)의 이름을 땄다.

같이 보기

• 격자 경로
• 격자 그래프

참고 문헌

• Donaghey, R.; Shapiro, L. W. (1977). “Motzkin numbers”. 《Journal of Combinatorial Theory》. Series A 23 (3): 291–301. doi:10.1016/0097-3165(77)90020-6. MR 0505544. 

외부 링크

• Weisstein, Eric Wolfgang. “Motzkin number”. 《Wolfram MathWorld》 (영어). Wolfram Research.