একটি বেল নাম্বার n এলিমেন্টের একটি সেটকে কতভাবে নন-এমপটি সাবসেটে পার্টিশন করা যায় সেটি ডিনোট করে (অর্থাৎ কমপক্ষে এক এলিমেন্ট থাকবে)।
এই প্রোগ্রামে, n এলিমেন্টের একটি সেট দেওয়া আছে এবং আমাদের সেটকে নন-এমপটি সাবসেটে পার্টিশন করার পথের সংখ্যা বের করতে হবে।
উদাহরণ
ইনপুট: 3 আউটপুট: 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 ১ থেকে 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)th এলিমেন্ট k পার্টিশনে যোগ করার সময় দুটি সম্ভাবনা থাকে −
- এটি এক্সিস্টিং পার্টিশনের একটি সেটে যোগ হয় অর্থাৎ s(n,k-1)।
- পার্টিশনের সব সেটে ভ্যালু যোগ করা অর্থাৎ k*s(n,k)।
প্রথম কয়েকটি বেল নাম্বার: 1, 1, 2, 5, 15, 52, 205
বেল নাম্বার বের করার কয়েকটি মেথড রয়েছে,
- সিম্পল মেথড হলো এক এক করে s(n,k) k=1 থেকে n পর্যন্ত কম্পিউট করে সব ভ্যালুর সম যোগ করা।
- বেল ট্রায়্যাঙ্গেল ব্যবহার করে হলো নিচের বেল ট্রায়্যাঙ্গেল ব্যবহার করা:
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;
}
