C++でオイラー数を求める：再帰による実装と解説

オイラー数とは

数学においてオイラー数（Eulerian number）は、特殊な組合せ数の一種です。1からnまでの数を並べた順列のうち、「隣接する2つの要素を比較したとき、前の要素より後の要素が大きくなる箇所（昇順）がちょうどm個ある」ような順列の個数を表します。

オイラー数は一般に A(n, m) と表記されます。

問題の定義

この問題では、2つの整数 n と m が与えられます。求めたいのは、条件を満たす順列の個数、すなわちオイラー数 A(n, m) の値です。

例で問題を理解しよう

入力： n = 4、m = 2

出力： 11

解説：

1から4までの数の順列は、全部で以下の24通りあります。

1 2 3 4　1 2 4 3　1 3 2 4　1 3 4 2　1 4 2 3　1 4 3 2
2 1 3 4　2 1 4 3　2 3 1 4　2 3 4 1　2 4 1 3　2 4 3 1
3 1 2 4　3 1 4 2　3 2 1 4　3 2 4 1　3 4 1 2　3 4 2 1
4 1 2 3　4 1 3 2　4 2 1 3　4 2 3 1　4 3 1 2　4 3 2 1

これらのうち、昇順がちょうどm（= 2）個になる順列は11個存在します。

解法のアプローチ

順列をすべて列挙して数える代わりに、オイラー数には以下の漸化式が成り立つことを利用します。

A(n, m) = 0　（m ≥ n または n = 0 のとき）
A(n, m) = 1　（m = 0 のとき）
A(n, m) = (n − m) × A(n−1, m−1) + (m + 1) × A(n−1, m)　（上記以外のとき）

この漸化式をそのまま再帰関数として実装すれば、すべての順列を列挙することなくオイラー数を求めることができます。

解法の実装例（C++）

サンプルコード

#include <iostream>
using namespace std;

int countEulerianNumber(int n, int m)
{
    if (m >= n || n == 0)
        return 0;
    if (m == 0)
        return 1;
    return (((n - m) * countEulerianNumber(n - 1, m - 1)) + ((m + 1) * countEulerianNumber(n - 1, m)));
}

int main() {

    int n = 5, m = 3;
    cout << "オイラー順列の個数は " << countEulerianNumber(n, m) << " です";
    return 0;
}

実行結果

オイラー順列の個数は 26 です

まとめ

オイラー数 A(n, m) は、昇順の個数によって順列を分類する重要な組合せ数です。漸化式を用いた再帰実装により、効率よく答えを求められます。ただし、素朴な再帰は同じ計算を繰り返すため、n が大きい場合はメモ化（動的計画法）を組み合わせると、さらに計算量を抑えることができます。