C++でモツキン数の第n項を計算する方法

モツキン数とは

モツキン数（Motzkin number）は、組合せ論で登場する有名な整数列の一つで、1, 1, 4, 9, 21, 51, ... と続きます。円周上に並べた n 個の点の間に互いに交差しない弦を引く方法の総数など、さまざまな組合せの問題を表すことで知られています。

モツキン数の一般項は、直前の2項を用いた次の漸化式によって求められます。

a₀ = 1

a₁ = 1

a₂ = 4

a₃ = 9

a_n = ((2n + 1) / (n + 2)) × M_(n−1) + ((3n − 3) / (n + 2)) × M_(n−2)

アルゴリズム

• 求めたい項の番号 n を初期化します。

• n まで繰り返し処理を行います。

  • 直前の2つの項の値を順次更新していきます。

• 最後に計算された項の値を返します。

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

このプログラムでは n = 5 のときのモツキン数を計算しており、結果として 21 が出力されます。計算量は O(n) と非常に効率的で、大きな n に対しても高速に動作します。ただし、項の値は急激に大きくなるため、大きな n を扱う場合は long long 型などの使用を検討してください。