Υπολογιστής Αριθμών Stirling (Δεύτερου Είδους)

Τύπος

How this is calculated

Εισαγάγετε δύο μη αρνητικούς ακέραιους: το n, το πλήθος των διακριτών (επισημασμένων) αντικειμένων, και το k, το πλήθος των μη κενών υποσυνόλων στα οποία θέλετε να τα χωρίσετε. Τα ίδια τα υποσύνολα είναι μη επισημασμένα, οπότε μόνο η ομαδοποίηση έχει σημασία, όχι η σειρά των ομάδων.

Ο υπολογιστής χρησιμοποιεί την κλασική αναδρομή S(n, k) = k · S(n−1, k) + S(n−1, k−1). Διαισθητικά, όταν προσθέτετε το n-οστό αντικείμενο είτε το τοποθετείτε σε ένα από τα k υπάρχοντα υποσύνολα (k · S(n−1, k) τρόποι) είτε ξεκινάτε ένα ολοκαίνουργιο υποσύνολο με αυτό μόνο του (S(n−1, k−1) τρόποι). Οι βασικές περιπτώσεις είναι S(0,0) = 1 (ένας τρόπος να διαμερίσεις το τίποτα σε τίποτα) και S(n,0) = 0 για n > 0, και S(n,k) = 0 όποτε k > n. Η αναδρομή αξιολογείται με δυναμικό προγραμματισμό σε μια μόνο γραμμή για αποδοτικότητα.

Το ραβδόγραμμα δείχνει το S(n, k) για κάθε k από 1 έως n, και το άθροισμά τους είναι ο αριθμός Bell B(n), το συνολικό πλήθος των διαμερίσεων ενός συνόλου n στοιχείων. Τα αποτελέσματα είναι ακριβείς ακέραιοι· οι είσοδοι περιορίζονται σε n ≤ 170 ώστε τα πλήθη να παραμένουν εντός του εύρους διπλής ακρίβειας. Μη ακέραιες καταχωρίσεις στρογγυλοποιούνται στον πλησιέστερο ακέραιο.