Utente:Grasso Luigi/sandbox4/Partizione di un intero

In matematica, una partizione di un intero positivo $n$ è un modo di scrivere $n$ come somma di interi positivi, senza tener conto dell'ordine degli addendi. Formalmente, una partizione di $n$ è una m-tupla di interi positivi $(\lambda _{1},\lambda _{2},\dots ,\lambda _{m})$ tali che

$\lambda _{1}\geq \lambda _{2}\geq \dots \geq \lambda _{m}~~{\text{e}}~~\lambda _{1}+\lambda _{2}+\dots +\lambda _{m}=n.$

Spesso si chiede che $n$ sia un intero positivo; talora però risulta opportuno considerare anche come unica partizione dello $0$ la sequenza vuota.

Esempi

Le partizioni di $4$ sono le seguenti:

1. $4$
2. $3+1$
3. $2+2$
4. $2+1+1$
5. $1+1+1+1$

Le partizioni di $8$ sono invece le seguenti:

1. $8$
2. $7+1$
3. $6+2$
4. $6+1+1$
5. $5+3$
6. $5+2+1$
7. $5+1+1+1$
8. $4+4$
9. $4+3+1$
10. $4+2+2$
11. $4+2+1+1$
12. $4+1+1+1+1$
13. $3+3+2$
14. $3+3+1+1$
15. $3+2+2+1$
16. $3+2+1+1+1$
17. $3+1+1+1+1+1$
18. $2+2+2+2$
19. $2+2+2+1+1$
20. $2+2+1+1+1+1$
21. $2+1+1+1+1+1+1$
22. $1+1+1+1+1+1+1+1$

La funzione di partizione

La funzione di partizione indica, per ogni intero positivo $n$, il numero di partizioni esistenti per $n$. Per esempio, per quanto mostrato negli esempi,

$p\left(4\right)=5,$

mentre

$p\left(8\right)=22.$

La funzione partizione non è né moltiplicativa né additiva e cresce più velocemente di qualsiasi polinomio in $n$ al crescere di $n$(si vedano le formule asintotiche nel seguito). Viene solitamente indicata con $p(n)$. I primi valori di $p(n)$, partendo da $n=0$, sono:

$1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958,2436,3010,3718,4565,5604,\ldots$

Congruenze

Ramanujan trovò le seguenti congruenze:

${\begin{aligned}p(5k+4)&\equiv 0{\bmod {5}}\\p(7k+5)&\equiv 0{\bmod {7}}\\p(11k+6)&\equiv 0{\bmod {1}}1\\\end{aligned}}$

Si nota che 4, 5, 6 sono numeri consecutivi e 5, 7 e 11 sono primi consecutivi. Allora si potrebbe pensare che

$p(13k+7)\equiv 0{\bmod {1}}3$

Questo è falso. Infatti, si può dimostrare che non ci sono altre congruenze del tipo $p(bk+a)\equiv 0{\bmod {b}}$.

Negli anni '60 A. O. L. Atkin dell'Università dell'Illinois a Chicago scoprì ulteriori congruenze, ad esempio:

$p((11^{3}\cdot 13)k+237)\equiv 0{\bmod {1}}3.$

Diagrammatic representations of partitions

There are two common diagrammatic methods to represent partitions: as Ferrers diagrams, named after Norman Macleod Ferrers, and as Young diagrams, named after Alfred Young. Both have several possible conventions; here, we use English notation, with diagrams aligned in the upper-left corner.

Ferrers diagram

The partition 6 + 4 + 3 + 1 of the number 14 can be represented by the following diagram:

The 14 circles are lined up in 4 rows, each having the size of a part of the partition. The diagrams for the 5 partitions of the number 4 are shown below:

4	=	3 + 1	=	2 + 2	=	2 + 1 + 1	=	1 + 1 + 1 + 1

Young diagram

An alternative visual representation of an integer partition is its Young diagram (often also called a Ferrers diagram). Rather than representing a partition with dots, as in the Ferrers diagram, the Young diagram uses boxes or squares. Thus, the Young diagram for the partition 5 + 4 + 1 is

while the Ferrers diagram for the same partition is

While this seemingly trivial variation does not appear worthy of separate mention, Young diagrams turn out to be extremely useful in the study of symmetric functions and group representation theory: filling the boxes of Young diagrams with numbers (or sometimes more complicated objects) obeying various rules leads to a family of objects called Young tableaux, and these tableaux have combinatorial and representation-theoretic significance.Template:Sfn As a type of shape made by adjacent squares joined together, Young diagrams are a special kind of polyomino.

Storia

Fino agli inizi del XX secolo si credeva che non fosse possibile trovare una formula per la funzione di partizione, ma nel 1918 Ramanujan e Hardy pubblicarono una formula asintotica per la funzione di partizione:

