C++でエントリンガー数を求める方法

エントリンガー数（Entringer Number）とは、{1, 2, 3, …, n+1} の順列のうち、K+1 で始まり、値が「減少 → 増加」を交互に繰り返すように並べられた順列の個数に等しい特殊な数です。

エントリンガー数は、次の漸化式を用いて求めることができます。

E(n, k) = E(n, k-1) + E(n-1, n-k)

基本値（ベースケース）は以下のとおりです。

E(0, 0) = 1

E(n, 0) = 0

具体例で値を確認してみよう

n = 5、k = 3 の場合を考えてみます。

E(5, 3) = 14 となります。

解法の動作を示すプログラム

例

#include <iostream>
using namespace std;

int EntringerNumber(int n, int k)
{
    if (n == 0 && k == 0)
        return 1;
    if (k == 0)
        return 0;
    return EntringerNumber(n, k - 1) + EntringerNumber(n - 1, n - k);
}

int main() {
    int n = 5, k = 3;
    cout << "E(" << n << ", " << k << ") の値 = " << EntringerNumber(n, k);
    return 0;
}

出力

E(5, 3) の値 = 14

プログラムの解説

このプログラムでは、再帰関数 EntringerNumber() を使って漸化式をそのまま実装しています。引数 n と k がともに 0 の場合は 1 を返し、k が 0 の場合は 0 を返します。それ以外の場合は、漸化式 E(n, k) = E(n, k-1) + E(n-1, n-k) に従って再帰的に計算を進めます。

ただし、この素朴な再帰実装は同じ引数の組み合わせを何度も計算し直すため、n が大きくなると処理時間が急激に増加します。実用的な場面では、メモ化（動的計画法）を組み合わせることで、計算量を大幅に削減できます。