Visualizza il feed RSS

Titolo provvisorio...

Un problemino con le addizioni...

Valutazione: 3 voti, con una media del 5.00.
di pubblicato il 21-03-2010 alle 23:53 (7046 Visite)
Abstract: questo post è alquanto lungo, tanto da dover essere suddiviso su due blog entries. Vale dunque la pena di anticiparne i contenuti in poche righe iniziali. Si parla di partizioni di numeri naturali, cioè dei modi per scrivere un numero dato come somma di altri numeri interi positivi: queste somme finite vengono studiate sistematicamente in matematica da almeno tre secoli, hanno proprietà importanti in Teoria dei Numeri e matematica discreta, e costituiscono inoltre un esercizio di programmazione combinatoria molto valido, sebbene elementare. Nel seguito si introduce l'argomento, senza la benché minima pretesa di esaustività e rigore ma con l'esplicito scopo di incuriosire il lettore e presentare un risultato storico eclatante - decisamente controintuitivo e sorprendente per i più - che riguarda le "banali" partizioni. Nella seconda parte sono inoltre presentati opportuni esempi di algoritmi combinatori implementati nei linguaggi più idonei.


Capita piuttosto sovente (ad esempio, qualche giorno fa) che il sottoscritto debba aiutare qualche utente dei forum alle prese con un problemino di partizioni numeriche: in varie forme, ciò ricorre abbastanza spesso tra gli esercizi di combinatorica elementare, come anche in numerosi altri campi "insospettabili".

Pur essendo assolutamente improponibile l'idea di affrontare seriamente l'argomento su un blog (esistono interi testi dedicati alla sola teoria delle partizioni, come [02] !), vale la pena di dare qualche cenno sulla questione ai miei affezionati lettori, in modo da suscitare almeno un po' di curiosità e offrire qualche minimo spunto di approfondimento.

Posso anticipare che si tratta di un problema fortemente rappresentativo dello spirito dell'intera Teoria del Numero, che in generale si occupa di problemi semplici, dall'apparenza elementare ed innocua, i quali però talora celano vette di complessità matematica impressionanti: tanto che normalmente gli approfondimenti in materia non fanno neppure parte dei normali piani di studio nei corsi di laurea, a maggior ragione nelle lauree "brevi".

Ma procediamo con ordine.

Per i nostri scopi, può essere accettabile la seguente definizione semplificata. Dato un numero naturale n non nullo, ossia un intero strettamente positivo, chiamiamo partizione del naturale n (in k parti) la successione finita non crescente di naturali:

Formula LaTeX: \lambda\ =\ \{\lambda_1,\,\lambda_2,\, \dots,\, \lambda_k\}

per la quale vale:

Formula LaTeX: \begin{cases}n\, \geq\, \lambda_1\, \geq\, \lambda_2\, \geq\, \dots\, \geq\, \lambda_k\,>\,0\\\lambda_1\,+\,\lambda_2\,+\, \dots\,+\, \lambda_k\,=\,n\end{cases}

Gli interi lambda sono propriamente detti parti. Quindi una partizione, in termini intuitivi, è un modo per scrivere il naturale n dato come somma di due o più addendi (al limite, un singolo termine), anch'essi naturali e ovviamente non nulli.

Ci sono alcuni fatti che discendono in modo immediato da questa semplice definizione: ad esempio, il numero di parti k non sarà in alcun caso superiore al numero dato n, in quanto si ha, al più:

Formula LaTeX: n\ =\ \underset{\text{n volte}}{\underbrace{1 + 1 + ... + 1}}

Allo stesso modo, esiste una sola possibilità per scrivere un numero n come unico termine, ed è l'identità n = n. Naturalmente, quando n è maggiore di 1, è unica e distinta dalla precedente anche la scrittura n = (n -1) +1.

Ci accordiamo per indicare, come quasi universalmente in letteratura, con P(n) il numero totale di partizioni del naturale n (la cosiddetta funzione di partizione), e con P(n, k) uno specifico numero di partizioni di n in esattamente k parti, con 1 < k < n.

Vale allora la semplice relazione di ricorrenza:

