Partizione di un intero

Da Wikipedia, l'enciclopedia libera.

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 sequenza di interi positivi (\lambda_1, \lambda_2, ...,  \lambda_m) tali che

\lambda_1 \geq \lambda_2 \geq ...\geq \lambda_m ~~\mathrm{e}~~ \lambda_1 + \lambda_2 + \cdots \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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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é moltiplicativaadditiva e cresce molto in fretta[non chiaro] al crescere di n. Viene solitamente indicata con p(n). I primi valori di p(n) , partendo da 0, sono:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101 ...[1]

Storia[modifica | modifica sorgente]

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{e^{\pi\sqrt{\frac{2n}{3}}}}{4n\sqrt{3}} \mbox { per } n \to \infty

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

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{d }{d n}
\left( \frac {\sinh \left( \frac{\pi}{k}
\sqrt{\frac{2}{3}\left(n-\frac{1}{24}\right)}\right) }
{\sqrt{n-\frac{1}{24}}}\right),

dove

A_k(n) = \sum_{0\le m < k \; ; \; (m,k)=1} e^{ 
\pi i s(m,k) - 2\pi i\frac{nm}k},

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 americano 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 essere scoperti da 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.[2][3]

Voci correlate[modifica | modifica sorgente]

Note[modifica | modifica sorgente]

  1. ^ (EN) Sequenza A000041 in On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
  2. ^ Hidden Fractals Suggest Answer to Ancient Math Problem, 28 gennaio 2011.
  3. ^ American Institute of Mathematics, Fractal Structure to Partition Function

Bibliografia[modifica | modifica sorgente]

  • 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.

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica