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

Stirling di seconda specie (numeri di)

Matematica combinatoria 

Indice

  1. 1. Pagina principale
  2. 2. Formule
  3. 3. Valori

I numeri di Stirling devono il nome al matematico scozzese James Stirling (Garden, Scozia, 5/1692 – Edinburgo, Scozia, 5/12/1770), che li introdusse nel 1730.

 

I numeri di Stirling di seconda specie sono generalmente indicati come Numero di Stirling di seconda specie S(n, k) o come S(n, k).

 

Sono utilizzati in matematica combinatoria (v. anche numero di composizioni).

 

Il numero di Stirling di seconda specie Numero di Stirling di seconda specie S(n, k) è il numero di modi in cui n oggetti distinguibili possono essere suddivisi tra k sottoinsiemi disgiunti e non vuoti.

Per esempio, Numero di Stirling di seconda specie S(4, 2), perché 4 oggetti possono essere suddivisi tra esattamente 2 sottoinsiemi in 7 modi differenti:

  • { { 1, 2, 3 }, { 4 } };

  • { { 1, 2, 4 }, { 3 } };

  • { { 1, 3, 4 }, { 2 } };

  • { { 2, 3, 4 }, { 1 } };

  • { { 1, 2 }, { 3, 4 } };

  • { { 1, 3 }, { 2, 4 } };

  • { { 1, 4 }, { 2, 3 } }.

 

Dalla definizione si ricava che Numero di Stirling di seconda specie S(n, k) è il numero di modi nei quali si possono suddividere n punti fissati lungo una circonferenza a formare i vertici di k poligoni convessi distinti (parzialmente sovrapposti), ammettendo poligoni degeneri formati da un solo punto o da due e dal segmento che li unisce.

 

Analogamente Numero di Stirling di seconda specie S(n, k) è il numero di possibili schemi di rima di n versi con k rime diverse.

 

Se gli oggetti sono numerati, come nell’esempio precedente, e si aggiunge la condizione che tra due oggetti dello stesso insieme vi sia una differenza almeno uguale a d, il numero di possibili suddivisioni è dato dai numeri di Stirling di seconda specie ridotti, indicati di solito come Sd(n, k) e legati ai numeri di Stirling di seconda specie dalla relazione Formula per il numero di Stirling di seconda specie ridotto Sd(n, k). Per esempio, vi sono Numero di Stirling di seconda specie ridotto S2(6, 3) modi di dividere gli interi da 1 a 6 in 3 insiemi non vuoti, in modo che gli interi di ogni insieme abbiano differenza almeno uguale a 2:

  • { { 1 }, { 2, 4, 6 }, { 3, 5 } };

  • { { 1, 3 }, { 2, 4, 6 }, { 5 } };

  • { { 1, 3 }, { 2, 5 }, { 4, 6 } };

  • { { 1, 3, 5 }, { 2 }, { 4, 6 } };

  • { { 1, 3, 5 }, { 2, 4 }, { 6 } }.

  • { { 1, 3, 5 }, { 2, 6 }, { 4 } };

  • { { 1, 3, 6 }, { 2, 4 }, { 5 } };

  • { { 1, 3, 6 }, { 2, 5 }, { 4 } };

  • { { 1, 4 }, { 2, 5 }, { 3, 6 } };

  • { { 1, 4 }, { 2, 6 }, { 3, 5 } };

  • { { 1, 4, 6 }, { 2 }, { 3, 5 } };

  • { { 1, 4, 6 }, { 2, 5 }, { 3 } };

  • { { 1, 5 }, { 2, 4 }, { 3, 6 } };

  • { { 1, 5 }, { 2, 4, 6 }, { 3 } };

  • { { 1, 6 }, { 2, 4 }, { 3, 5 } }.

 

Numero di Stirling di seconda specie S(n, k) è il numero di sequenze di n interi da 1 a k, tali che ogni intero compaia almeno una volta e la sua prima occorrenza preceda la prima occorrenza del numero superiore. Per esempio, per n = 4 e k = 3 le sequenze sono Numero di Stirling di seconda specie S(4, 3): { 1, 1, 2, 3 }, { 1, 2, 1, 3 }, { 1, 2, 3, 1 }, { 1, 2, 2, 3 }, { 1, 2, 3, 2 }, { 1, 2, 3, 3 }.

 

Dato un insieme S di n elementi, il numero di possibili catene di sottoinsiemi Um di lunghezza k (non contando l’insieme vuoto) ∅ = U0U1U2 ⊂ ... Uk – 1Uk = S è k! * S(n, k) e il numero complessivo di catene del genere è Numero di catene di sottoinsiemi, che è uguale al valore della derivata n-esima di 1 / (2 – e^x) calcolata per x = 0 e che si può approssimare con n / (2 * log(2)^(n + 1)).

