모츠킨 수열(Motzkin sequence)

모츠킨 수열(Motzkin sequence)

 

0. 서론

카탈란 수열과 비슷하지만 또 재밌는 수열이 한가지 있습니다. 바로 모츠킨 수열(Motzkin numbers)인데요

오늘은 이 모츠킨 수열을 한번 살펴보도록 하겠습니다.

카탈란 수열에 +a한 수열이므로, 사실 카탈란 수열(https://omnil.tistory.com/221)시리즈를 전부 읽고 오시는 걸 추천드립니다.

 

 

1. 모츠킨 수열이란?

조합론에서 등장하는 아름다운 수열 중 하나가 모츠킨 수열(Motzkin numbers)입니다. 이 수열은 특정한 경로를 세는 문제나 괄호 구조, 평면 그래프의 엣지 수와도 관련이 있어, 카탈란 수열과 함께 종종 등장합니다.

카탈란 수열과 마찬가지로 테오도르 모츠킨(Theodore Motzkin)이 1948년 체계화해 발표한 것을 계기로 명명된 수열입니다.

 

 

2. 정의

모츠킨 수열 $M_n$은

1) 제일 간단하게 카탈란 수열(https://omnil.tistory.com/221)의 Dyck path에서 우상향(↗), 우하향(↘) 외에 평행이동(→)이 추가된 수열입니다.

2) 다음 조건을 만족하는 경로의 수로 정의됩니다:

시작점 $(0,0)$에서 시작하여 $(n,0)$에서 끝나는 경로 중,

1. 한 번에 $(1,1)$ (↗), $(1,0)$ (→), $(1,-1)$ (↘) 이동 가능하고
2. 절대 음의 높이(음수 y좌표)를 가지지 않는 경로의 개수.

즉, 위로 올라가거나 수평으로 가거나 내려가되, 절대로 수평선((0,0)~(n,0)) 아래로 내려가지 않는 경로의 개수를 셉니다.

 

 

3. 예시

$ M_0 = 1, \ M_1 = 1, \ M_2 = 2, \ M_3 = 4, \ M_4 = 9, \ M_5 = 21, \ M_6 = 51, \ \cdots $

카탈란 수보다 증가속도가 느리다고 생각할수도 있지만, 사실은 경우의 수가 한가지 더 늘어나서 더 빠르게 증가합니다.

그러나 항 수로 보면 느리게 증가하게 보이는 이유는, 카탈란 수와는 다르게 조건이 홀수개 이므로 수열 자체가 $ n \rightarrow 2n $으로 정의되던 카탈란 수열과 다르게 $ n \rightarrow n $으로 정의되기 때문입니다.

실제로 짝수항만 놓고보면 카탈란 수열보다 더 빠르게 증가함을 알 수 있습니다.

 

 

4. 점화식

모츠킨 수열을 다음과 같은 점화식을 만족합니다.

$ M_0 = 1, \ M_1 = 1, \ M_n = M_{n-1} + \sum \limits _{k=0} ^{n-2} M_kM_{n-2-k} \quad \operatorname{for} \ n \ge 2$

1) 첫 시작이 수평(→)이라면, 단순히 경로가 하나 줄어든 것이므로 $ M_{n-1} $ 값을 가집니다.

2) 첫 시작이 수평(→)이 아니라면, 무조건 우상향(↗)으로 시작해야하며, 이것은 카탈란 수의 점화식과 동일한 모양을 갖습니다.

단, 카탈란 수열은 무조건 총 경로가 짝수개여야만 하므로 점화식에서 -1만 빼 주어도 1쌍(시작:우상향, 끝:우하향)이 빠지는 결과가 나오지만, 모츠킨 수열은 총 경로가 홀수개여도 되므로, 점화식에서 -2(시작:우상향, 끝:우하향)를 빼주어야 합니다.

 

 

5. 생성함수

점화식을 알고있으니, 생성함수도 구할 수 있습니다.

카탈란 수열과 비슷하게 생성함수를 구해보면

$ M(x) = \sum \limits _{n=0} ^\infty M_n x^n = \frac{1-x-\sqrt{1-2x-3x^2}}{2x^2} $

으로 구해집니다만.. 카탈란 수보다 근호 안쪽이 한 차수 늘어난 걸 보면, 생성함수로 일반항 찾기는 아주 쉽지 않아보입니다.

일단 생성함수도 구할 수 있다 정도로만 생각하시고 넘어가시죠

