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 Plantilla:Segle. 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[\genfrac{}{}{0ex}{}{n}{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{array}{c}n\\ k\end{array}\right\}=S_n^{(k)}$ per als nombre de Stirling de segona espècie.

Alguns autors fan servir una $S$ majúscula i una $𝔖$ 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[\genfrac{}{}{0ex}{}{n}{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^{\underset{\_}{n}}$ per a factorial descendent, i $x^{\bar{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 $\{\genfrac{}{}{0ex}{}{n}{k}\}$. 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)=(\genfrac{}{}{0ex}{}{n-1}{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(\genfrac{}{}{0ex}{}{n-1+j}{n-k+j})(\genfrac{}{}{0ex}{}{2n-k}{n-k-j})S(n-k+j,j)$

i

$S(n,k)=\sum _{j=0}^{n-k}(-1{)}^j(\genfrac{}{}{0ex}{}{n-1+j}{n-k+j})(\genfrac{}{}{0ex}{}{2n-k}{n-k-j})s(n-k+j,j).$

Bibliografia

• Plantilla:Ref-llibre
• Plantilla:Ref-publicació Plantilla:Webarchive
• Plantilla:Ref-llibre

Enllaços externs

• Plantilla:Planetmath reference.
• Plantilla:Planetmath reference.