bell_numbers_list — Sequences

Returns the Bell numbers of order 0 to n.

Interface

#include <codecogs/maths/combinatorics/sequences/bell_numbers_list.h>

using namespace Maths::Combinatorics::Sequences;

std::vector<int> bell_numbers_list(int n)

The Bell number $B(n)$ is defined as the number of partitions (of any size) of a set into n distinguishable objects.

It is also the number of restricted growth functions on $n$. Note that the Stirling numbers of the second kind, $S^m_n$, count the number of partitions of n objects into m classes, and so it is true that

$$B(n) = \sum_{i = 1}^n S^i_n$$

(1)

For example, there are 15 partitions of a set of 4 objects:

$$\begin{array}{ccccc} (1234) & (123)(4) & (124)(3) & (12)(34) & (12)(3)(4) \cr (134)(2) & (13)(24) & (13)(2)(4) & (14)(23) & (1)(234) \cr (1)(23)(4) & (14)(2)(3) & (1)(24)(3) & (1)(2)(34) & (1)(2)(3)(4) \end{array}$$

(2)

and so $B(4) = 15$. The recurrence relation used with this function to calculate the Bell number of order i is as follows:

$$B(i) = \sum_{1 \leq j \leq i} \left( \begin{array}{c} i - 1 \cr j-1 \end{array} \right) \cdot B(i - j)$$

(3)

where i takes values from 0 to n.

References

SUBSET, a C++ library of combinatorial routines, http://www.csit.fsu.edu/~burkardt/cpp_src/subset/subset.html

Example 1

#include <codecogs/maths/combinatorics/sequences/bell_numbers_list.h>
#include <iostream>

int main() {
  std::vector<int> result = Maths::Combinatorics::Sequences::bell_numbers_list(5);
  std::cout << "Number of values: " << result.size() << std::endl;
  for (int i = 0; i < result.size(); i++)
    std::cout << result[i] << "  ";
  std::cout << std::endl;

  return 0;
}

Output

Number of values: 6
1  1  2  5  15  52

Parameters

the maximum value of the index in the generated Bell sequence

Returns

the Bell numbers of order 0 to n