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

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

本文概述

给定一组n个元素, 请找到多种分区方法。

例子：

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)

是将n个元素划分为k个集合的总数。对于k = 1到n, 第n个贝尔号的值是S(n, k)的和。

贝尔（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个分区时, 有两种可能性。

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

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

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

前几个贝尔编号是1、1、2、5、15、52、203, ...。

一种简单方法要计算第n个贝尔数, 则将k = 1到n的计算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)

解释

然后Bell(n, k)计算集合{1, 2​​, …, n + 1}的分区数, 其中元素k +1是该集合中可以单独存在的最大元素。

例如, Bell(3, 2)是3, 它是{1, 2, 3, 4}的分区数的计数, 其中3是最大的单例元素。有三个这样的分区：

{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

上述解决方案的时间复杂度为O(n2)。我们很快将讨论计算贝尔数的其他更有效的方法。

贝尔数字可以解决的另一个问题

.

一个数字是

无平方

如果不能用除1以外的完美平方整除, 例如6是无平方数, 但不能用12除以4。

给定无平方数x, 找到x的不同乘法分区的数量。乘法分区的数量是Bell(n), 其中n是x的素数的数量。例如x = 30, 有3个素数分别为2、3和5。因此答案是Bell(3), 即5。5个分区是1 x 30、2 x15、3 x 10、5 x 6和2 3 x 5

行使：

上面的实现导致n的较大值发生算术溢出。扩展上面的程序, 以便以模1000000007计算结果, 以避免溢出。

参考：

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

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

本文作者：拉杰夫·阿格劳瓦尔(Rajeev Agrawal)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: