Numeri di Stirling

Da Wikipedia, l'enciclopedia libera.

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.

Prima specie[modifica | modifica wikitesto]

I numeri di Stirling di prima specie s(n,k) (s minuscola) sono definiti come i coefficienti dell'espansione polinomiale del fattoriale decrescente di x con n fattori:

(x)_n = x(x-1)(x-2)\cdots(x-n+1) = \sum_{k=1}^n s(n,k) x^k

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

\left|s(n,k)\right| = (-1)^{n-k} s(n,k)

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

Sono talvolta scritti con la notazione alternativa \left[\begin{matrix} n \\ k \end{matrix}\right].

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]

s(n,k) = [ (-1)^{n-k} ]
                \times [ \frac{n!}{(k-1)! \times 2^{n-k}} ] \times
[ { (1/(n-k)!) } \times n^{n-k-1}
- { (1/6) \times (1/(n-k-2)!) } \times n^{n-k-2}
+ { (1/72) \times (1/(n-k-4)!) } \times n^{n-k-3}
- { (1/6480) \times (5/(n-k-6)!-36/(n-k-4)!) } \times n^{n-k-4}
+ { (1/155520) \times (5/(n-k-8)!-144/(n-k-6)!) } \times n^{n-k-5}
- { (1/6531840) \times (7/(n-k-10)! -504/(n-k-8)!+2304/(n-k-6)!) } \times n^{n-k-6}
+ { (1/1175731200) \times (35/(n-k-12)!-5040/(n-k-10)!+87264/(n-k-8)!) } \times n^{n-k-7}
- { (1/7054387200) \times (5/(n-k-14)!-1260/(n-k-12)!+52704/(n-k-10)!-186624/(n-k-8)!) } \times n^{n-k-8}
+ { (1/338610585600) \times (5/(n-k-16)!-2016/(n-k-14)!+164736/(n-k-12)!-2156544/(n-k-10)!) } \times n^{n-k-9}
- ... ]

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(n,k) (S maiuscola) sono definiti come il numero di possibili k-partizioni (cioè partizioni fatte da k insiemi) di un insieme con n elementi. Valgono le relazioni:

\sum_{k=0}^n S(n,k)(x)_k=x^n

e

B_n=\sum_{k=1}^n S(n,k)

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

Una forma esplicita per i numeri di Stirling di seconda specie è la seguente:

S(n,k)
=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n
.

Sono talvolta scritti in notazione alternativa come S_n^{(k)} o \left\{\begin{matrix} n \\ k \end{matrix}\right\}. 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

Relazioni[modifica | modifica wikitesto]

  • I numeri di prima e seconda specie sono legati dalle relazioni
\sum_{n=0}^{\max\{j,k\}} 
\left[\begin{matrix} n \\ j \end{matrix}\right]
\left\{\begin{matrix} k \\ n \end{matrix}\right\}
= \delta_{jk}

e

\sum_{n=0}^{\max\{j,k\}} 
\left\{\begin{matrix} n \\ j \end{matrix}\right\}
\left[\begin{matrix} k \\ n \end{matrix}\right]
= \delta_{jk}

dove \delta_{jk} è il delta di Kronecker. Queste relazioni possono essere interpretate in senso matriciale, fissando un qualsiasi N numero naturale: se pensiamo a (s_{nk})_{n=1}^N come la matrice triangolare inferiore con \left[\begin{matrix} n \\ j \end{matrix}\right] all'n-k esimo posto e (S_{nk})_{n=1}^N come la matrice, sempre triangolare inferiore, con \left\{\begin{matrix} n \\ k \end{matrix}\right\} all'n-k esimo posto, allora una matrice è l'inversa dell'altra, cioè
s^{-1}=S.

  • Abramowitz e Stegun inoltre hanno dato le seguenti formule che legano tra loro i due tipi di numeri:
\left[\begin{matrix} n \\ k \end{matrix}\right] =
\sum_{j=0}^{n-k}
(-1)^j
{n-1+j \choose n-k+j} {2n-k \choose n-k-j}
\left\{\begin{matrix} n-k+j \\ j \end{matrix}\right\}

e

\left\{\begin{matrix} n \\ k \end{matrix}\right\} =
\sum_{j=0}^{n-k}
(-1)^j
{n-1+j \choose n-k+j} {2n-k \choose n-k-j}
\left[\begin{matrix} n-k+j \\ j \end{matrix}\right]
.



matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica