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).$

Notis 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).$

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 Journal of Computational and Applied Mathematics, Vol. 79, 1997, pàg. 119-130.
• 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.