Calcolatore di partizioni intere

La funzione di partizione intera p(n) risponde a una domanda classica di conteggio: in quanti modi si può scrivere un intero non negativo n come somma di interi positivi quando l'ordine degli addendi non conta? Ad esempio, 4 è uguale a 4, 3+1, 2+2, 2+1+1 e 1+1+1+1, quindi p(4) vale cinque; 5 ha sette partizioni e 10 ne ha quarantadue. Le partizioni compaiono nella teoria dei numeri, nelle funzioni generatrici, nella meccanica statistica e nelle gare di programmazione ogni volta che si contano somme di multiinsiemi piuttosto che composizioni ordinate o partizioni di insiemi etichettati. Questa capacità accetta un intero non negativo n e restituisce il p(n) esatto come stringa decimale calcolata con programmazione dinamica in BigInt, così che valori ben oltre i limiti abituali degli interi sicuri restino corretti cifra per cifra. Un n negativo viene rifiutato con un errore di convalida chiaro invece di uno zero silenzioso o di una risposta errata.

Come è definita la funzione di partizione p(n)

Una partizione intera non ristretta di un intero non negativo n è un modo di scrivere n come somma di interi positivi in cui l'ordine degli addendi è irrilevante. Per convenzione p(0) vale uno, contando la partizione vuota dello zero. I piccoli valori da manuale sono p(1)=1, p(2)=2 (ossia 2 e 1+1), p(3)=3, p(4)=5, p(5)=7, p(6)=11 e p(10)=42.

La funzione generatrice ordinaria della successione è il prodotto infinito, su k maggiore o uguale a uno, di uno su uno meno x elevato a k, che codifica il fatto che ogni intero positivo può comparire un numero qualsiasi di volte come parte. Una ricorrenza pratica usata nel software è il programma dinamico classico in stile resto di monete: si inizializza un array con un modo per formare la somma zero, poi per ogni dimensione di parte da uno a n si aggiungono i modi per completare il resto.

Quella ricorrenza riempie p(n) in modo esatto e non conta mai due volte gli ordinamenti perché le parti vengono introdotte una sola volta in ordine di dimensione non decrescente.

Oggetti affini ma diversi includono le composizioni, in cui l'ordine conta e vi sono due elevato a n meno uno composizioni di n; le partizioni di insiemi contate dai numeri di Stirling di seconda specie o dai numeri di Bell, che partizionano elementi etichettati invece di sommare interi positivi non etichettati; e le partizioni ristrette che richiedono parti distinte, solo parti dispari o un numero fisso di parti.

Questa implementazione non usa mai approssimazioni in virgola mobile, campionamento Monte Carlo o tabelle esterne: riempie un array unidimensionale di BigInt affinché ogni cifra sia corretta. Il percorso è pienamente deterministico — senza semi casuali, senza orologi, senza rete e senza deriva di modello —, cosicché lo stesso n produce sempre la stessa stringa.

Dove le partizioni intere compaiono nel lavoro reale

I corsi di teoria dei numeri e le gare di programmazione chiedono costantemente quante partizioni non ristrette abbia un dato n, come cresca p(n) o se una tabella di piccoli valori coincida con le congruenze di Ramanujan e altre identità classiche. I progettisti di algoritmi usano i conteggi di partizioni quando analizzano spazi di stato in stile knapsack intero, contano decomposizioni a multiinsieme di un budget di risorse o dimensionano tabelle di DP le cui dimensioni seguono le dimensioni delle parti.

Contesti di fisica e combinatoria collegano p(n) alle funzioni di partizione bosoniche e ai coefficienti di funzioni generatrici; gli educatori spesso mostrano un elenco breve di partizioni di un piccolo n e poi chiedono solo il conteggio. La preparazione ai colloqui e l'allenamento olimpico richiedono di frequente un p(n) affidabile senza mantenere a mano grandi tabelle né rischiare conteggi di composizioni sfalsati di uno.

Se in seguito servono composizioni in cui l'ordine conta, partizioni di insiemi tramite numeri di Stirling di seconda specie, solo numeri di Bell, partizioni ristrette con parti distinte o solo dispari, oppure un elenco esplicito di ogni partizione anziché il conteggio, li tratti come intenti di ricerca separati anziché sovraccaricare questa pagina. Mantenga n entro il limite documentato affinché la latenza del livello gratuito resti prevedibile, e preferisca consumatori di stringa per il valore restituito perché p(n) esce dall'intervallo degli interi sicuri molto prima di cinquemila.