Calculator Numerele Stirling (Tipul al Doilea)

Formulă

How this is calculated

Introduceți două numere întregi nenegative: n, numărul de elemente distincte (etichetate), și k, numărul de submulțimi nevide în care doriți să le împărțiți. Submulțimile în sine sunt neetichetate, deci contează numai gruparea, nu ordinea grupurilor.

Calculatorul folosește recurența clasică S(n, k) = k · S(n−1, k) + S(n−1, k−1). Intuitiv, când adăugați al n-lea element, fie îl plasați într-una din cele k submulțimi existente (k · S(n−1, k) moduri), fie îl plasați singur într-o submulțime complet nouă (S(n−1, k−1) moduri). Cazurile de bază sunt S(0,0) = 1 (un singur mod de a partiționa nimic în nimic) și S(n,0) = 0 pentru n > 0, și S(n,k) = 0 ori de câte ori k > n. Recurența este evaluată cu programare dinamică pe un singur rând pentru eficiență.

Diagrama cu bare arată S(n, k) pentru fiecare k de la 1 la n, iar suma lor este numărul Bell B(n), numărul total de partiții ale unei mulțimi cu n elemente. Rezultatele sunt numere întregi exacte; intrările sunt limitate la n ≤ 170 astfel încât numărătorile să rămână în intervalul de precizie dublă. Valorile non-întregi sunt rotunjite la cel mai apropiat număr întreg.