C++로 구현하는 모츠킨 수(Motzkin Number) – 정의, 점화식, 예제 코드

모츠킨 수(Motzkin Number)란?

모츠킨 수는 조합론에서 다루는 대표적인 수열로, 원 위에 배치한 n개의 점을 서로 교차하지 않는 현(chord)으로 연결하는 방법의 수를 의미합니다. 격자 경로(lattice path)의 개수를 셀 때에도 활용되며, 수학과 컴퓨터 과학 전반에서 자주 등장하는 개념입니다.

모츠킨 수열은 다음과 같이 시작합니다.

M₀ = 1
M₁ = 1
M₂ = 2
M₃ = 4
M₄ = 9
M₅ = 21
M₆ = 51 …

n번째 일반항은 아래 점화식을 통해 구할 수 있습니다.

M_n = ((2n + 1) × M_(n-1) + (3n − 3) × M_(n-2)) ÷ (n + 2)

알고리즘

• 구하고자 하는 항의 번호 n을 초기화합니다.

• 2부터 n까지 반복합니다.

  • 점화식을 적용해 앞선 두 항을 갱신합니다.

• 마지막으로 계산된 값을 반환합니다.

C++ 구현 예제

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int getNthTerm(int n) {
    if(n == 0 || n == 1) {
        return 1;
    }
    int a = 1, b = 1;
    for(int i = 2; i <= n; ++i) {
        int c = ((2 * i + 1) * b + (3 * i - 3) * a) / (i + 2);
        a = b;
        b = c;
    }
    return b;
}
int main() {
    int n = 5;
    cout << getNthTerm(n) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

21

코드 동작 원리

변수 a와 b에는 각각 M_i-2와 M_i-1 값이 저장됩니다. 반복문이 진행될 때마다 점화식으로 새 항 c를 계산한 뒤, 두 변수를 한 칸씩 앞으로 이동시켜 다음 연산에 활용합니다. 이 방식은 배열 없이 상수 개수의 변수만으로 답을 구할 수 있어 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적입니다.