Numeri di Stirling

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

In matematica, i numeri di Stirling sono delle quantità che si incontrano in vari campi della combinatoria. Prendono il loro nome dal matematico James Stirling.

I numeri di Stirling di prima specie (s minuscola) sono definiti come i coefficienti dello sviluppo polinomiale del fattoriale decrescente di x con n fattori:

I numeri di Stirling di prima specie senza segno sono definiti invece da

e rappresentano il numero di possibili permutazioni di n elementi in k cicli disgiunti.

Sono talvolta scritti con la notazione alternativa .

Tavola di valori

[modifica | modifica wikitesto]
n \ k 0 1 2 3 4 5 6 7 8 9
0 1
1 0 1
2 0 −1 1
3 0 2 −3 1
4 0 −6 11 −6 1
5 0 24 −50 35 −10 1
6 0 −120 274 −225 85 −15 1
7 0 720 −1764 1624 −735 175 −21 1
8 0 −5040 13068 −13132 6769 −1960 322 −28 1
9 0 40320 −109584 118124 −67284 22449 −4536 546 −36 1

Formula esplicita

[modifica | modifica wikitesto]

Sorgente: André F. Labossière, 2006-03-27, A008275 ( OEIS - The On-Line Encyclopedia of Integer Sequences )

Seconda specie

[modifica | modifica wikitesto]

I numeri di Stirling di seconda specie (S maiuscola) sono definiti come il numero di possibili k-partizioni (cioè partizioni fatte da k insiemi) di un insieme di cardinalità n. Valgono le relazioni:

e

L'immagine mostra un esempio di funzione suriettiva tra due insiemi: il primo di cardinalità n=8 e il secondo di cardinalità k=3. La funzione è stata costruita partizionando in 3 blocchi l'insieme di 8 ed associando ad ogni blocco uno dei 3 elementi del secondo insieme.

dove Bn è l'n-esimo numero di Bell.

Inoltre, è possibile ricavare una formula esplicita per calcolare numeri di Stirling di seconda specie. Si può infatti osservare che il numero di funzioni suriettive da un insieme di cardinalità n ad uno di cardinalità k può essere individuato partizionando il dominio (di cardinalità n) in k blocchi e associando ad ognuno di questi blocchi uno dei k elementi del codominio (e ciò si può fare in k! modi). Così si ricava la formula:

Sono talvolta scritti in notazione alternativa come o . Come per la prima specie, l'idea di usare parentesi, in analogia con il coefficiente binomiale, è venuta per la prima volta a Jovan Karamata nel 1935 ed è stata supportata poi da Donald Knuth; è per questo nota come "notazione Karamata".

Tavola di valori

[modifica | modifica wikitesto]
n \ k 0 1 2 3 4 5 6 7 8 9
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1
  • I numeri di prima e seconda specie sono legati dalle relazioni

e

dove è il delta di Kronecker. Queste relazioni possono essere interpretate come segue: la matrice è l'inversa della matrice , e analogamente la matrice è l'inversa della matrice .

  • Abramowitz e Stegun inoltre hanno dato le seguenti formule che legano tra loro i due tipi di numeri:

e

.

Voci correlate

[modifica | modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica