Nombres d'Stirling del segon tipus

Les 15 particions d'un conjunt de 4 elements ordenades en un diagrama de Hasse. Hi ha S (4,1),... , S (4, 4) = 1, 7, 6, 1 particions que contenen 1, 2, 3, 4 conjunts.

En matemàtiques, particularment en combinatòria, un nombre d'Stirling del segon tipus (o nombre de partició d'Stirling) és el nombre de maneres de dividir un conjunt de n objectes en k subconjunts no buits i es denota per $S(n,k)$ o https://wikimedia.org/api/rest_v1/media/math/render/svg/ac552d368788269c5efc1e80e92dea8049141a3e. Els nombres de Stirling del segon tipus es produeixen en el camp de les matemàtiques anomenat combinatòria i l'estudi de les particions. Reben el nom de James Stirling.

Els nombres de Stirling del primer i del segon tipus es poden entendre com a inversos els uns dels altres quan es consideren matrius triangulars. Aquest article està dedicat a les especificitats dels números de Stirling del segon tipus. Les identitats que vinculen els dos tipus apareixen a l'article sobre els números d'Stirling.

Definició

Els nombres de Stirling del segon tipus, escrits $S(n,k)$ o $\lbrace \textstyle {n \atop k}\rbrace$ o amb altres anotacions, compta el nombre de maneres de particionar un conjunt $n$ objectes etiquetats en $k$ subconjunts no buits sense etiquetar. De manera equivalent, compten amb precisió el nombre de relacions d'equivalència diferents $k$ classes d'equivalència que es poden definir en un $n$ conjunt d'elements. De fet, hi ha una bijecció entre el conjunt de particions i el conjunt de relacions d'equivalència en un conjunt determinat. Òbviament,

$\left\{{n \atop n}\right\}=1$ per a n ≥ 0, i $\left\{{n \atop 1}\right\}=1$ per a n ≥ 1,

ja que l'única manera de dividir un conjunt d'n elements en n parts és posar cada element del conjunt en la seva pròpia part, i l'única manera de dividir un conjunt no buit en una part és posar tots els elements a la mateixa part.. A diferència dels nombres de Stirling del primer tipus, es poden calcular mitjançant una fórmula d'una suma:

$\left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}i^{n}=\sum _{i=0}^{k}{\frac {(-1)^{k-i}i^{n}}{(k-i)!i!}}.$

Els nombres de Stirling del primer tipus es poden caracteritzar com els nombres que sorgeixen quan s'expressa potències d'una x indeterminada en termes de factorials descendents

$(x)_{n}=x(x-1)(x-2)\cdots (x-n+1).$

(En particular, ( x ) ₀ = 1 perquè és un producte buit).

Els nombres de Stirling del segon tipus satisfan la relació

$\sum _{k=0}^{n}\left\{{n \atop k}\right\}(x)_{k}=x^{n}.$

Propietats

Relació de recurrència

Els nombres de Stirling del segon tipus obeeixen a la relació de recurrència

$\left\{{n+1 \atop k}\right\}=k\left\{{n \atop k}\right\}+\left\{{n \atop k-1}\right\}\quad {\mbox{for}}\;0<k<n$

Fórmula explícita

Els nombres de Stirling del segon tipus es donen per la fórmula explícita:

$\left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}j^{n}=\sum _{j=0}^{k}{\frac {(-1)^{k-j}j^{n}}{(k-j)!j!}}.$

Funcions generadores

Per a un nombre enter fix n, la funció de generació ordinària dels nombres de Stirling del segon tipus $\left\{{n \atop 0}\right\},\left\{{n \atop 1}\right\},\ldots$ està donat per

$\sum _{k=0}^{n}\left\{{n \atop k}\right\}x^{k}=T_{n}(x),$

on $T_{n}(x)$ són polinomis de Touchard.

Taula de valors

A continuació es mostra una matriu triangular de valors per als nombres de Stirling del segon tipus (seqüència A008277) de l'OEIS):

k		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

Aplicacions

Moments de la distribució de Poisson

Si X és una variable aleatòria amb una distribució de Poisson amb valor esperat λ, aleshores el seu moment n és és

$E(X^{n})=\sum _{k=0}^{n}\left\{{n \atop k}\right\}\lambda ^{k}.$

En particular, el moment n -è de la distribució de Poisson amb el valor esperat 1 és precisament el nombre de particions d'un conjunt de mida n, és a dir, és l' ésimo nombre de Bell (aquest fet és la fórmula de Dobiński).

Moments de punts fixos de permutacions aleatòries

Sigui la variable aleatòria X el nombre de punts fixos d'una permutació aleatòria distribuïda uniformement d'un conjunt finit de mida m. Aleshores, el moment n de X és

$E(X^{n})=\sum _{k=0}^{m}\left\{{n \atop k}\right\}.$

Esquemes de rimes

Els nombres de Stirling del segon tipus poden representar el nombre total d'esquemes de rima per a un poema de n línies. $S(n,k)$ dóna el nombre d'esquemes de rima possibles per a n línies utilitzant k síl·labes de rima úniques. Com a exemple, per a un poema de 3 línies, hi ha 1 esquema de rima que utilitza només una rima (aaa), 3 esquemes de rima amb dues rimes (aab, aba, abb) i 1 esquema de rima amb tres rimes (abc).