모츠킨 수(Motzkin number)는 수학, 특히 조합론에서 다루어지는 정수 수열이다. n번째 모츠킨 수 M_n은 원 위에 놓인 n개의 점 사이에서 서로 교차하지 않는 현(chord)들을 그리는 방법의 총 가짓수로 정의된다. 이때 모든 점이 반드시 현으로 연결될 필요는 없다는 점이 특징이다.
정의
모츠킨 수는 다음과 같은 여러 조합론적 문제의 답과 동치이다.
- n개의 점을 원 위에 배치하고, 일부 점들을 서로 교차하지 않는 현으로 연결하는 방법의 수
- 좌표평면에서 (0, 0)에서 시작하여 (n, 0)에서 끝나며, 각 단계에서 (1, −1), (1, 0), (1, 1)의 보폭만 사용하고 y축 값이 0보다 아래로 내려가지 않는 격자 경로의 수
- n개의 변을 갖는 이진 트리의 수 (단, 자식이 하나뿐인 노드의 경우 왼쪽과 오른쪽을 구분하지 않음)
수열의 값
처음 몇 개의 모츠킨 수는 다음과 같다.
1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, ...
이 수열은 OEIS(온라인 정수열 사전)의 A001006으로 등재되어 있다.
점화식
모츠킨 수는 다음과 같은 점화식을 만족한다.
M_n = M_(n−1) + Σ_(k=0)^(n−2) M_k · M_(n−k−2)
또한 다음의 형태로도 표현된다.
M_n = ((2n+1)/(n+2))·M_(n−1) + ((3n−3)/(n+2))·M_(n−2)
생성 함수
모츠킨 수의 생성 함수는 다음과 같다.
Σ M_n·x^n = (1 − x − √(1 − 2x − 3x²)) / (2x²)
이항 계수와의 관계
모츠킨 수는 카탈란 수 C_k와 이항 계수를 이용하여 다음과 같이 표현할 수 있다.
M_n = Σ_(k=0)^(⌊n/2⌋) C(n, 2k)·C_k
명칭의 유래
모츠킨 수는 미국의 수학자 시어도어 모츠킨(Theodore Motzkin)의 이름에서 유래하였다. 모츠킨은 1948년에 이 수열을 처음 연구한 것으로 알려져 있다.
응용
모츠킨 수는 기하학, 조합론, 수론 등 다양한 분야에서 응용된다. 특히 RNA 분자의 2차 구조를 세는 문제, 평면 그래프, 괄호 구조의 개수, 격자 경로 세기 등에서 등장한다. Donaghey와 Shapiro(1977)는 모츠킨 수가 나타나는 14가지 서로 다른 조합적 대상들을 제시한 바 있다.
참고 문헌
- Donaghey, R.; Shapiro, L. W. (1977). "Motzkin numbers". Journal of Combinatorial Theory, Series A 23 (3): 291–301.
- Weisstein, Eric Wolfgang. "Motzkin Number." Wolfram MathWorld.
