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