Partizioni in parti distinte

La funzione di partizione in parti distinte q(n) risponde a una domanda classica di teoria dei numeri: in quanti modi può Lei scrivere un intero non negativo n come somma di interi positivi quando ogni addendo compare al più una volta e l'ordine non conta? Ad esempio, 5 è uguale a 5, 4+1 e 3+2, quindi q(5) vale tre; 6 ha quattro partizioni in parti distinte e 10 ne ha dieci. Questo conteggio differisce dalla funzione di partizione non ristretta p(n), che ammette parti ripetute come 2+2 o 1+1+1. Le partizioni in parti distinte compaiono nelle identità delle funzioni generatrici, nel teorema di Eulero che le equipara a quelle in parti dispari, nelle olimpiadi e negli esercizi di programmazione dinamica. Questa capacità accetta un intero non negativo n e restituisce il q(n) esatto come stringa decimale calcolata con programmazione dinamica 0-1 in BigInt, così i valori oltre gli interi sicuri restano corretti cifra per cifra. Un n negativo viene rifiutato con un chiaro errore di validazione invece di uno zero silenzioso o di una risposta sbagliata.

Come si definiscono e si contano le partizioni in parti distinte

Una partizione di un intero non negativo n in parti distinte è un modo di scrivere n come somma di interi positivi in cui nessuna parte si ripete e l'ordine degli addendi è irrilevante. Per convenzione q(0) vale uno, contando la partizione vuota dello zero. I valori classici da manuale sono q(1)=1 (ossia 1), q(2)=1 (ossia 2), q(3)=2 (3 e 2+1), q(4)=2 (4 e 3+1), q(5)=3 (5, 4+1, 3+2), q(6)=4 e q(10)=10.

La funzione generatrice ordinaria della successione è il prodotto infinito su k maggiore o uguale a uno di uno più x elevato a k, che codifica che ogni intero positivo può comparire zero volte o esattamente una volta come parte.

Un algoritmo pratico nel software è il programma dinamico classico in stile zaino 0-1: inizializzi un array con un modo per formare la somma zero e, per ogni dimensione di parte da uno a n, scorra l'array delle somme residue da n verso il basso fino a quella dimensione e sommi i modi che escludono la parte a quelli che la includono. L'ordine decrescente garantisce che ogni parte sia usata al più una volta, così l'uso multiplo non ristretto non si verifica mai.

Oggetti correlati ma diversi includono le partizioni non ristrette p(n), dove le parti possono ripetersi; le composizioni, dove l'ordine conta; le partizioni di insiemi contate dai numeri di Stirling di seconda specie; e le partizioni solo in parti dispari, che Eulero ha dimostrato equinumerose a quelle in parti distinte per ogni n. Questa implementazione non usa approssimazione in virgola mobile, campionamento Monte Carlo né tabelle esterne: riempie un array unidimensionale BigInt affinché ogni cifra sia corretta.

Il percorso è pienamente deterministico — senza semi casuali, orologi, rete né deriva di modello —, così lo stesso n produce sempre la stessa stringa.

Dove le partizioni in parti distinte compaiono nel lavoro reale

I corsi di teoria dei numeri e i concorsi di programmazione chiedono di continuo quante partizioni di n usano addendi a due a due distinti, come quel conteggio si confronti con p(n) non ristretta, o se una tabella di piccoli valori coincida con l'identità di Eulero sulle partizioni in parti dispari.

I progettisti di algoritmi usano i conteggi in parti distinte per analizzare spazi di stato stile subset-sum 0-1, contare combinazioni di dimensioni di risorsa uniche che totalizzano un budget, o dimensionare tabelle di DP le cui dimensioni seguono dimensioni di parte usate al più una volta. Le lezioni di combinatoria e funzioni generatrici collegano q(n) al prodotto di uno più x elevato a k e a identità ristrette di tipo Rogers–Ramanujan; gli educatori spesso elencano le partizioni distinte di un piccolo n e poi chiedono solo il conteggio.

La preparazione a colloqui e olimpiadi ha spesso bisogno di un q(n) affidabile senza tabelle tenute a mano né confusione con composizioni o partizioni non ristrette. Se più avanti le serve p(n) non ristretta, composizioni in cui l'ordine conta, partizioni di insiemi via Stirling di seconda specie, o un elenco esplicito di ogni partizione in parti distinte invece del conteggio, le tratti come intenzioni di ricerca separate anziché sovraccaricare questa pagina.

Tenga n entro il limite documentato così che la latenza del livello gratuito resti prevedibile, e preferisca consumatori di stringa per il valore restituito perché q(n) finisce per uscire dall'intervallo degli interi sicuri per argomenti grandi.