Formula LaTeX: \\P(n,k)\ =\ P(n \,-\,1,\, k \,-\,1)\,+\,P(n \,-\,k,\,k)\\P(n, \,1)\ =\ P(n, \,n)\ =\ 1

Per pura pedanteria, ricordo che in altri contesti è utile che n sia semplicemente un intero non negativo, quindi possibilmente anche nullo (nel qual caso, esiste comunque una unica partizione derivata da 0 = 0); allo stesso modo, a volte è utile e comodo considerare la partizione stessa come una serie infinita definitivamente nulla dopo il k-esimo termine. Ma ciò trascende ampiamente gli scopi della nostra chiacchierata.

Piuttosto, i miei lettori più computazionalmente smaliziati avranno già iniziato a pensare ad altre proprietà combinatorie di queste "semplici" somme. Prendiamo in considerazione, ad esempio, la partizione in sei parti del numero 6 e mostriamo un modo intuitivo e ricorsivo nel quale tutte le altre dieci partizioni di tale numero possono essere da essa derivate, tramite parentesizzazione vincolata. Tralascio l'enunciazione esplicita delle banali regole del gioco, lasciandole all'intuizione dei miei lettori, e lascio "parlare" l'esempio.

Formula LaTeX: \begin{array}{rlr}6&=\ 1\ +\ 1\ +\ 1\ +\ 1\ +\ 1\ +\ 1&(1)\\\\6&=\ \underset{6}{\underbrace{(1\ +\ 1\ +\ 1\ +\ 1\ +\ 1\ +\ 1)}}&(2)\\5\ +\ 1&=\ \underset{5}{\underbrace{(1\ +\ 1\ +\ 1\ +\ 1\ +\ 1)}}\ +\ 1&(3)\\4\ +\ 2&=\ \underset{4}{\underbrace{(1\ +\ 1\ +\ 1\ +\ 1)}}\ +\ \underset{2}{\underbrace{(1\ +\ 1)}}&(4)\\4\ +\ 1\ +\ 1&=\ \underset{4}{\underbrace{(1\ +\ 1\ +\ 1\ +\ 1)}}\ +\ 1\ +\ 1&(5)\\3\ +\ 3&=\ \underset{3}{\underbrace{(1\ +\ 1\ +\ 1)}}\ +\ \underset{3}{\underbrace{(1\ +\ 1 +\ 1)}}&(6)\\3\ +\ 2\ +\ 1&=\ \underset{3}{\underbrace{(1\ +\ 1\ +\ 1)}}\ +\ \underset{2}{\underbrace{(1\ +\ 1)}}\ +\ 1&(7)\\3\ +\ 1\ +\ 1\ +\ 1&=\ \underset{3}{\underbrace{(1\ +\ 1\ +\ 1)}}\ +\ 1\ +\ 1\ +\ 1&(8)\\2\ +\ 2\ +\ 2&=\ \underset{2}{\underbrace{(1\ +\ 1)}}\ + \underset{2}{\underbrace{(1\ +\ 1)}}\ +\ \underset{2}{\underbrace{(1\ +\ 1)}}&(9)\end{array}

Ho qui riportato solo i primi otto passaggi, comunque banali e ampiamente sufficienti a delineare l'idea: la cui natura, squisitamente ricorsiva, invoglia a codificare immediatamente una soluzione pratica nel proprio linguaggio preferito - magari con un generatore python!
Naturalmente l'algoritmica in ambito combinatorio ci ha consegnato anche altri approcci alla generazione esaustiva delle partizioni, ma tale esempio così intuitivo mantiene comunque un suo fascino (e grande valore didattico).

Sempre restando in tema di rappresentazioni semplici, uno degli strumenti grafici più interessanti ed efficaci sviluppati per trattare la teoria delle partizioni sono i diagrammi di Ferrers e quelli di Young.
In tali diagrammi, semplici e intuitivi, ogni addendo (parte) viene rappresentato con un numero di simboli (risp. pallini o quadratini) pari al suo valore, allineati ai vertici di una griglia quadrata rispettando un ordinamento non crescente dall'alto verso il basso.

Ecco, ad esempio, una delle partizioni di 7 così rappresentata secondo Ferrers:

