# Bell Numbers (Number of ways to Partition a Set)

Given a set of n elements, find number of ways of partitioning it.
Examples:

```Input:  n = 2
Output: Number of ways = 2
Explanation: Let the set be {1, 2}
{ {1}, {2} }
{ {1, 2} }

Input:  n = 3
Output: Number of ways = 5
Explanation: Let the set be {1, 2, 3}
{ {1}, {2}, {3} }
{ {1}, {2, 3} }
{ {2}, {1, 3} }
{ {3}, {1, 2} }
{ {1, 2, 3} }.
```

Solution to above questions is Bell Number.

What is a Bell Number?
Let S(n, k) be total number of partitions of n elements into k sets. The value of n’th Bell Number is sum of S(n, k) for k = 1 to n.

Value of S(n, k) can be defined recursively as, S(n+1, k) = k*S(n, k) + S(n, k-1)

How does above recursive formula work?
When we add a (n+1)’th element to k partitions, there are two possibilities.
1) It is added as a single element set to existing partitions, i.e, S(n, k-1)
2) It is added to all sets of every partition, i.e., k*S(n, k)

S(n, k) is called Stirling numbers of the second kind

First few Bell numbers are 1, 1, 2, 5, 15, 52, 203, ….

A Simple Method to compute n’th Bell Number is to one by one compute S(n, k) for k = 1 to n and return sum of all computed values. Refer this for computation of S(n, k).

A Better Method is to use Bell Triangle. Below is a sample Bell Triangle for first few Bell Numbers.

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

The triangle is constructed using below formula.

```// If this is first column of current row 'i'
If j == 0
// Then copy last entry of previous row
// Note that i'th row has i entries
Bell(i, j) = Bell(i-1, i-1)

// If this is not first column of current row
Else
// Then this element is sum of previous element
// in current row and the element just above the
// previous element
Bell(i, j) = Bell(i-1, j-1) + Bell(i, j-1)
```

Interpretation
Then Bell(n, k) counts the number of partitions of the set {1, 2, …, n + 1} in which the element k + 1 is the largest element that can be alone in its set.

For example, Bell(3, 2) is 3, it is count of number of partitions of {1, 2, 3, 4} in which 3 is the largest singleton element. There are three such partitions:

```    {1}, {2, 4}, {3}
{1, 4}, {2}, {3}
{1, 2, 4}, {3}. ```

Below is Dynamic Programming based implementation of above recursive formula.

## C++

 `// A C++ program to find n'th Bell number ` `#include ` `using` `namespace` `std; ` ` `  `int` `bellNumber(``int` `n) ` `{ ` `   ``int` `bell[n+1][n+1]; ` `   ``bell[0][0] = 1; ` `   ``for` `(``int` `i=1; i<=n; i++) ` `   ``{ ` `      ``// Explicitly fill for j = 0 ` `      ``bell[i][0] = bell[i-1][i-1]; ` ` `  `      ``// Fill for remaining values of j ` `      ``for` `(``int` `j=1; j<=i; j++) ` `         ``bell[i][j] = bell[i-1][j-1] + bell[i][j-1]; ` `   ``} ` `   ``return` `bell[n][0]; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `   ``for` `(``int` `n=0; n<=5; n++) ` `      ``cout << ``"Bell Number "` `<< n << ``" is "`  `           ``<< bellNumber(n) << endl; ` `   ``return` `0; ` `} `

## Java

 `// Java program to find n'th Bell number ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `    ``// Function to find n'th Bell Number ` `    ``static` `int` `bellNumber(``int` `n) ` `    ``{ ` `        ``int``[][] bell = ``new` `int``[n+``1``][n+``1``]; ` `        ``bell[``0``][``0``] = ``1``; ` `         `  `        ``for` `(``int` `i=``1``; i<=n; i++) ` `        ``{ ` `            ``// Explicitly fill for j = 0 ` `            ``bell[i][``0``] = bell[i-``1``][i-``1``]; ` `  `  `            ``// Fill for remaining values of j ` `            ``for` `(``int` `j=``1``; j<=i; j++) ` `                ``bell[i][j] = bell[i-``1``][j-``1``] + bell[i][j-``1``]; ` `        ``} ` `         `  `        ``return` `bell[n][``0``]; ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``for` `(``int` `n=``0``; n<=``5``; n++) ` `            ``System.out.println(``"Bell Number "``+ n + ` `                            ``" is "``+bellNumber(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by Pramod Kumar `

## Python3

 `# A Python program to find n'th Bell number ` ` `  `def` `bellNumber(n): ` ` `  `    ``bell ``=` `[[``0` `for` `i ``in` `range``(n``+``1``)] ``for` `j ``in` `range``(n``+``1``)] ` `    ``bell[``0``][``0``] ``=` `1` `    ``for` `i ``in` `range``(``1``, n``+``1``): ` ` `  `        ``# Explicitly fill for j = 0 ` `        ``bell[i][``0``] ``=` `bell[i``-``1``][i``-``1``] ` ` `  `        ``# Fill for remaining values of j ` `        ``for` `j ``in` `range``(``1``, i``+``1``): ` `            ``bell[i][j] ``=` `bell[i``-``1``][j``-``1``] ``+` `bell[i][j``-``1``] ` ` `  `    ``return` `bell[n][``0``] ` ` `  `# Driver program ` `for` `n ``in` `range``(``6``): ` `    ``print``(``'Bell Number'``, n, ``'is'``, bellNumber(n)) ` ` `  `# This code is contributed by Soumen Ghosh `

## C#

 `// C# program to find n'th Bell number ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Function to find n'th  ` `    ``// Bell Number ` `    ``static` `int` `bellNumber(``int` `n) ` `    ``{ ` `        ``int``[,] bell = ``new` `int``[n + 1,  ` `                              ``n + 1]; ` `        ``bell[0, 0] = 1; ` `         `  `        ``for` `(``int` `i = 1; i <= n; i++) ` `        ``{ ` `             `  `            ``// Explicitly fill for j = 0 ` `            ``bell[i, 0] = bell[i - 1, i - 1]; ` ` `  `            ``// Fill for remaining values of j ` `            ``for` `(``int` `j = 1; j <= i; j++) ` `                ``bell[i, j] = bell[i - 1, j - 1] +  ` `                             ``bell[i, j - 1]; ` `        ``} ` `         `  `        ``return` `bell[n, 0]; ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``for` `(``int` `n = 0; n <= 5; n++) ` `            ``Console.WriteLine(``"Bell Number "``+ n + ` `                              ``" is "``+bellNumber(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

## PHP

 ` `

Output:

```Bell Number 0 is 1
Bell Number 1 is 1
Bell Number 2 is 2
Bell Number 3 is 5
Bell Number 4 is 15
Bell Number 5 is 52```

Time Complexity of above solution is O(n2). We will soon be discussing other more efficient methods of computing Bell Numbers.

Another problem that can be solved by Bell Numbers.
A number is squarefree if it is not divisible by a perfect square other than 1. For example, 6 is a square free number but 12 is not as it is divisible by 4.
Given a squarefree number x, find the number of different multiplicative partitions of x. The number of multiplicative partitions is Bell(n) where n is number of prime factors of x. For example x = 30, there are 3 prime factors of 2, 3 and 5. So the answer is Bell(3) which is 5. The 5 partitions are 1 x 30, 2 x15, 3 x 10, 5 x 6 and 2 x 3 x 5.

Exercise:
The above implementation causes arithmetic overflow for slightly larger values of n. Extend the above program so that results are computed under modulo 1000000007 to avoid overflows.