Số Bell dùng để biểu thị số cách một tập hợp n phần tử có thể được phân hoạch thành các tập con không rỗng (tức là có ít nhất một phần tử).
Trong chương trình này, cho một tập hợp n phần tử, ta phải tìm số cách phân hoạch tập hợp thành các tập con không rỗng.
Ví dụ
Input: 3 Output: 5
Giải thích − Giả sử tập ba phần tử {1, 2, 3}.
Các tập con là {{1}, {2}, {3}}; {{1}, {2,3}}; {{1,2}, {3}}; {{2}, {1,3}}; {1,2,3}.
Số Bell: Số Bell bell(n) cho giá trị tổng của s(n,k) với mọi k từ 1 đến n. Ở đây s(n,k) là số phân hoạch n phần tử thành k tập con.
Công thức:
$$bell(n)=\sum_{k=0}^n S(n,k)$$
Hàm s(n,k) được định nghĩa đệ quy:
s(n+1,k) = k*s(n,k) + s(n,k-1).
Cơ chế
Khi thêm phần tử (n+1) vào k phân hoạch, có hai khả năng:
- Nó thêm một vào k phân hoạch của các phân hoạch hiện có, tức là s(n,k-1).
- Thêm giá trị vào tất cả các tập của phân hoạch, tức là k*s(n,k).
Một vài số Bell đầu tiên: 1, 1, 2, 5, 15, 52, 205
Để tìm số Bell, có một vài phương pháp:
- Phương pháp đơn giản là lần lượt tính s(n,k) cho k = 1 đến n và cộng tổng tất cả giá trị.
- Sử dụng tam giác Bell là dùng tam giác Bell như sau:
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52
Ví dụ
#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<<"Số Bell "<<n<<" là "<<bellNumber(n)<<endl;
return 0;
}