Formula LaTeX: 7\ =\ 3\,+\,2\,+\,1\,+\,1\\\\\begin{matrix}(3) & \bullet & \bullet & \bullet\\(2) & \bullet & \bullet & \\(1) & \bullet &  & \\(1) & \bullet &  & \end{matrix}

Usando tali diagrammi, viene naturale definire anche la partizione coniugata: è sufficiente scambiare righe e colonne, ossia "contare i pallini" per colonne, anziché per righe, e riscrivere il nuovo diagramma con tale ordine:

Formula LaTeX: \begin{matrix} & (4) & (2) & (1)\\(3) & \bullet & \bullet & \bullet\\(2) & \bullet & \bullet & \\(1) & \bullet &  & \\(1) & \bullet &  &\end{matrix}\ \ \Leftrightarrow \ \ \begin{matrix}(4) & \bullet & \bullet & \bullet & \bullet\\(2) & \bullet & \bullet & \\(1) & \bullet &  & \end{matrix}

In questo modo è immediato, ad esempio, farvi intuire la dimostrazione di un fondamentale teorema: ogni partizione di n il cui elemento massimo sia m (in questo caso, 3) corrisponde ad una partizione del medesimo numero n che abbia esattamente m parti; il che appare ovvio contando le "colonne" di una partizione, e quindi le "righe" della sua coniugata, in rappresentazione Ferrers o Young.

Purtroppo gli spazi del blog non ci consentono di giocare oltre con i diagrammi e le altre innumerevoli, interessantissime proprietà delle partizioni: a malincuore, non posso far altro che rimandarvi alla scheletrica bibliografia introduttiva in calce.

Ora che ho fornito almeno una ectoplasmatica idea di questa inerente (ma solo apparente !) semplicità, nessuno si stupirà nell'apprendere che praticamente tutti i testi di algoritmica combinatoria trattano l'argomento "Generazione delle partizioni di un naturale" nelle primissime pagine, tra gli oggetti combinatori elementari... per divertirci un po' a fare i contabili, ecco dove appare il relativo paragrafo in alcuni dei testi consultati:

[13] Ruskey, pag. 16;
[10] Nijenius & Wilf, pag. 65;
[07] Kreher & Stinson, pag. 67;
[12] Reingold-Nievergelt-Deo, pag. 191 (solo perché contiene una parte introduttiva molto corposa );

