Calcolatore dei Numeri di Stirling (Secondo Tipo)

Formula

How this is calculated

Inserisci due interi non negativi: n, il numero di elementi distinti (etichettati), e k, il numero di sottoinsiemi non vuoti in cui vuoi suddividerli. I sottoinsiemi stessi non sono etichettati, quindi conta solo il raggruppamento, non l'ordine dei gruppi.

Il calcolatore usa la classica ricorrenza S(n, k) = k · S(n−1, k) + S(n−1, k−1). Intuitivamente, quando aggiungi l'n-esimo elemento puoi collocarlo in uno dei k sottoinsiemi esistenti (k · S(n−1, k) modi) o iniziare un sottoinsieme nuovo di zecca con esso da solo (S(n−1, k−1) modi). I casi base sono S(0,0) = 1 (un modo per partizionare niente in niente) e S(n,0) = 0 per n > 0, e S(n,k) = 0 ogni volta che k > n. La ricorrenza è valutata con la programmazione dinamica su una singola riga per efficienza.

Il grafico a barre mostra S(n, k) per ogni k da 1 a n, e la loro somma è il numero di Bell B(n), il numero totale di partizioni di un insieme di n elementi. I risultati sono interi esatti; gli input sono limitati a n ≤ 170 così i conteggi restano entro l'intervallo a doppia precisione. Le voci non intere vengono arrotondate all'intero più vicino.