# Nombres de Stirling

En matemàtiques, els nombres de Stirling apareixen en una gran varietat de problemes analítics i combinatoris. Reben el seu nom del matemàtic escocès James Stirling, qui els va introduir en el segle xviii. Existeixen dos conjunts diferents de nombres de Stirling: els de primera espècie i els de segona espècie.

## Notació

S'utilitzen diferents notacions per als nombres de Stirling. En general, els nombres de Stirling de primera espècie s'escriuen amb uns s minúscula, mentre que pels de segona espècie es fa servir una S majúscula. Els nombres de Stirling de segona espècie no són mai negatius, però els de primera espècie poden ser positius i negatius: per això també s'utilitza una notació específica per als nombres de primera espècie sense signe (en valor absolut). Les notacions comunament utilitzades són:
    $s(n,k)\,$ per als nombres de Stirling de primera espècie (amb el seu signe),
    $c(n,k)=\left[{n \atop k}\right]=|s(n,k)|\,$ per als nombre de Stirling de primera espècie en valor absolut, (sense signe), i
    $S(n,k)=\left\{{\begin{matrix}n\\k\end{matrix}}\right\}=S_{n}^{(k)}\,$ per als nombre de Stirling de segona espècie.
Alguns autors fan servir una $S$ majúscula i una ${\mathfrak {S}}$ gòtica, respectivament, pels nombres de primera i segona espècie. La notació amb claus i claudàtors, en analogia amb els coeficients binomials, va ser introduïda el 1935 per Jovan Karamata i promoguda després per Donald Knuth.

## Nombres de Stirling de primera espècie

Els Nombres de Stirling sense signe de primera espècie compten el nombre de permutacions de n elements en k cicles disjunts. Per exemple, si considerem el conjunt $(1,2,3,4)$, pot ser dividit en dos cicles de les següents onze formes:
    $[1,2,3],[4]$ — $[1,3,2],[4]$ — $[1,2,4],[3]$ — $[1,4,2],[3]$ — $[1,3,4],[2]$ — $[1,4,3],[2]$
    $[2,3,4],[1]$ — $[2,4,3],[1]$ — $[1,2],[3,4]$ — $[1,3],[2,4]$ — $[1,4],[2,3]$
És a dir: $|s(4,2)|=11$, i, en general:
    $c(n,k)=\left[{n \atop k}\right]=|s(n,k)|=(-1)^{n-k}s(n,k)$
És fàcil comprovar que $|s(n,n)|=1$ i que $|s(n,1)|=(n-1)!$.
Els nombres de Stirling de primera espècie en general (que inclouen nombres negatius) són els coeficients de l'expansió de:
    $(x)_{n}=\sum _{k=0}^{n}s(n,k)x^{k}.$
on $(x)_{n}$ (un símbol de Pochhammer) denota el factorial descendent: $(x)_{n}=x(x-1)(x-2)\cdots (x-n+1).$
Noti's que $x_{0}=1$ perquè és un prodducte buit. En combinatòria també s'utilitza a vegades la notació $x^{\underline {n\!}}$ per a factorial descendent, i $x^{\overline {n\!}}$ per al factorial ascendent.
Uns pocs dels nombres de Stirling de primera espècie s'il·lustren en la taula següent:
    ${\begin{array}{ccccccccccc}&&&&&~~1~~&&&&&\\&&&&-1&&~~1~~&&&&\\&&&2&&-3&&~~1~~&&&\\&&-6&&11&&-6&&~~1~~&&\\&24&&-50&&35&&-10&&~~1~~&\\-120&&274&&-225&&85&&-15&&~~1~~\\\end{array}}$
en la que
    $s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)$

## Nombres de Stirlig de segona espècie

Els nombres de Stirlig de segona espècie compten el nombre de formes de partir un conjunt de $n$ elements entre $k$ subconjunts no buits. Per exemple, el conjunt $\{1,2,3,4\}$ pot partir-se en dos subconjunts no buits de les següents set formes:
    $\{1,2,3\}\cup \{4\}$ — $\{1,2,4\}\cup \{3\}$ — $\{1,3,4\}\cup \{2\}$ — $\{2,3,4\}\cup \{1\}$
    $\{1,2\}\cup \{3,4\}$ — $\{1,3\}\cup \{2,4\}$ — $\{1,4\}\cup \{2,3\}$