Il piazzamento in manuali più generalisti risulta leggermente diverso, per la cronaca:
[03] Arndt, pag. 333;
[15] Skiena, pag. 456 (in realtà all'inizio della seconda sezione, dedicata più specificamente ai singoli algoritmi).

Va bene, basta, per carità... con questi pochi dati abbiamo già intuito che l'esercizio di generare tutte le partizioni di n è elementare, forse anche troppo. Così, almeno, ragionano i giovani programmatori che periodicamente vengono a bussarmi all'uscio: un po' stupiti e un po' contrariati perché, in uno scenario così semplice, il loro libro preferito "sembra aver dimenticato di menzionare la formuletta per calcolare quante sono in totale le partizioni P(n) di un numero n dato".
Probabilmente, aggiungono, perché deve essere una formula talmente puerile da esser lasciata come "semplice esercizio per il lettore interessato", anche se stranamente non sono riusciti a ricavarla da soli dopo vari tentativi (a volte anche ingegnosi, a onor del vero).

Le cose non vanno diversamente se si apre uno dei tanti testi di matematica discreta, ad esempio il bel lavoro [09] che pure all'argomento dedica un intero capitoletto, trattando anche temi relativamente avanzati, come i reticoli di dominanza e quelli di Young.

Se sul Kreher-Stinson si giunge addirittura a scrivere che «Although partitions have been studied by mathematicians for hundreds of years and many interesting results are known, there is no known formula for the values of P(m).» ([07], pag. 67), gli altri testi se la cavano con una più dignitosa omertà, dopo aver ricordato che P(n) cresce in modo estremamente veloce, o si limitano a presentare tabelline varie, come la seguente nella quale P(n) rappresenta il numero totale di partizioni, q(n) il numero di partizioni semplici ovvero in parti tutte distinte:

Formula LaTeX: \begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\\hline P(n) & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 42 & 56 & 77 & 101 & 135\\ \hline q(n) & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 6 & 8 & 10 & 12 & 15 & 18 & 22\\ \hline \end{array}

A questo punto, messo di fronte - libri alla mano - a cotanta generale evidenza, di solito il giovane programmatore sbotta impaziente: "Ma insomma, che avrà mai di strano 'sta dannata formuletta, che tutti se la nascondono nella manica ? Per tirar fuori quei quattro numeretti, non sarà mica così complicata... insomma... voglio dire, se esiste la formuletta di Binet per trovare l'ennesimo numero di Fibonacci in O(1), ci sarà ben qualcosa anche per questo caso... o no ?!?!?!"

Ebbene, una formula esiste. Purtroppo però è un tantino complicata. Anzi, è opinione popolare che si tratti di una delle formule più mostruosamente complicate, astruse e macchinose dell'intera matematica pura...

La stima asintotica originariamente trovata da Hardy e Ramanujan un secolo fa aveva già un aspetto "poco rassicurante":

Formula LaTeX: (1)\ \ \ P(n)\ \underset{n \rightarrow \infty}{\cong}\ \frac{1}{4n\sqrt{3}} \cdot \textrm{exp}{\left(\pi \sqrt{\frac{2n}{3}}\right)}

Ma questo è nulla. Il numero di partizioni di un naturale n è dato dalla valutazione parziale (con approssimazione all'intero più vicino) della serie asintotica convergente che segue:

Formula LaTeX: {\color{red}(2)\ \ \ P(n)\ =\ \frac{1}{\pi \sqrt{2}}\, \sum_{k\,=\,1}^{\infty}A_k(n)\sqrt{k}\,\frac{d}{dx  }\left[\frac{\sinh\left(\frac{\pi}{k}\sqrt{\frac{2}{3}(x \,-\,\frac{1}{24})\,}\right )}{\sqrt{(x \,-\,\frac{1}{24})}} \right]_{x\,=\,n}}

dove

Formula LaTeX: (3)\ \ \ A_k(n)\ =\ \sum_{h\,=\,1}^{k}\delta\left[MCD(h,k),\,1\right] \, exp \left[i\pi \, \left(s(h,k) -{\frac{2nh}{k}} \right) \right]

Nella definizione qui sopra compare anche la familiare funzione discreta Delta di Kronecker, poiché contribuiscono al totale solo quei termini nei quali h e k sono primi tra loro (coprimi), il che è verificato quando il loro massimo comun divisore è pari a uno:

Formula LaTeX: (4)\ \ \ \delta(a, b)\ \overset{def}{=}\ \begin{cases}0 & \text{se } a\,\neq\,b \\ 1 & \text{se } a\,=\,b \end{cases}

Inoltre, si definisce come segue la somma di Dedekind:

Formula LaTeX: (5)\ \ \ s(h,k)\ =\ \sum_{j\,=\,1}^{k-1}\frac{j}{k}\,\left(\frac{hj}{k}\,-\,\left\lfloor{\frac{hj}{k}}\right\rfloor\,-\,\frac{1}{2} \right)

Solo una pennellata di pedanteria formale. L'uso della notazione funzionale "informatichese" exp(x) per l'esponenziale è una scelta dettata da opportunità pratica, perché ci consente di rendere molto più leggibili esponenti lunghi e complicati, senza forzature di font:

Formula LaTeX: exp(x)\ \overset{def}{=}\ e^x

Per il resto, la notazione è conforme a quella usata su Wolfram MathWorld, in [01] e nella maggioranza delle pubblicazioni moderne. Il venerabile Knuth [06], che all'argomento dedica le prime 25 pagine nel fascicolo 3b del quarto volume, fa ovviamente uso di una notazione leggermente diversa, peraltro con l'uso della funzione sferica di Bessel modificata, rigorosamente coerente con la sua esposizione dello sviluppo storico della formula e di altri risultati correlati.

La stupefacente formula, alla quale tra l'altro si fa cenno anche in [14], è dovuta come accennavo ai teorici dei numeri Hardy e Ramanujan, con sostanziali migliorie a posteriori da parte di Hans Rademacher, e porta quindi il nome di tutti e tre. Le pubblicazioni originali sono la [08] e la [11], rispettivamente.

Orbene, a questo punto potete facilmente immaginare l'espressione (del tipo "giovane mucca in ridente pascolo alpestre Svizzero che vede passare per la prima volta un treno a cremagliera" ) del nostro giovane programmatore: giunto al mio cospetto ansioso di abbellire il suo programmino col calcolo del numero di partizioni del naturale dato in input, si trova di fronte a questo spaventoso formulone.

Più di qualcuno ha osservato letteralmente che invece di una "vera formula", di quelle che "si studiano a scuola", questa sembra piuttosto una di quelle apocalittiche bischerate matematiche che gli scenografi fanno copiare a qualche scagnozzo sulle finte lavagne dei finti laboratori del solito improbabile scienziato pazzo cinematografico (per chi fosse interessato, c'è in rete un'ampia quanto oziosa letteratura su formule mal copiate e intere lavagnate di nonsense apparse a vario titolo in pellicole più o meno famose).

In effetti è una formula sbalorditiva secondo la qualificata opinione della maggioranza dei matematici (computazionali): Knuth la definisce senza mezzi termini «...surely one of the most astonishing identities ever discovered» ([06], fasc. 3b, pag. 8).
Sembra davvero provenire da un'altra galassia, per quanto è sproporzionatamente distante dalla banalissima natura di questo umile problemino di addizioni: una sfilza di radicali, pigreco, l'unità immaginaria, funzioni trascendenti, differenziali, floor, una delta discreta applicata ad un massimo comun divisore e una storia d'implicazioni che rimanda facilmente a cerchi di Ford, serie di Farey, funzione sferica di Bessel...

Per il momento temo che dovremo fermarci qui, essendo vicinissimi al limite dei ventimila caratteri. Ma non perdete la prossima puntata !!!

[01] G. Almkvist & H. S. Wilf, "On the coefficients in the Hardy-Ramanujan-Rademacher formula for p(n)", J. Number Theory 50 (1995), 329—334; {link}

[02] G. E. Andrews, "The theory of partitions", Encyclopedia of Mathematics and Its Applications, Gian-Carlo Rota (editor), Addison-Wesley, 1976

[03] J. Arndt, "Matters Computational", {preprint}

[04] R. E. Boss, "Partitions of numbers: An efficient algorithm in J", Vector, Vol. 23, Issue 4, {link}

[05] R. Kanigel, "L'uomo che vide l'infinito. La vita breve di Srinivasa Ramanujan, genio della matematica", Rizzoli, 2003

[06] D. E. Knuth, "The Art of Computer Programming, Vol. 4", Addison-Wesley, 2004, {link}

[07] D. L. Kreher & D. R. Stinson, "Combinatorial Algorithms: Generation, Enumeration and Search", CRC Press, 1998, {link}

[08] G. H. Hardy & S. Ramanujan "Asymptotic formulae in combinatorial analysis", Proc. London Math. Soc., 17, 237-252 (1918)

[09] E. Munarini e N. Zagaglia Salvi, "Matematica Discreta", UTET Città Studi, 1997

[10] A. Nijenhius & H. S. Wilf, "Combinatorial Algorithms", Academic Press, 1975, {download}

[11] H. Rademacher, “On the Partition Function p(n)”, Proc. London Math. Soc. 43, 241-254, 1937

[12] E. M. Reingold + J. Nievergelt & N. Deo, "Combinatorial Algorithms", Prentice Hall, 1977

[13] F. Ruskey, "Combinatorial Generation", {electronic edition}

[14] M. du Sautoy, "L'enigma dei numeri primi", Rizzoli, 2004

[15] S. S. Skiena, "The Algorithms Design Manual, 2nd ed.", Springer, 1997, {link}

[16] R. Stanley, "Enumerative Combinatorics, Vol. 1", Cambridge University Press, 1997, {link}

[17] E. W. Weisstein, “Partition” - MathWorld, a Wolfram Web Resource, {link}

[18] A. Zoghbi & I. Stojmenovic, "FAST ALGORITHMS FOR GENERATING INTEGER PARTITIONS", Intern. J. Computer Math., Vol- 70. pp. 319-332, {link}

Commenti