ベル数とは？C++で集合を空でない部分集合に分割する方法の数を求める

ベル数（Bell number）とは、n個の要素からなる集合を、空でない部分集合（少なくとも1つの要素を含む集合）に分割する方法の総数を表す数です。

本記事では、n個の要素からなる集合が与えられたとき、その集合を空でない部分集合に分割する方法が何通りあるかを求めるプログラムをC++で実装します。

具体例

入力 : 3
出力 : 5

解説 − 3つの要素からなる集合 {1, 2, 3} を考えてみましょう。

分割の仕方は次の5通りあります。

• {{1}, {2}, {3}}
• {{1}, {2, 3}}
• {{1, 2}, {3}}
• {{2}, {1, 3}}
• {{1, 2, 3}}

ベル数の定義と漸化式

ベル数 bell(n) は、k が 1 から n までのすべての値に対する s(n, k) の総和として定義されます。ここで s(n, k) は「n個の要素をk個の部分集合に分割する方法の数」を表します。

数式で表すと次のようになります。

$$bell(n)=\sum_{k=0}^n S(n,k)$$

また、関数 s(n, k) は次の漸化式で再帰的に定義できます。

s(n+1, k) = k × s(n, k) + s(n, k−1)

仕組み

(n+1)番目の要素をk個の分割に追加する場合、次の2通りの可能性があります。

• 既存の k−1 個の分割に新たな分割として1つ追加するケース：s(n, k−1)
• 既存の k 個の分割のいずれかに追加するケース：k × s(n, k)

最初のいくつかのベル数は「1, 1, 2, 5, 15, 52, 205」となります。

ベル数を求める方法

• 単純な方法： k = 1 から n まで順に s(n, k) を計算し、その総和を求めます。
• ベル三角形を使う方法： 次のようなベルの三角形を利用して効率的に計算します。

1
1   2
2   3   5
5   7   10  15
15  20  27  37  52

ベル三角形では、各行の先頭の値は前の行の最後の値と一致し、それ以降の値は「左隣の値」と「左上の値」の和になります。三角形の左端の列を上から読むと、それがそのままベル数の列になります。

C++による実装例

#include<iostream>
using namespace std;
int bellNumber(int n) {
    int bell[n+1][n+1];
    bell[0][0] = 1;
    for (int i=1; i<=n; i++) {
        bell[i][0] = bell[i-1][i-1];
        for (int j=1; j<=i; j++)
            bell[i][j] = bell[i-1][j-1] + bell[i][j-1];
    }
    return bell[n][0];
}
int main() {
    for (int n=0; n<=5; n++)
        cout<<"Bell Number "<<n<<" is "<< bellNumber(n)<<endl;
    return 0;
}

このプログラムを実行すると、n = 0 から 5 までのベル数が出力され、「1, 1, 2, 5, 15, 52」が得られます。ベル三角形を二次元配列で構築することで、動的計画法により効率的にベル数を求められる点がポイントです。