Don't take life too seriously: it's just a temporary situation

Partizioni (numero di)

Matematica combinatoria 

Indice

  1. 1. Pagina principale
  2. 2. Proprietà modulari dei numeri di partizioni
  3. 3. Partizioni con vincoli sul numero di parti
  4. 4. Partizioni con vincoli sul tipo di parti

Il numero di partizioni di n, talvolta indicato con p(n), è il numero di modi distinti per ottenere n come somma di interi maggiori di zero, anche ripetuti, indipendentemente dall’ordine. Per esempio p(5) = 7, perché 5 può essere ottenuto come somma di interi nei seguenti modi:

  • 5,

  • 4 + 1,

  • 3 + 2,

  • 3 + 1 + 1,

  • 2 + 2 + 1,

  • 2 + 1 + 1 + 1,

  • 1 + 1 + 1 + 1 + 1.

 

Si indica invece con q(n) il numero di modi distinti per ottenere n come somma di interi maggiori di zero, tutti diversi, indipendentemente dall’ordine. Per esempio q(5) = 3, perché 5 può essere ottenuto come somma di interi differenti nei seguenti modi:

  • 5,

  • 4 + 1,

  • 3 + 2.

 

Leibniz, nel 1669, fu il primo a indagare sul numero di modi di scomporre un intero come somma di altri; l’argomento fu poi ripreso da Eulero nel 1740, da Ramanujan nel 1917 e quindi da molti altri. Le notazioni p(n) e q(n) furono introdotte da Hardy nel 1920.

 

Le partizioni hanno applicazioni in quasi tutte le scienze naturali; per esempio, in fisica statistica si presenta il problema di ripartire un certo numero di quanti di energia tra particelle, o di particelle tra livelli energetici possibili.

 

Varie formule permettono di calcolare p(n) e q(n) a partire dal numero di partizioni di interi inferiori:

  • Formula per il calcolo di p(n), dove la somma va arrestata quando gli argomenti di p diventano negativi; questa identità, dimostrata da Eulero, permette di calcolare velocemente p(n), almeno per i primi valori di n, e utilizza i numeri pentagonali generalizzati.

  • Formula per il calcolo di p(n);

  • Formula per il calcolo di p(2n + 1);

  • Formula per il calcolo di p(n);

  • Formula per il calcolo di q(n);

  • Formula per il calcolo di q(n), dove s(n) vale (–1)m, se Formula per i numeri pentagonali generalizzati (ossia se n è un numero pentagonale generalizzato), 0 altrimenti.

 

Esiste anche un modo per calcolare direttamente (si fa per dire!) p(n): la spettacolare formula di Hardy – Ramanujan – Rademacher:

Formula di Hardy – Ramanujan – Rademacher, dove Formula per la funzione di Bessel modificata di ordine 3 / 2 è la funzione di Bessel modificata di ordine Tre mezziFormula per la definizione di Ak(n) e infine Formula per la definizione di s(h, k). La formulazione di Rademacher è Versione di Rademacher della formula per il calcolo di p(n); anche solo dimostrare che le due formule sono equivalenti è un esercizio di analisi piuttosto impegnativo.

 

I numeri di partizioni per n sino a 20 sono riportati nella tabella seguente.

n

pn

qn

0

1

1

1

1

1

2

2

1

3

3

2

4

5

2

5

7

3

6

11

4

7

15

5

8

22

6

9

30

8

10

42

10

11

56

12

12

77

15

13

101

18

14

135

22

15

176

27

16

231

32

17

297

38

18

385

46

19

490

54

20

627

64

 

Alcune proprietà:

  • Somma che coinvolge p(n);

  • Proprietà di p(n);

  • Proprietà di p(n), per n > 24 (supposta da W.Y.C. Chen nel 2010 e dimostrata poco dopo da J.E. Janoski);

  • Proprietà di p(n), per n > 5 (Yi Wang e Bao-Xuan Zhu, 2013);

  • Proprietà di q(n), per n > 3.

 

Nel 2012 Zhi-Wei Sun propose alcune congetture sul numero di partizioni:

  • Formula che coinvolge p(n) è strettamente crescente per n > 25;

  • Proprietà di q(n), per n > 8;

  • Formula che coinvolge q(n) è strettamente crescente per n > 44.

Sun verificò le congetture per n fino a 100000.

 

