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 ${\displaystyle s(n,k)}$ (s minuscola) sono definiti come i coefficienti dello sviluppo polinomiale del fattoriale decrescente di x con n fattori:

${\displaystyle (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

${\displaystyle \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 ${\displaystyle \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

${\displaystyle s(n,k)=[(-1)^{n-k}]\times \left[{\frac {n!}{(k-1)!\times 2^{n-k}}}\right]\times }$

${\displaystyle [{(1/(n-k)!)}\times n^{n-k-1}}$

${\displaystyle -{(1/6)\times (1/(n-k-2)!)}\times n^{n-k-2}}$

${\displaystyle +{(1/72)\times (1/(n-k-4)!)}\times n^{n-k-3}}$

${\displaystyle -{(1/6480)\times (5/(n-k-6)!-36/(n-k-4)!)}\times n^{n-k-4}}$

${\displaystyle +{(1/155520)\times (5/(n-k-8)!-144/(n-k-6)!)}\times n^{n-k-5}}$

${\displaystyle -{(1/6531840)\times (7/(n-k-10)!-504/(n-k-8)!+2304/(n-k-6)!)}\times n^{n-k-6}}$

${\displaystyle +{(1/1175731200)\times (35/(n-k-12)!-5040/(n-k-10)!+87264/(n-k-8)!)}\times n^{n-k-7}}$

${\displaystyle -{(1/7054387200)\times (5/(n-k-14)!-1260/(n-k-12)!+52704/(n-k-10)!-186624/(n-k-8)!)}\times n^{n-k-8}}$

${\displaystyle +{(1/338610585600)\times (5/(n-k-16)!-2016/(n-k-14)!+164736/(n-k-12)!-2156544/(n-k-10)!)}\times n^{n-k-9}}$

${\displaystyle -...]}$

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 ${\displaystyle 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:

${\displaystyle \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.

${\displaystyle 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:

${\displaystyle 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 ${\displaystyle S_{n}^{(k)}}$ o ${\displaystyle \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

${\displaystyle \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

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

${\displaystyle \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

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

Bibliografia

• (EN) Rosen Kenneth H., Handbook of Discrete and Combinatorial Mathematics, Boca Raton, CRC Press, 2018, ISBN 978-1-5848-8780-5.
• (EN) Mansour Toufik; Schork Mathias, Commutation Relations, Normal Ordering, and Stirling Numbers, Boca Raton, CRC Press, 2015, ISBN 978-1-4665-7989-7.

Voci correlate

• Polinomi di Bell
• Numero di Catalan
• Cicli e punti fissi
• Fattoriale crescente
• Sequenza polinomiale
• Polinomio di Touchard
• Permutazione di Stirling