একটি বেল নম্বর n উপাদানগুলির একটি সেটকে কতগুলি উপায়ে উপসেটগুলিতে ভাগ করা যায় যেগুলি খালি নয় (অর্থাৎ কমপক্ষে একটি উপাদান রয়েছে) তা বোঝাতে ব্যবহৃত হয়৷
এই প্রোগ্রামে, আমাদেরকে n উপাদানগুলির একটি সেট দেওয়া হয়েছে এবং আমাদের সেটটিকে অ-খালি উপসেটে ভাগ করার উপায় খুঁজে বের করতে হবে৷
উদাহরণ
Input : 3 Output : 5
ব্যাখ্যা − তিনটি উপাদানের সেট করা যাক {1, 2, 3}।
উপসেটগুলি হল {{1} , {2} , {3}}; {{1} , {2,3}}; {{1, 2}, {3}}; {{2} , {1 , 3}}; {1 , 2 , 3}৷
৷বেল নম্বর:একটি বেল নম্বর বেল(n) 1 থেকে n পর্যন্ত k-এর সমস্ত মানের জন্য s(n,k) এর যোগফলের মান দেয়। এখানে s(n,k) হল k উপসেটে n উপাদানের পার্টিশনের সংখ্যা।
সূত্রটি হবে −
$$bell(n)=\sum_{k=0}^n S(n,k)$$
ফাংশন s(n,k) পুনরাবৃত্তিমূলকভাবে −
হিসাবেs(n+1,k) =k*s(n,k) + s(n,k-1)।
কাজ করছে
k পার্টিশনে (n+1)তম উপাদান যোগ করার সময়, দুটি সম্ভাবনা রয়েছে -
-
এটি বিদ্যমান পার্টিশনের k পার্টিশনে একটি যোগ করে যেমন s(n,k-1)।
-
পার্টিশনের সমস্ত সেটে মান যোগ করা হচ্ছে, যেমন k*s(n,k).
প্রথম কয়েকটি বেল নম্বর হল 1, 1, 2,5,15, 52, 205
বেল নম্বর খোঁজার জন্য, আমাদের কাছে কয়েকটি পদ্ধতি আছে,
-
সহজ পদ্ধতি k =1 থেকে n এর জন্য একে একে s(n,k) গণনা করুন এবং সংখ্যার সমস্ত মানের যোগফল যোগ করুন।
-
বেল ত্রিভুজ ব্যবহার করে নীচে দেওয়া হিসাবে বেলের ত্রিভুজ ব্যবহার করতে হয় −
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;
} 