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

Indichiamo con p(n, m) e q(n, m) rispettivamente il numero di partizioni di n in m parti, anche nulle (ovvero in al massimo m parti) e il numero di partizioni di n in m parti diverse tra loro, (quindi con al massimo una delle parti nulla), allora:

  • p(n, nt) è costante per n ≥ 2t;

  • p(n, m) = p(n) per mn;

  • p(n, m) e uguale al numero di partizioni di n + m in esattamente m interi non nulli;

  • p(n, m) e uguale al numero di partizioni di n con la parte massima uguale a m;

  • Formula per il numero di partizioni di n in m parti differenti (Eulero);

  • Formula per il numero di partizioni di n in m parti differenti (Eulero).

 

Per calcolare questi valori si può sfruttare la ricorrenza p(n, 0) = 0, p(n, 1) = 1, p(n, m) = p(n, m – 1) + p(nm, m) (Eulero).

Il numero P(n, k) di partizioni di n in k parti non nulle può essere calcolato con la ricorrenza P(n, 1) = 1, P(n, n) = 1, P(n, k) = P(n – 1, k – 1) + P(nk, k).

 

Il numero di partizioni di n in 2 parti anche nulle è Formula per i numero di partizioni di n in 2 parti anche nulle, che è anche il numero di partizioni di n in parti uguali a 1 o 2.

Il numero di partizioni di n in 2 parti non nulle è Formula per i numero di partizioni di n in 2 parti non nulle.

Il numero di partizioni di n in 3 parti anche nulle è l’intero più vicino a Formula per i numero di partizioni di n in 3 parti anche nulle, ovvero Formula per i numero di partizioni di n in 3 parti anche nulle, che è anche il numero di partizioni di n in parti uguali a 1, 2 o 3 (De Morgan, 1843).

Il numero di partizioni di n in 3 parti non nulle è l’intero più vicino a Formula per i numero di partizioni di n in 3 parti non nulle, ovvero Formula per i numero di partizioni di n in 3 parti non nulle (De Morgan, 1843).

Il numero di partizioni di n in 4 parti non nulle è l’intero più vicino a Formula per i numero di partizioni di n in 4 parti non nulle (De Morgan, 1843).

 

In generale il numero di partizioni in al massimo k parti è dato da m polinomi di grado k – 1, dove m è il minimo comune multiplo degli interi da 1 a k, uno per ogni possibile resto ottenuto dividendo n per k. In alcuni casi, come quelli mostrati sopra, è possibile raggruppare tali polinomi in un’unica formula.

 

Il numero di partizioni di n in esattamente m parti e uguale al numero di partizioni di n con la parte massima uguale a m.

Il numero di partizioni di n in al massimo m parti e uguale al numero di partizioni di n con parti non superiori a m.

 

Il numero di partizioni di n in m parti, tutte maggiori di 1, con esattamente r parti dispari è uguale al numero di partizioni di n, con parte massima uguale a 2k + 1 meno il doppio del numero di parti.

 

Il numero di partizioni di n in parti dispari, la massima delle quali uguale a 2k + 1, è uguale a V2k + 1(n) + V2k(n), dove V2k(n) è il numero di partizioni di n in parti distinte, nelle quali la parte massima meno il numero di parti è uguale a k. (N.J. Fine).

 

Il numero di partizioni di n in m parti tutte maggiori di 1, con r parti dispari distinte è uguale al numero di partizioni di n, con parte massima uguale a 2m ed esattamente r parti dispari, tutte distinte.

 

Il numero di partizioni di n in un numero pari di interi distinti meno il numero di partizioni di n in un numero dispari di interi distinti è (–1)k, se n è un numero pentagonale generalizzato, ossia è della forma Formula per i numeri pentagonali generalizzati, 0 altrimenti (Eulero; per la dimostrazione si veda Mathematical gems III, citato nella bibliografia).

Se consideriamo solo le partizioni in interi congruenti a 0, a t o a –t modulo 2k + 1, il numero di partizioni di n in un numero pari di interi distinti meno il numero di partizioni di n in un numero dispari di interi distinti è (–1)m, se Condizione per n, 0 altrimenti.

 

Per i numeri pentagonali, cioè della forma Formula per i numeri pentagonali, il numero di partizioni in un numero pari di parti è superiore o inferiore al numero di partizioni in un numero dispari di parti, a seconda che n sia pari o dispari, mentre per i numeri non di tale forma i due numeri di partizioni sono uguali (Legendre, 1830).

 

La funzione generatrice per il numero di partizioni in al massimo m parti, non superiori a r è Funzione generatrice per il numero di partizioni in al massimo m parti, non superiori a r.

 

Indicando con p(n, k, m) il numero di partizioni di n in k interi (anche nulli) non superiori a m, valgono le formule:

  • p(nm, k – 1, m) = p(nk, m – 1, k);

  • p(n, k, m) = p(n, k – 1, m) + p(nk, k, m – 1).

 

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.