Per això, $S(4,2)=7$.
És fàcil comprovar que $S(n,1)=1$ i que $S(n,n)=1$.
Es denoten com $S(n,k)$ o $\textstyle \lbrace {n \atop k}\rbrace$. La suma
    $\sum _{k=0}^{n}S(n,k)=B_{n}$
és l'enèsim nombre de Bell.
Utilitzant els factorials descendents, podem caracteritzar els nombres de Stirling de segona espècie amb la identitat:
    $\sum _{k=0}^{n}S(n,k)(x)_{k}=x^{n}.$

## Nombres de Lah

Els nombres de Lah $L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}$ es denominen sovint nombres de Stirling de tercera espècie.

## Relació inversa

Els nombres de Stirling de primera i segona espècie poden ser considerats com inversos els uns dels altres:
    $\sum _{j=0}^{n}s(n,j)S(j,k)=\delta _{nk}$
i
    $\sum _{j=0}^{n}S(n,j)s(j,k)=\delta _{nk},$
on $\delta _{nk}$ és la delta de Kronecker. Aquestes dues relacions es poden entendre com si fossin relacions entre matrius inverses. És a dir, sigui $s$ la més petita matriu triangular, amb elements de la matriu $s_{nk}=s(n,k).\,$. La seva matriu inversa, $S$, serà la més petita matriu triangular dels nombres de Stirling de segona espècie, amb elements de la matriu $S_{nk}=S(n,k).$.
Simbòlicament es pot escriure:
    $s^{-1}=S\,$
Encara que $s$ i $S$ són infinites, o sigui que calcular un producte involucra una suma infinita, el producte d'aquestes matrius es pot obtenir perquè són mínimes triangulars i només un nombre finit de termes de la suma són diferents de zero.
Una generalització d'aquesta relació d'inversió proporciona l'enllaç amb els nombres de Lah $L(n,k):$
    $(-1)^{n}L(n,k)=\sum _{z}(-1)^{z}s(n,z)S(z,k),$
amb les convencions $L(0,0)=1$ i $L(n,k)=0$ si $k>n$.

## Fórmules simètriques

Les segúents fórmules simètriques relacionen els nombres de Stirlig de primera i de segona espècie:
    $s(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}S(n-k+j,j)$
i
    $S(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}s(n-k+j,j).$

## Referències

* ↑ Goldberg, Newman i Haynsworth, pàgina 824
* ↑ Aigner, Martin. A Course In Enumeration (en anglès). Springer, 2007, p. 38. ISBN 9783540390350.
* ↑ Gossett, pàgina 424. Definició 8.7
* ↑ Graham, Ronald L; Knuth, Donald E; Patashnik, Oren. Concrete Mathematics. Reading MA: Addison-Wesley, 1988, p. 244.. ISBN 0-201-14236-8.
* ↑ Sandor, Jozsef; Crstici, B. Handbook of Number Theory II, Volume 2. Dordrecht: Kluwer Academic, 2004, p. 464. ISBN 1-4020-2546-7.

## Bibliografia

* Goldberg, M.; Newman, M; Haynsworth, E. «Combinatorial Analysis». A: Milton Abramowitz; Irene A. Stegun (eds.). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (en anglès). Washington: National Bureau of Standards, 1972, p. 821-874.
* Adamchik, Victor «Còpia arxivada». Journal of Computational and Applied Mathematics, Vol. 79, 1997, pàg. 119-130. Arxivat de l'original el 2009-06-16 [Consulta: 26 desembre 2014]. Arxivat 2009-06-16 a Wayback Machine.
* Gossett, Eric. Discrete Mathematics with Proof (en anglès). Willey and Sons, 2009. ISBN 978-0-170-45793-1.

## Enllaços externs

* Stirling numbers of the first kind, s(n,k) a PlanetMath.
* Stirling numbers of the second kind, S(n,k) a PlanetMath.