Se S è l’insieme dei fattori primi di un intero m, prodotto di n fattori primi distinti, si possono far corrispondere alle catene le sequenze di k + 1 interi che iniziano con 1 e terminano con m, tali che ciascuno sia multiplo del precedente. Il numero di sequenze di lunghezza k è allora k! * S(n, k). Per esempio, per m = 70 abbiamo n = 3 e vi sono 1! * S(3, 1) sequenze del genere con 1 intero, 2! * S(3, 2) con 2 e 3! * S(3, 3) con 3, sempre senza contare il numero 1 iniziale:

  • { 1, 70 };

  • { 1, 2, 70 }, { 1, 5, 70 }, { 1, 7, 70 }, { 1, 10, 70 }, { 1, 14, 70 }, { 1, 35, 70 };

  • { 1, 2, 10, 70 }, { 1, 2, 14, 70 }, { 1, 5, 10, 70 }, { 1, 5, 35, 70 }, { 1, 7, 14, 70 }, { 1, 7, 35, 70 }.

Il numero totale di sequenze è Numero totale di sequenze, come nel caso delle catene di insiemi, quindi 13 per n = 3.

 

Il numero di modi nei quali si possono suddividere n oggetti distinti tra k sottoinsiemi disgiunti, distinti e non vuoti è k! * S(n, k). Per esempio, 4 oggetti distinti possono essere suddivisi tra 3 insiemi non vuoti in 3! * S(4, 3) modi distinti:

  • { 1, 2 }, { 3 }, { 4 };

  • { 1, 2 }, { 4 }, { 3 };

  • { 1, 3 }, { 2 }, { 4 };

  • { 1, 3 }, { 4 }, { 2 };

  • { 1, 4 }, { 3 }, { 2 };

  • { 1, 4 }, { 2 }, { 3 };

  • { 2, 3 }, { 1 }, { 4 };

  • { 2, 3 }, { 4 }, { 1 };

  • { 2, 4 }, { 1 }, { 3 };

  • { 2, 4 }, { 3 }, { 1 };

  • { 3, 4 }, { 1 }, { 2 };

  • { 3, 4 }, { 2 }, { 1 };

  • { 4 }, { 1, 2 }, { 3 };

  • { 3 }, { 1, 2 }, { 4 };

  • { 4 }, { 1, 3 }, { 2 };

  • { 2 }, { 1, 3 }, { 4 };

  • { 2 }, { 1, 4 }, { 3 };

  • { 3 }, { 1, 4 }, { 2 };

  • { 4 }, { 2, 3 }, { 1 };

  • { 1 }, { 2, 3 }, { 4 };

  • { 3 }, { 2, 4 }, { 1 };

  • { 1 }, { 2, 4 }, { 3 };

  • { 2 }, { 3, 4 }, { 1 };

  • { 1 }, { 3, 4 }, { 2 };

  • { 3 }, { 4 }, { 1, 2 };

  • { 4 }, { 3 }, { 1, 2 };

  • { 2 }, { 4 }, { 1, 3 };

  • { 4 }, { 2 }, { 1, 3 };

  • { 3 }, { 2 }, { 1, 4 };

  • { 2 }, { 3 }, { 1, 4 };

  • { 1 }, { 4 }, { 2, 3 };

  • { 4 }, { 1 }, { 2, 3 };

  • { 1 }, { 3 }, { 2, 4 };

  • { 3 }, { 1 }, { 2, 4 };

  • { 1 }, { 2 }, { 3, 4 };

  • { 2 }, { 1 }, { 3, 4 }.

 

Il numero di modi nei quali si possono disporre k gettoni su una scacchiera triangolare di lato n, in modo che ve ne sia al massimo 1 per casella e che non ve ne siano 2 sulla stessa riga o colonna è S(n + 1, n – k + 1). Il problema è equivalente a quello di disporre k torri su una scacchiera triangolare di lato n in modo che non si attacchino.

Per esempio, con una scacchiera di lato 3 vi sono:

Numero di Stirling di seconda specie S(4, 4) modi di disporre 0 torri;

Numero di Stirling di seconda specie S(4, 3) modi di disporre 1 torre;

Numero di Stirling di seconda specie S(4, 2) modi di disporre 2 torri;

Numero di Stirling di seconda specie S(4, 1) modi di disporre 3 torri.

La figura seguente mostra queste disposizioni.

Disposizioni di torri su una scacchiera triangolare

Bibliografia

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