$p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left(\pi {\sqrt[{}]{\frac {2n}{3}}}\right){\text{ per }}n\to \infty$

J.V. Uspensky ritrovò la stessa formula, indipendentemente, nel 1920.

Hardy e Ramanujan trovarono un'espansione asintotica con questa approssimazione come primo termine:

$p(n)\sim {\frac {1}{2\pi {\sqrt {2}}}}\sum _{k=1}^{v}A_{k}(n){\sqrt {k}}{\frac {\mathrm {d} }{\mathrm {d} n}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\exp \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right)$

Nel 1937, Hans Rademacher migliorò la formula di Hardy e Ramanujan, elaborando una serie convergente che tende a $p(n)$:

$p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }{\sqrt {k}}\;A_{k}(n)\;{\frac {\mathrm {d} }{\mathrm {d} n}}\left({\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\sinh \left({\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}\right)\right),$

dove, in entrambi i casi

$A_{k}(n)=\sum _{0\leq m<k\;;\;(m,k)=1}\exp \left(\pi is(m,k)-2\pi i{\frac {nm}{k}}\right),$

con la somma effettuata sui numeri naturali compresi tra $0$ e $k$ che sono coprimi con $k$ e con $s(m,k)$ che indica la somma di Dedekind.

Nel gennaio del 2011, il matematico statunitense Ken Ono, della Emory University di Atlanta, Georgia, insieme ai suoi collaboratori ha fatto grossi progressi nella comprensione del comportamento della funzione di partizione. Estendendo alcune formule di Ramanujan, è riuscito a mostrare che i numeri di partizione hanno un comportamento di tipo frattale: apparentemente essi sono disordinati, senza alcun legame logico o alcuna congruenza, ma se analizzati a fondo si scoprono schemi ordinati con un preciso ordine di ripetizione. Inoltre, Ken Ono, insieme ai suoi collaboratori, è riuscito a ottenere una formula esplicita che permette di calcolare le partizioni $p(n)$di qualsiasi numero intero attraverso una somma di un numero finito di termini.

Bibliografia

• George E. Andrews, The Theory of Partitions (1976), Cambridge University Press. ISBN 052163766X.
• Tom M. Apostol, Modular functions and Dirichlet Series in Number Theory (1990), Springer-Verlag, New York. ISBN 0387971270 (vedi il capitolo 5 per un'introduzione pedagogica moderna alla formula di Rademacher)
• Sautoy, Marcus Du. The Music of the Primes. New York: Perennial-HarperCollins, 2003.
• D. H. Lehmer, On the remainder and convergence of the series for the partition function Trans. Amer. Math. Soc. 46(1939) pp 362–373.
• Gupta, Gwyther, Miller, Roy. Soc. Math. Tables, vol 4, Tables of partitions, (1962)
• Ian G. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, 1979, ISBN 0198535309 (vedi sezione l.1)
• Ken Ono, Distribution of the partition function modulo m, Annals of Mathematics 151 (2000) pp 293–307.
• Richard P. Stanley, Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press, 1999 ISBN 0521560691.
• A. L. Whiteman, A sum connected with the series for the partition function, Pacific Journal of Math. 6:1 (1956) 159–176. (Contiene la formula di Selberg. La forme Provides the Selberg formula)
• Hans Rademacher, Collected Papers of Hans Rademacher, (1974) MIT Press; v II, p 100–107, 108–122, 460–475.
• Miklós Bóna (2002). A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific Publishing. ISBN 981-02-4900-4.
• George E. Andrews, Kimmo Eriksson (2004). Integer Partitions. Cambridge University Press. ISBN 0-521-60090-1.

Voci correlate

• Tabella di Young
• Numeri di Bell
• Partizione di un insieme

Collegamenti esterni

• (EN) I primi valori di p(n) nell'enciclopedia delle sequenze numeriche
• Emory University Home Page.
• Partition and composition calculator, su btinternet.com. URL consultato il 3 maggio 2019 (archiviato dall'url originale il 10 novembre 2006).
• First 4096 values of the partition function, su numericana.com.
• An algorithm to compute the partition function, su numericana.com.
• Pieces of Number da Science News Online
• Lectures on Integer Partitions di Herbert S. Wilf
• Counting with partitions, su luschny.de.
• Integer::Partition Perl module dal CPAN
• Fast Algorithms For Generating Integer Partitions (PDF), su site.uottawa.ca. URL consultato il 29 gennaio 2011 (archiviato dall'url originale il 20 febbraio 2009).
• Generating All Partitions: A Comparison Of Two Encodings, su arxiv.org.
• Amanda Folsom, Zachary A. Kent, e Ken Ono, l-adic properties of the partition function.
• Jan Hendrik Bruinier e Ken Ono, An algebraic formula for the partition function.