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 $\{\genfrac{}{}{0ex}{}{n}{k}\}$ 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\{\genfrac{}{}{0ex}{}{n}{n}\right\}=1$ per a n ≥ 0, i $\left\{\genfrac{}{}{0ex}{}{n}{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\{\genfrac{}{}{0ex}{}{n}{k}\right\}=\frac{1}{k!}\sum _{i=0}^k(-1{)}^{k-i}(\genfrac{}{}{0ex}{}{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\{\genfrac{}{}{0ex}{}{n}{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\{\genfrac{}{}{0ex}{}{n+1}{k}\right\}=k\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}+\left\{\genfrac{}{}{0ex}{}{n}{k-1}\right\}\text{for}0<k<n$

Fórmula explícita

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

$\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}=\frac{1}{k!}\sum _{j=0}^k(-1{)}^{k-j}(\genfrac{}{}{0ex}{}{k}{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\{\genfrac{}{}{0ex}{}{n}{0}\right\},\left\{\genfrac{}{}{0ex}{}{n}{1}\right\},\dots$ està donat per

$\sum _{k=0}^n\left\{\genfrac{}{}{0ex}{}{n}{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\{\genfrac{}{}{0ex}{}{n}{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\{\genfrac{}{}{0ex}{}{n}{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).