사실 모츠킨수열은 조합론적 수열이다보니 경우의 수로 일반항 구하는게 더 쉽습니다.(카탈란 수열에서도 경우의 수로 구하는게 훨씬 쉬웠죠?)

 

 

6. 일반항

모츠킨 수열의 일반항은

$ M_n = \sum \limits_{k=0}^{[n/2]} \ _{n}\operatorname{C}_{2k} \ C_k$

여기서 왼쪽 C는 조합이고, 오른쪽 C는 카탈란 수 인데, 헛갈리니까 binomial 표현으로 바꿔주면

$ M_n = \sum \limits_{k=0}^{[n/2]} \binom{n}{2k} \ C_k$

이 됩니다.

여기서  
- $ \binom{n}{2k} $는 전체 n칸 중에 길이 2k짜리 구간을 선택하는 방법의 수를 나타내며,  
- $ C_k $는 카탈란 수로, 길이 2k인 Dyck path의 개수를 의미합니다.



이 식을 조합적으로 해석하면 다음과 같습니다.

1. 전체 경로의 길이는 n입니다.  
   우리는 이 길이를 Dyck path 구간(길이 2씩 짝을 이루는 구간)과 수평선(→)으로 나눠 생각합니다.

2. 짝수 영역 선택하기:  
   Dyck path는 길이가 항상 짝수여야 하므로, 2k ≤ n인 k에 대해서만 고려할 수 있습니다.  
   즉, 가능한 k의 범위는 0 ≤ k ≤ [n/2]입니다.(여기서 대괄호는 '가우스 기호'혹은 '가우스 함수'라고 불리며, '기호 안의 값을 넘지 않는 최대 정수'를 의미합니다. 내림(floor)과 동일합니다. 즉, [2.5] = 2입니다.)[여기서 이 기호는 짝수 2k가 전체 길이 n을 넘지 않게 제한하는 역할을 합니다.]

3. $ \binom{n}{2k} $는 길이 n 중에서 길이 2k짜리 블록이 들어가는 위치를 고르는 방법입니다.

4. $ C_k $는 선택된 2k칸에 대해 Dyck path를 구성하는 방법의 수입니다.

5. 남은 n - 2k칸은 모두 수평선(→)으로 채우면 됩니다.

즉,  
- 각 k마다  
  $ \binom{n}{2k} $: Dyck path가 들어갈 위치 조합 ×  
  $ C_k $: 그 위치에 Dyck path를 실제로 배치하는 방법  
을 곱해서 전체 경로의 수를 계산하는 것입니다.

 

예를 들어 n = 3이라면,  
가능한 k는 0 또는 1입니다.

- k = 0: 전부 수평선(→) → 1가지  
- k = 1:  
  $ \binom{3}{2} $ = 3 (길이 2짜리 블록 하나를 어디 넣을지 선택) ×  
  C₁ = 1  
  → 총 3가지

따라서,

$ M_3 = \binom{3}{0}·C_0 + \binom{3}{2}·C_1 = 1·1 + 3·1 = 4 $

 

다시 정리해보자면

$ M_n = \sum \limits_{k=0}^{[n/2]} \binom{n}{2k} \ C_k$

- k는 Dyck path로 채울 수 있는 짝수 영역의 개수  
- binom(n, 2k)는 그 위치를 고르는 조합  
- $ C_k $는 그 영역에 실제 Dyck path를 채우는 방법의 수

라는 조합적 해석을 갖습니다.

 

여기서 카탈란 수열 $ C_k $는 $ \frac{1}{k+1}\binom{2k}{k} $이므로 전체 풀어쓰면

$ M_n = \sum \limits_{k=0}^{[n/2]} \binom{n}{2k} \cdot \frac{1}{k+1}\binom{2k}{k}$

 

결국, 카탈란 수열을 나눠서 얘들이 어디에 쏙쏙 배치될지만 결정하는게 모츠킨 수열이네요~

 

 

7. 결론

모츠킨 수열의 점화식: $ M_0 = 1, \ M_1 = 1, \ M_n = M_{n-1} + \sum \limits _{k=0} ^{n-2} M_kM_{n-2-k} \quad \operatorname{for} \ n \ge 2$

모츠킨 수열의 일반항: $ M_n = \sum \limits_{k=0}^{[n/2]} \binom{n}{2k} \cdot \frac{1}{k+1}\binom{2k}{k}$

카탈란 수열을 심도있게 공부해봤다면, 너무나도 쉽게 카탈란 수가 들어갈 공간만 계산해주면 바로 모츠킨 수열의 일반항이 나온다는 사실을 알 수가 있답니다~