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

Composizioni (numero di)

Matematica combinatoria 

Il numero di composizioni di un numero naturale n è il numero di modi distinti per ottenere n come somma di interi maggiori di zero, anche ripetuti, contando separatamente i vari ordini possibili degli addendi. Per esempio, il numero di composizioni di 4 è 8, perché 4 può essere ottenuto come somma di interi nei seguenti modi:

  • 4,

  • 3 + 1,

  • 1 + 3,

  • 2 + 2,

  • 2 + 1 + 1,

  • 1 + 2 + 1,

  • 1 + 1 + 2,

  • 1 + 1 + 1 + 1.

 

Il numero k compare (nk + 3)2 – k – 2 volte nelle composizioni di n; per esempio, 2 compare 5 volte nelle composizioni di 4.

 

Il numero di composizioni di n è:

  • 2n – 1, metà delle quali con un numero pari di parti pari;

  • Numero di composizioni di n con k parti anche nulle, con k parti anche nulle (ossia k parti al massimo);

  • Numero di composizioni di n con esattamente k parti non minori di m, con esattamente k parti non minori di m; e in particolare Numero di composizioni di n con esattamente k parti non nulle con esattamente k parti non nulle;

  • Numero di composizioni di n con esattamente k parti non nulle e distinte, con esattamente k parti non nulle e distinte;

  • il numero di Fibonacci Fn – 1, se le parti sono maggiori di 1;

  • il numero Gm, n – 1, se le parti sono maggiori o uguali a m, dove Gm, n è definito dalla ricorrenza Gm, n = Gm, n – 1 + Gm, nm, con G0, m = G1, m = ... = Gm – 2, m = 0 e Gm, m – 1 = 1;

  • il numero di Fibonacci Fn + 1, se le parti sono uguali a 1 o 2;

  • il numero di tribonacci Tn + 1, se le parti sono uguali a 1, 2 o 3;

  • il numero di Padovan Pn – 2, se le parti sono uguali a 2 o 3;

  • il numero di Fibonacci Fn, se le parti sono dispari;

  • il numero di Padovan Pn – 5, se le parti sono dispari e maggiori di 1;

  • il numero di Padovan Pn – 4, se le parti sono della forma 3m + 2;

  • il numero di Padovan P2n – 2, se le parti sono diverse da 2;

  • il numero di Padovan Pn, se le parti sono diverse da 2 e la composizione è palindroma;

  • il numero di Jacobsthal Jn, se l'ultima parte è dispari;

  • il numero di Jacobsthal Jn – 1, se l'ultima parte è pari.

Il numero di composizioni di n in k parti non nulle tende, per n tendente a infinito, a Limite cui tende il numero di composizioni di n con k parti non nulle, se k cresce più lentamente della radice cubica di n (Erdös).

 

Se moltiplichiamo i numeri che compaiono in ogni singola composizione di n e sommiamo i prodotti, otteniamo il numero di Fibonacci F2n. Per esempio, nel caso n = 4 abbiamo 4 + 3 · 1 + 1 · 3 + 2 · 2 + 2 · 1 · 1 + 1 · 2 · 1 + 1 · 1 · 2 + 1 · 1 · 1 · 1 = 21 = F8.

 

Se calcoliamo 2k, dove k è il numero di 1 in una composizione di n e sommiamo i risultati per tutte le composizioni, otteniamo il numero di Fibonacci F2n + 1. Per esempio, nel caso n = 4 abbiamo 20 + 21 + 21 + 20 + 22 + 22 + 22 + 24 = 1 + 2 + 2 + 1 + 4 + 4 + 4 + 16 = 34 = F9.

 

Se moltiplichiamo 2k – 1 – 1 per ogni valore di k che compare in ogni singola composizione di n (notate che se un valore di k è zero, il prodotto si annulla) e sommiamo i prodotti, otteniamo il numero di Fibonacci F2n – 2. Per esempio, nel caso n = 4 abbiamo 7 + 3 • 0 + 0 • 3 + 1 • 1 + 1 • 0 • 0 + 0 • 1 • 0 + 0 • 0 • 1 + 0 • 0 • 0 • 0 = 8 = F6.

 

Se moltiplichiamo m elevato alla a(k) meno 1 per ogni valore di am che compare in una singola composizione di n (con m che va da 1 a k) e sommiamo i prodotti relativi alle composizioni con k addendi, otteniamo il numero di Stirling di seconda specie Numero di Stirling di seconda specie S(n, k). Per esempio, nel caso n = 4 abbiamo Somma dei prodotti relativi alle composizioni di 4 con 1 addendo per le composizioni con un addendo, Somma dei prodotti relativi alle composizioni di 4 con 2 addendi per quelle con due addendi, Somma dei prodotti relativi alle composizioni di 4 con 3 addendi per quelle con tre addendi, Somma dei prodotti relativi alle composizioni di 4 con 4 addendi per quelle con quattro addendi.

 

Per le composizioni moltiplicative si veda la costante di Kalmar.

 

  • il numero di Padovan Pn – 2, se le parti sono uguali a 2 o 3;

  • il numero di Fibonacci Fn, se le parti sono dispari;

  • il numero di Padovan Pn – 5, se le parti sono dispari e maggiori di 1;

  • il numero di Padovan Pn – 4, se le parti sono della forma 3m + 2;

  • il numero di Padovan P2n – 2, se le parti sono diverse da 2;

  • il numero di Padovan Pn, se le parti sono diverse da 2 e la composizione è palindroma;

  • il numero di Jacobsthal Jn, se l'ultima parte è dispari;

  • il numero di Jacobsthal Jn – 1, se l'ultima parte è pari.

 

Bibliografia

  • Andrews, G.E.;  The Theory of Partitions, Cambridge University Press, 1984.
  • Koshy, Thomas;  Fibonacci and Lucas Numbers with Applications, New York, John Wiley & Sons, 2001.
  • Stanley, Richard P.;  Enumerative Combinatorics, Cambridge University Press, vol. I, 1997.

Contattami

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