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:

${\displaystyle s(n,k)\,}$ per als nombres de Stirling de primera espècie (amb el seu signe),

${\displaystyle 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

${\displaystyle 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^[1] fan servir una ${\displaystyle S}$ majúscula i una ${\displaystyle {\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 ${\displaystyle (1,2,3,4)}$, pot ser dividit en dos cicles de les següents onze formes:

${\displaystyle [1,2,3],[4]}$ — ${\displaystyle [1,3,2],[4]}$ — ${\displaystyle [1,2,4],[3]}$ — ${\displaystyle [1,4,2],[3]}$ — ${\displaystyle [1,3,4],[2]}$ — ${\displaystyle [1,4,3],[2]}$

${\displaystyle [2,3,4],[1]}$ — ${\displaystyle [2,4,3],[1]}$ — ${\displaystyle [1,2],[3,4]}$ — ${\displaystyle [1,3],[2,4]}$ — ${\displaystyle [1,4],[2,3]}$

És a dir: ${\displaystyle |s(4,2)|=11}$, i, en general:

${\displaystyle c(n,k)=\left[{n \atop k}\right]=|s(n,k)|=(-1)^{n-k}s(n,k)}$

És fàcil comprovar que ${\displaystyle |s(n,n)|=1}$ i que ${\displaystyle |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:

${\displaystyle (x)_{n}=\sum _{k=0}^{n}s(n,k)x^{k}.}$

on ${\displaystyle (x)_{n}}$ (un símbol de Pochhammer) denota el factorial descendent: ${\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1).}$

Noti's que ${\displaystyle x_{0}=1}$ perquè és un prodducte buit. En combinatòria també s'utilitza a vegades la notació ${\displaystyle x^{\underline {n\!}}}$ per a factorial descendent, i ${\displaystyle x^{\overline {n\!}}}$ per al factorial ascendent.^[2]

Uns pocs dels nombres de Stirling de primera espècie s'il·lustren en la taula següent:

${\displaystyle {\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

${\displaystyle 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 ${\displaystyle n}$ elements entre ${\displaystyle k}$ subconjunts no buits.^[3] Per exemple, el conjunt ${\displaystyle \{1,2,3,4\}}$ pot partir-se en dos subconjunts no buits de les següents set formes:

${\displaystyle \{1,2,3\}\cup \{4\}}$ — ${\displaystyle \{1,2,4\}\cup \{3\}}$ — ${\displaystyle \{1,3,4\}\cup \{2\}}$ — ${\displaystyle \{2,3,4\}\cup \{1\}}$

${\displaystyle \{1,2\}\cup \{3,4\}}$ — ${\displaystyle \{1,3\}\cup \{2,4\}}$ — ${\displaystyle \{1,4\}\cup \{2,3\}}$

Per això, ${\displaystyle S(4,2)=7}$.

És fàcil comprovar que ${\displaystyle S(n,1)=1}$ i que ${\displaystyle S(n,n)=1}$.

Es denoten com ${\displaystyle S(n,k)}$ o ${\displaystyle \textstyle \lbrace {n \atop k}\rbrace }$.^[4] La suma

${\displaystyle \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:

${\displaystyle \sum _{k=0}^{n}S(n,k)(x)_{k}=x^{n}.}$

Nombres de Lah

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

Relació inversa

Els nombres de Stirling de primera i segona espècie poden ser considerats com inversos els uns dels altres:

${\displaystyle \sum _{j=0}^{n}s(n,j)S(j,k)=\delta _{nk}}$

i

${\displaystyle \sum _{j=0}^{n}S(n,j)s(j,k)=\delta _{nk},}$

on ${\displaystyle \delta _{nk}}$ és la delta de Kronecker. Aquestes dues relacions es poden entendre com si fossin relacions entre matrius inverses. És a dir, sigui ${\displaystyle s}$ la més petita matriu triangular, amb elements de la matriu ${\displaystyle s_{nk}=s(n,k).\,}$. La seva matriu inversa, ${\displaystyle S}$, serà la més petita matriu triangular dels nombres de Stirling de segona espècie, amb elements de la matriu ${\displaystyle S_{nk}=S(n,k).}$.

Simbòlicament es pot escriure:

${\displaystyle s^{-1}=S\,}$

Encara que ${\displaystyle s}$ i ${\displaystyle 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 ${\displaystyle L(n,k):}$

${\displaystyle (-1)^{n}L(n,k)=\sum _{z}(-1)^{z}s(n,z)S(z,k),}$

amb les convencions ${\displaystyle L(0,0)=1}$ i ${\displaystyle L(n,k)=0}$ si ${\displaystyle 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:

${\displaystyle 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

${\displaystyle 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

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.