Numeri di Stirling
# 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]$.
