bell numbers list

Returns the Bell numbers of order 0 to n.

Controller: CodeCogs

Contents

Interface
Bell Numbers List
Page Comments

Dependents

Interface

C++

Bell Numbers List

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

The Bell number $\inline 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 $\inline n$ . Note that the Stirling numbers of the second kind, $\inline 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$

(2)

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}$

(3)

and so $\inline 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)$

(4)

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

n	the maximum value of the index in the generated Bell sequence

Returns

the Bell numbers of order 0 to n

Authors

Lucian Bentea (August 2005)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.