घंटी संख्या n तत्वों के एक सेट को उन सबसेट में विभाजित करने के तरीकों की संख्या को निरूपित करने के लिए उपयोग किया जाता है जो खाली नहीं हैं (यानी कम से कम एक तत्व है)।
इस कार्यक्रम में, हमें n तत्वों का एक सेट दिया जाता है और हमें सेट को गैर-रिक्त उपसमुच्चय में विभाजित करने के तरीकों की संख्या ज्ञात करनी होती है।
उदाहरण
Input : 3 Output : 5
स्पष्टीकरण - तीन तत्वों का समुच्चय {1, 2, 3} दें।
उपसमुच्चय {{1} , {2} , {3}} हैं; {{1} , {2,3}}; {{1 , 2} , {3}}; {{2} , {1 , 3}}; {1 , 2 , 3}।
घंटी संख्या:घंटी संख्या घंटी (एन) 1 से n तक के सभी मूल्यों के लिए s(n,k) के योग का मान देती है। यहाँ s(n,k) k उपसमुच्चय में n तत्वों के विभाजन की संख्या है।
सूत्र होगा -
$$घंटी(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;
}