बेल नंबर का उपयोग n एलिमेंट्स के एक सेट को उन सबसेट्स में पार्टीशन करने के तरीकों की संख्या को दर्शाने के लिए किया जाता है जो खाली नहीं हैं (यानी कम से कम एक एलिमेंट रखते हैं)।
इस प्रोग्राम में, हमें n एलिमेंट्स का एक सेट दिया गया है और हमें सेट को नॉन-एम्प्टी सबसेट्स में पार्टीशन करने के तरीकों की संख्या ढूंढनी है।
उदाहरण
इनपुट: 3 आउटपुट: 5
व्याख्या - मान लीजिए तीन एलिमेंट्स का सेट {1, 2, 3} है।
सबसेट्स हैं {{1}, {2}, {3}}; {{1}, {2,3}}; {{1, 2}, {3}}; {{2}, {1, 3}}; {1, 2, 3}।
बेल नंबर: एक बेल नंबर bell(n) k के सभी मानों के लिए s(n,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 पार्टीशन्स में जोड़ने पर, दो संभावनाएं हैं:
यह मौजूदा पार्टीशन्स के 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;
} 