Asintoticamente:

  • p(n) tende a Limite asintotico per p(n) (Hardy e Ramanujan, 1917);

  • q(n) tende a Limite asintotico per p(n) (Hardy e Ramanujan, 1917).

 

Funzioni generatrici:

  • per p(n) è Funzione generatrice per p(n);

  • per q(n) è Funzione generatrice per q(n);

  • per il numero di partizioni nelle quali nessuna parte capita più di d volte è Funzione generatrice per il numero di partizioni nelle quali nessuna parte capita più di d volte;

  • per il numero di partizioni nelle quali nessuna parte capita esattamente una volta è Funzione generatrice per il numero di partizioni nelle quali nessuna parte capita esattamente una volta;

  • per il numero di partizioni nelle quali ogni parte capita esattamente 2, 3 o 5 volte è Funzione generatrice per il numero di partizioni nelle quali ogni parte capita esattamente 2, 3 o 5 volte.

 

Ramanujan trovò le funzioni generatrici Funzione generatrice per il numero di partizioni degli interi della forma 5n + 4 e Funzione generatrice per il numero di partizioni degli interi della forma 7n + 5, senza però darne una dimostrazione.

 

Le partizioni in interi appartenenti a un insieme S hanno funzione generatriceFunzione generatrice per il numero di partizioni in interi appartenenti a un insieme S.

 

Per n grande, p(n) si può approssimare con Approssimazione per p(n) (Hardy e Ramanujan, 1917).

 

Costruendo una tabella delle partizioni, si può notare una coincidenza apparentemente curiosa. Proviamo con il numero 6, con le partizioni mostrate nella tabella seguente.

Partizione

Numero di 1

Parti distinte

6

0

1

5 + 1

1

2

4 + 2

0

2

4 + 1 + 1

2

2

3 + 3

0

1

3 + 2 + 1

1

3

3 + 1 + 1 + 1

3

2

2 + 2 + 2

0

1

2 + 2 + 1 + 1

2

2

2 + 1 + 1 + 1 + 1

4

2

1 + 1 + 1 + 1 + 1 + 1

6

1

Totale

19

19

Il numero totale di 1 che compaiono nelle partizioni è 19, uguale al numero totale di parti distinte. Non è affatto una coincidenza: il teorema di Stanley, infatti, dimostra che i due totali sono sempre uguali.

Nel 1984 Paul Elder dimostrò una generalizzazione di questo teorema: il numero totale di occorrenze di un intero k tra le partizioni di n è uguale al numero totale di volte che una parte ha k o più occorrenze in una singola partizione. Il teorema di Stanley corrisponde al caso k = 1.

Per le dimostrazioni si vedano i libri di Honsberger e Stanley citati nella bibliografia.

 

Le dimostrazioni di molte delle formule elencate si trovano sui testi di Yaglom e Andrews, citati nella bibliografia.

Bibliografia

  • Andrews, G.E.;  The Theory of Partitions, Cambridge University Press, 1984.
  • Balzarotti, Giorgio;  Lava, Paolo Pietro;  103 Curiosità matematiche, Milano, Hoepli, 2010.
  • Clawson, Calvin C.;  Mathematical Mysteries, Basic Books, 1996.
  • Dunham, William;  Euler, the Master of Us All, The Mathematical Association of America, 1999.
  • Guy, Richard K.;  Larson, Loren;  Vaderlind, Paul;  The Inquisitive Problem Solver, The Mathematical Association of America, 2002 -

    Una buona raccolta di problemi non troppo complessi, spesso con generalizzazioni interessanti.

  • Honsberger, Ross;  Mathematical Gems III, The Mathematical Association of America,, 1985.
  • Stanley, Richard P.;  Enumerative Combinatorics, Cambridge University Press, vol. I, 1997.
  • Yaglom, A.M.;  Yaglom, I.M.;  Challenging Mathematical Problems with Elementary Solutions, New York, Dover, 1987 -

    Traduzione dal russo di Neelementarnye Zadachi v Elementarnom Izlozhenii (Problemi non elementari e soluzioni elementari), Mosca, Ist. Governativo di stampa per la letteratura tecnico-teorica, 1954. Una splendida raccolta di problemi, generalmente non facili, comparsa per la prima volta in occidente nel 1964 (S. Francisco, Holden-Day Inc., 1964).

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.