ベル数-C++でセットを分割する方法の数

ベル数 n個の要素のセットを空ではない（つまり、少なくとも1つの要素を持つ）サブセットに分割できる方法の数を示すために使用されます。

このプログラムでは、n個の要素のセットが与えられ、そのセットを空でないサブセットに分割する方法の数を見つける必要があります。

例

Input : 3
Output : 5

説明 −3つの要素のセットを{1、2、3}とします。

サブセットは{{1}、{2}、{3}}です。 {{1}、{2,3}}; {{1、2}、{3}}; {{2}、{1、3}}; {1、2、3}。

ベル数：ベル数bell（n）は、1からnまでのkのすべての値に対する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個のパーティション、つまりs（n、k-1）に1つ追加します。

• パーティションのすべてのセット、つまりk * s（n、k）に付加価値を付けます。

最初のいくつかのベル数は1、1、2、5、15、52、205

ベルの数を見つけるには、いくつかの方法があります。

• 簡単な方法 k =1からnに対してs（n、k）を1つずつ計算し、数値のすべての値の合計を加算します。

• ベルトライアングルの使用 以下に示すようにベルの三角形を使用することです-

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

例

#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;
}