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

Stirling di prima 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 prima specie sono generalmente indicati come Numero di Stirling di prima specie s(n, k), Numero di Stirling di prima specie s(n, k) o s(n, k); la notazione s(n, k) è spesso usata per i numeri di Stirling con segno: Formula per ll definizione dei numeri di Stirling di prima specie con segno.

 

Sono utilizzati in matematica combinatoria.

 

Immaginiamo di avere n punti numerati sul piano e di volerli collegare a formare cicli disgiunti; per esempio, se colleghiamo il punto numero 1 al 2, il 2 al 3 e questo al primo, formiamo un ciclo di 3, che indicheremo con { 1, 2, 3 }. Tale ciclo equivale al ciclo { 3, 1, 2 }, perché il punto di partenza del ciclo è irrilevante, ma non al ciclo { 1, 3, 2 }, perché l’ordine di percorrenza del ciclo è differente, pur essendo uguale il percorso.

Il numero di Stirling di prima specie Numero di Stirling di prima specie s(n, k) è il numero di modi in cui n oggetti possono essere suddivisi tra k cicli non vuoti.

Per esempio, Numero di Stirling di prima specie s(4, 2) e 4 oggetti possono essere suddivisi tra esattamente 2 cicli non vuoti in 11 modi differenti:

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

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

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

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

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

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

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

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

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

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

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

 

Come si vede dall’esempio, sono ammessi cicli formati da un solo oggetto.

 

Il numero di Stirling di prima specie Numero di Stirling di prima specie s(n, k) è il numero di permutazioni dei primi n interi nelle quali esattamente k interi sono maggiori di tutti i precedenti (incluso il numero in prima posizione).

Per esempio, vi sono Numero di Stirling di prima specie s(4, 2) permutazioni degli interi da 1 a 4 nelle quali 2 sono maggiori di tutti i precedenti:

  • 1, 4, 2, 3; 1 e 4 sono maggiori dei precedenti;

  • 1, 4, 3, 2; 1 e 4 sono maggiori dei precedenti;

  • 2, 1, 4, 3; 2 e 4 sono maggiori dei precedenti;

  • 2, 4, 1, 3; 2 e 4 sono maggiori dei precedenti;

  • 2, 4, 3, 1; 2 e 4 sono maggiori dei precedenti;

  • 3, 2, 1, 4; 3 e 4 sono maggiori dei precedenti;

  • 3, 2, 4, 1; 3 e 4 sono maggiori dei precedenti;

  • 3, 1, 2, 4; 3 e 4 sono maggiori dei precedenti;

  • 3, 1, 4, 2; 3 e 4 sono maggiori dei precedenti;

  • 3, 4, 2, 1; 3 e 4 sono maggiori dei precedenti;

  • 3, 4, 1, 2; 3 e 4 sono maggiori dei precedenti.

 

Il numero di permutazioni di n elementi prive di cicli di lunghezza k è invece Formula per il numero di permutazioni di n interi prive di cicli di lunghezza k.

 

Il numero di Stirling di prima specie Numero di Stirling di prima specie s(n, k) è il numero di alberi con n nodi nei quali la radice ha k figli.

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.