เลขเบล (Bell number) ใช้แทนจำนวนวิธีที่เซตของ n สมาชิกสามารถแบ่งเป็นเซตย่อยที่ไม่ว่างเปล่าได้ (คือมีสมาชิกอย่างน้อยหนึ่งตัว)
ในโปรแกรมนี้ เราได้รับเซตของ n สมาชิก และต้องหาจำนวนวิธีการแบ่งเซตเป็นเซตย่อยที่ไม่ว่างเปล่า
ตัวอย่าง
Input : 3 Output : 5
คำอธิบาย − ให้เซตสามสมาชิก {1, 2, 3}
เซตย่อยคือ {{1} , {2} , {3}} ; {{1} , {2,3}} ; {{1 , 2} , {3}} ; {{2} , {1 , 3}} ; {1 , 2 , 3}
เลขเบล: เลขเบล bell(n) ให้ค่าผลรวมของ s(n,k) สำหรับค่า k ทั้งหมดตั้งแต่ 1 ถึง n ที่นี่ s(n,k) คือจำนวนการแบ่ง n สมาชิกเป็น k เซตย่อย
สูตรจะเป็น −
$$bell(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 เข้าไปใน k การแบ่งของการแบ่งที่มีอยู่ นั่นคือ s(n,k-1)
- เพิ่มค่าเข้าไปในทุกเซตของการแบ่ง นั่นคือ k*s(n,k)
เลขเบลแรกๆ คือ 1 , 1 , 2 ,5 ,15 , 52 , 205
สำหรับการหาเลขเบล เรามีหลายวิธี
วิธีง่าย คือคำนวณ s(n,k) ทีละอันสำหรับ k = 1 ถึง n และบวกผลรวมของค่าทั้งหมด
ใช้สามเหลี่ยมเบล (Bell triangle) คือใช้สามเหลี่ยมเบลดังด้านล่าง −
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52
ตัวอย่าง
#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++) { bell[i][0] = bell[i-1][i-1]; for (int j=1; j<=i; j++) bell[i][j] = bell[i-1][j-1] + bell[i][j-1]; } return bell[n][0]; } int main() { for (int n=0; n<=5; n++) cout<<"Bell Number "<<n<<" is "<< bellNumber(n)<<endl; return 0; }