Numeri di Stirling di seconda specie

I numeri di Stirling di seconda specie rispondono a una domanda di conteggio fondamentale nella matematica discreta: dati n oggetti distinti, in quanti modi può particionarli in esattamente k gruppi non vuoti non etichettati? La risposta si scrive S(n,k) o talvolta {n choose k} con parentesi graffe. Questi numeri compaiono ogni volta che raggruppa persone in squadre senza nominare le squadre, divide un insieme di chiavi in secchi non etichettati, conta funzioni suriettive a meno di un fattore fattoriale, costruisce i numeri di Bell come somma su k, o valuta compiti che chiedono partizioni di insiemi piuttosto che permutazioni. Questa capacità accetta interi non negativi n (numero di elementi) e k (numero di sottoinsiemi non vuoti) e restituisce l'S(n,k) esatto come stringa decimale calcolata con programmazione dinamica BigInt, così valori ben oltre i limiti degli interi sicuri ordinari restano corretti cifra per cifra. Gli input con k negativo o con k maggiore di n vengono respinti con un errore di validazione chiaro invece di uno zero silenzioso o una risposta sbagliata.

Come si definiscono i numeri di Stirling di seconda specie

Un numero di Stirling di seconda specie S(n,k) conta le partizioni di un insieme a n elementi in esattamente k sottoinsiemi non vuoti non etichettati. L'ordine dentro un sottoinsieme non conta, e i sottoinsiemi stessi non sono ordinati: la partizione {{1,2},{3}} è la stessa di {{3},{1,2}}. La ricorrenza standard è S(n,k) = k · S(n−1,k) + S(n−1,k−1).

Intuitivamente, quando aggiunge l'elemento più recente n, o forma un singleton da solo (allora i restanti n−1 elementi formano k−1 sottoinsiemi, contati da S(n−1,k−1)), o si unisce a uno dei k sottoinsiemi esistenti in una partizione dei primi n−1 elementi in k blocchi (k scelte, volte S(n−1,k)). I casi base che chiudono la tabella sono S(0,0) = 1, S(n,0) = 0 per n > 0, S(0,k) = 0 per k > 0, S(n,1) = 1 e S(n,n) = 1.

Controlli classici da manuale includono S(3,2) = 3, S(4,2) = 7, S(5,2) = 15 e S(5,3) = 25. Il numero di Bell B_n, totale delle partizioni di un n-insieme con qualsiasi numero di blocchi, è la somma di S(n,k) su k da zero a n. Oggetti correlati ma diversi includono i numeri di Stirling di prima specie (che tracciano permutazioni per conteggio di cicli) e i coefficienti binomiali (che scelgono elementi senza partizionare il resto).

Questa implementazione non usa mai approssimazione in virgola mobile, campionamento Monte Carlo o tabelle esterne: riempie una riga di programmazione dinamica con aritmetica BigInt esatta così ogni cifra è corretta. Il percorso è pienamente deterministico — senza semi casuali, orologi, rete né deriva di modello — così gli stessi n e k producono sempre la stessa stringa.

Dove i conteggi di Stirling di seconda specie compaiono nel lavoro reale

Corsi di combinatoria e contest di programmazione chiedono costantemente in quanti modi dividere n persone etichettate in k squadre non etichettate, quante relazioni di equivalenza su n elementi hanno esattamente k classi, o in quanti modi distribuire n regali distinti in k scatole identiche non vuote — tutto uguale a S(n,k).

I progettisti di algoritmi usano tabelle di Stirling di seconda specie nell'analizzare strutture dati di partizione di insiemi, bozze di clustering con numero fisso di cluster, o nel contare i modi in cui un processo ricorsivo può raggruppare risultati intermedi. Corsi di probabilità e statistica collegano S(n,k) al numero di modi per assegnare n esiti distinti a k secchi non vuoti non etichettati e alla forma chiusa del numero di suriezioni da un n-insieme su un k-insieme, che è k!

· S(n,k). Educatori e preparazione ai colloqui spesso mostrano un breve triangolo di piccoli valori S(n,k); calcolare una sola voce in una chiamata mantiene le demo interattive allineate a manuali e chiavi di risposta senza mantenere a mano grandi tabelle. Se in seguito le servono numeri di Stirling di prima specie, solo numeri di Bell, conteggi di suriezione con il fattore k! già applicato, o un elenco esplicito di partizioni piuttosto che il conteggio, li tratti come intenti di ricerca separati piuttosto che sovraccaricare questa pagina.