bell数：对集合进行分区的方式数量

2021年3月9日16:12:34 发表评论 479 次浏览

本文概述

``````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} }.``````

S(n, k)

S(n, k)的值可以递归定义为S(n + 1, k)= k * S(n, k)+ S(n, k-1)

1)将其作为单个元素集添加到现有分区, 即S(n, k-1)

2)将其添加到每个分区的所有集合中, 即k * S(n, k)

S(n, k)被称为第二类斯特林数

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

``````// 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)``````

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

C ++

``````// A C++ program to find n'th Bell number
#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++)
{
// 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

``````<?php
// A PHP program to find
// n'th Bell number

// function that returns
// n'th bell number
function bellNumber( \$n )
{

\$bell [0][0] = 1;
for ( \$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 ( \$j = 1; \$j <= \$i ; \$j ++)
\$bell [ \$i ][ \$j ] = \$bell [ \$i - 1][ \$j - 1] +
\$bell [ \$i ][ \$j - 1];
}
return \$bell [ \$n ][0];
}

// Driver Code
for ( \$n = 0; \$n <= 5; \$n ++)
echo ( "Bell Number " . \$n . " is "
. bellNumber( \$n ) . "\n" );

// This code is contributed by Ajit.
?>``````

``````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``````

.

https://en.wikipedia.org/wiki/Bell_number

https://en.wikipedia.org/wiki/Bell_triangle