Numeri di Stirling

Template:F 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

$|s(n,k)|=(-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{array}{c}n\\ k\end{array}\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}(\genfrac{}{}{0ex}{}{k}{j})j^n$

Sono talvolta scritti in notazione alternativa come $S_n^{(k)}$ o $\left\{\begin{array}{c}n\\ k\end{array}\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{array}{c}n\\ k\end{array}\right]\left\{\begin{array}{c}k\\ m\end{array}\right\}(-1{)}^k=(-1{)}^n{\delta }_{mn}$

e

$\sum _{k=0}^n\left\{\begin{array}{c}n\\ k\end{array}\right\}\left[\begin{array}{c}k\\ m\end{array}\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{array}{c}n\\ k\end{array}\right\}$ è l'inversa della matrice $\left[\begin{array}{c}n\\ k\end{array}\right]$, e analogamente la matrice $(-1{)}^{n-k}\left[\begin{array}{c}n\\ k\end{array}\right]$ è l'inversa della matrice $\left\{\begin{array}{c}n\\ k\end{array}\right\}$.

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

$\left[\begin{array}{c}n\\ k\end{array}\right]=\sum _{j=0}^{n-k}(-1{)}^j(\genfrac{}{}{0ex}{}{n-1+j}{n-k+j})(\genfrac{}{}{0ex}{}{2n-k}{n-k-j})\left\{\begin{array}{c}n-k+j\\ j\end{array}\right\}$

e

$\left\{\begin{array}{c}n\\ k\end{array}\right\}=\sum _{j=0}^{n-k}(-1{)}^j(\genfrac{}{}{0ex}{}{n-1+j}{n-k+j})(\genfrac{}{}{0ex}{}{2n-k}{n-k-j})\left[\begin{array}{c}n-k+j\\ j\end{array}\right]$.

Bibliografia

• Template:Cita libro
• Template:Cita libro

Voci correlate

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