Numeri di Stirling

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

I numeri di Stirling di prima specie $s(n,k)$ (s minuscola) sono definiti come i coefficienti dello sviluppo 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

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

$s(n,k)=[(-1)^{n-k}]\times \left[{\frac {n!}{(k-1)!\times 2^{n-k}}}\right]\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

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 di cardinalità n. Valgono le relazioni:

$\sum _{k=0}^{n}S(n,k)(x)_{k}=x^{n}$

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.

$B_{n}=\sum _{k=1}^{n}S(n,k)$

dove B_n è 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:

$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

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

• I numeri di prima e seconda specie sono legati dalle relazioni

$\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]\left\{{\begin{matrix}k\\m\end{matrix}}\right\}(-1)^{k}=(-1)^{n}\delta _{mn}$

e

$\sum _{k=0}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}\left[{\begin{matrix}k\\m\end{matrix}}\right](-1)^{k}=(-1)^{n}\delta _{mn}$

dove $\delta _{jk}$ è il delta di Kronecker. Queste relazioni possono essere interpretate come segue: la matrice $(-1)^{n-k}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$ è l'inversa della matrice $\left[{\begin{matrix}n\\k\end{matrix}}\right]$, e analogamente la matrice $(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]$ è l'inversa della matrice $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$.

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