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 nome da James Stirling.

Indice

1 Prima specie
- 1.1 Tavola di valori
2 Seconda specie
- 2.1 Tavola di valori
3 Relazioni

[modifica] Prima specie

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]$ .

[modifica] Tavola di valori

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

[modifica] Seconda specie

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$

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

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

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

[modifica] Tavola di valori

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

[modifica] Relazioni

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}$

$\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 $δ j k$ è 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\}$

$\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]$ .