Números Stirling de segunda clase

Los números de Stirling de segundo tipo obedecen la relación de recurrencia (descubierta por primera vez por Masanobu Saka en su Sanpō-Gakkai de 1782 ): ^{[ 12 ]}

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

con condiciones iniciales

${\displaystyle \left\{{n \atop n}\right\}=1\quad {\mbox{ para}}\;n\geq 0\quad {\text{ y }}\quad \left\{{n \atop 0}\right\}=\left\{{0 \atop n}\right\}=0\quad {\text{ para }}n>0{\text{.}}}$

Por ejemplo, el número 25 en la columna k  =  3 y la fila n  =  5 viene dado por 25  =  7  +  (3×6), donde 7 es el número que está encima y a la izquierda de 25, 6 es el número que está encima de 25 y 3 es la columna que contiene el  6.

Para probar esta recurrencia, observe que una partición de la ⁠${\displaystyle n+1}$⁠ objetos en k subconjuntos no vacíos o bien contiene el ⁠${\displaystyle (n+1)}$El objeto -ésimo es un singleton o no lo es. El número de maneras en que el singleton es uno de los subconjuntos viene dado por

${\displaystyle \left\{{n \atop k-1}\right\}}$

puesto que debemos particionar los n objetos restantes en los disponibles${\displaystyle k-1}$subconjuntos. En el otro caso , el${\displaystyle (n+1)}$El -ésimo objeto pertenece a un subconjunto que contiene otros objetos. El número de maneras viene dado por

${\displaystyle k\left\{{n \atop k}\right\}}$

ya que dividimos todos los objetos excepto el ⁠${\displaystyle (n+1)}$-ésimo en k subconjuntos, y luego nos quedan k opciones para insertar el objeto .${\displaystyle n+1}$⁠ . La suma de estos dos valores da el resultado deseado.

Otra relación de recurrencia viene dada por

${\displaystyle \left\lbrace {\begin{matrix}n\\k\end{matrix}}\right\rbrace ={\frac {k^{n}}{k!}}-\sum _{r=1}^{k-1}{\frac {\left\lbrace {\begin{matrix}n\\r\end{matrix}}\right\rbrace }{(kr)!}}.}$

lo cual se deduce de la evaluación${\displaystyle \sum _{r=0}^{n}\left\{{n \atop r}\right\}(x)_{r}=x^{n}}$en${\displaystyle x=k}$.

También se conjetura que para un fijo${\displaystyle n}$tenemos

${\displaystyle {\begin{aligned}\left\{{n \atop k}\right\}&={\frac {1}{nk}}\sum _{j=2}^{n-k+1}(j-2)!{\binom {-k}{j}}\left\{{n \atop k+j-1}\right\},\\\left\{{n \atop n}\right\}&=1.\end{aligned}}}$

Aquí comenzamos con el cálculo recursivo de${\displaystyle \left\{{n \atop n-1}\right\}}$, luego calcular${\displaystyle \left\{{n \atop n-2}\right\}}$y así sucesivamente hasta${\displaystyle \left\{{n \atop 1}\right\}}$.

Otra conjetura es que para un fijo${\displaystyle k}$tenemos

${\displaystyle {\begin{aligned}\left\{{n \atop k}\right\}&={\frac {1}{n-k}}\sum _{j=2}^{n-k+1}{\binom {n}{j}}\left\{{n-j+1 \atop k}\right\}(-1)^{j},\\\left\{{n \atop n}\right\}&=1.\end{aligned}}}$

Si cambias${\displaystyle (j-2)!}$de la primera suma y${\displaystyle (-1)^{j}}$A partir del segundo, obtendrás conjeturas similares, pero para números de Stirling de primera especie .

Algunas identidades simples incluyen:

${\displaystyle \left\{{n \atop n-1}\right\}={\binom {n}{2}}.}$

Esto se debe a que dividir n elementos en n − 1   conjuntos implica necesariamente dividirlos en un conjunto de tamaño 2 y n − 2   conjuntos de tamaño 1. Por lo tanto, solo necesitamos elegir esos dos elementos;

y

${\displaystyle \left\{{n \atop 2}\right\}=2^{n-1}-1.}$

Para comprobarlo, primero observemos que existen 2n ^pares ordenados de subconjuntos complementarios A y B. En un caso, A está vacío, y en otro, B está vacío, por lo que quedan 2n − 2   pares ordenados de subconjuntos. Finalmente, como buscamos pares no ordenados en lugar de pares ordenados ^, dividimos este último número entre 2, obteniendo el resultado anterior.

Otra expansión explícita de la relación de recurrencia proporciona identidades en el espíritu del ejemplo anterior.

La tabla de la sección 6.1 de Matemáticas Concretas proporciona una gran cantidad de formas generalizadas de sumas finitas que involucran los números de Stirling. Varias sumas finitas particulares relevantes para este artículo incluyen:

${\displaystyle {\begin{aligned}\left\{{n+1 \atop k+1}\right\}&=\sum _{j=k}^{n}{n \choose j}\left\{{j \atop k}\right\}\\\left\{{n+1 \atop k+1}\right\}&=\sum _{j=k}^{n}(k+1)^{n-j}\left\{{j \atop k}\right\}\\\left\{{n+k+1 \atop k}\right\}&=\sum _{j=0}^{k}j\left\{{n+j \atop j}\right\}\\\left\{{n \atop \ell +m}\right\}{\binom {\ell +m}{\ell }}&=\sum _{k}\left\{{k \atop \ell }\right\}\left\{{n-k \atop m}\right\}{\binom {n}{k}}\end{aligned}}}$

Los números de Stirling de segunda especie vienen dados por la fórmula explícita:

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

Esto se puede derivar utilizando el principio de inclusión-exclusión para contar las sobreyecciones de n a k y utilizando el hecho de que el número de tales sobreyecciones es${\textstyle k!\left\{{n \atop k}\right\}}$.

Además, esta fórmula es un caso especial de la k -ésima diferencia hacia adelante del monomio.${\displaystyle x^{n}}$evaluado en x = 0:

${\displaystyle \Delta ^{k}x^{n}=\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}(x+j)^{n}.}$

Dado que los polinomios de Bernoulli pueden escribirse en términos de estas diferencias finitas hacia adelante, se obtiene inmediatamente una relación en los números de Bernoulli :

${\displaystyle B_{m}(0)=\sum _{k=0}^{m}{\frac {(-1)^{k}k!}{k+1}}\left\{{m \atop k}\right\}.}$

La evaluación del polinomio exponencial incompleto de Bell B _{n , k} ( x ₁ , x ₂ ,...) sobre la secuencia de unos es igual a un número de Stirling de segunda especie:

${\displaystyle \left\{{n \atop k}\right\}=B_{n,k}(1,1,\dots ,1).}$

Otra fórmula explícita que se da en el Manual de funciones matemáticas del NIST es:

${\displaystyle \left\{{n \atop k}\right\}=\sum _{\begin{array}{c}c_{1}+\ldots +c_{k}=n-k\\c_{1},\ldots ,\ c_{k}\ \geq \ 0\end{array}}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}}$

La paridad de un número de Stirling de segunda especie es la misma que la paridad de un coeficiente binomial relacionado :

${\displaystyle \left\{{n \atop k}\right\}\equiv {\binom {z}{w}}\ {\pmod {2}},}$dónde${\displaystyle z=n-\left\lceil \displaystyle {\frac {k+1}{2}}\right\rceil ,\ w=\left\lfloor \displaystyle {\frac {k-1}{2}}\right\rfloor .}$

Esta relación se especifica mapeando las coordenadas n y k sobre el triángulo de Sierpiński .

Más directamente, consideremos dos conjuntos que contienen las posiciones de los 1 en las representaciones binarias de los resultados de expresiones respectivas:

${\displaystyle {\begin{aligned}\mathbb {A}$ :\ \sum _{i\in \mathbb {A} }2^{i}&=nk,\\\mathbb {B}  :\ \sum _{j\in \mathbb {B} }2^{j}&=\left\lfloor {\dfrac {k-1}{2}}\right\rfloor .\\\end{aligned}}}

Se puede simular una operación AND bit a bit intersectando estos dos conjuntos:

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2={\begin{cases}0,&\mathbb {A} \cap \mathbb {B} \neq \emptyset$ ;\\1,&\mathbb {A} \cap \mathbb {B} =\emptyset  ;\end{cases}}}

Para obtener la paridad de un número de Stirling de segunda especie en tiempo O (1) . En pseudocódigo :

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2:=\left[\left(\left(n-k\right)\ \And \ \left(\left(k-1\right)\,\mathrm {div} \,2\right)\right)=0\right];}$

dónde${\displaystyle \left[b\right]}$es el soporte de Iverson .

La paridad de un número de Stirling central de segunda clase${\displaystyle \textstyle \left\{{2n \atop n}\right\}}$es extraño si y solo si${\displaystyle n}$es un número fibinario , un número cuya representación binaria no tiene dos 1 consecutivos. ^{[ 13 ]}

Para un entero fijo n , la función generadora ordinaria para los números de Stirling de segundo tipo${\displaystyle \left\{{n \atop 0}\right\},\left\{{n \atop 1}\right\},\ldots }$es dado por

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

dónde${\displaystyle T_{n}(x)}$son polinomios de Touchard . Si en cambio se suman los números de Stirling contra el factorial descendente, se pueden demostrar las siguientes identidades, entre otras:

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

y

${\displaystyle \sum _{k=1}^{n+1}\left\{{n+1 \atop k}\right\}(x-1)_{k-1}=x^{n},}$

que tiene un caso especial

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

Para un entero fijo k , los números de Stirling de segunda especie tienen una función generatriz ordinaria racional.

${\displaystyle \sum _{n=k}^{\infty }\left\{{n \atop k}\right\}x^{n-k}=\prod _{r=1}^{k}{\frac {1}{1-rx}}={\frac {1}{x^{k+1}(1/x)_{k+1}}}}$

y tienen una función generadora exponencial dada por ^{[ 14 ].}

${\displaystyle \sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}={\frac {(e^{x}-1)^{k}}{k!}}.}$

Una función generadora bivariada mixta para los números de Stirling de segundo tipo es

${\displaystyle \sum _{k=0}^{\infty }\sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}y^{k}=e^{y(e^{x}-1)}.}$

Si${\displaystyle n\geq 2}$y${\displaystyle 1\leq k\leq n-1}$, entonces

${\displaystyle {\frac {1}{2}}(k^{2}+k+2)k^{n-k-1}-1\leq \left\{{n \atop k}\right\}\leq {\frac {1}{2}}{n \choose k}k^{n-k}}$. ^{[ 15 ]}

Para un valor fijo de${\displaystyle k,}$el valor asintótico de los números de Stirling de segunda especie como${\displaystyle n\rightarrow \infty }$es dado por

${\displaystyle \left\{{n \atop k}\right\}{\underset {n\to \infty }{\sim }}{\frac {k^{n}}{k!}}.}$

Si${\displaystyle k=o({\sqrt {n}})}$(donde o denota la notación o minúscula ) entonces

${\displaystyle \left\{{n+k \atop n}\right\}{\underset {n\to \infty }{\sim }}{\frac {n^{2k}}{2^{k}k!}}.}$^{[ 16 ]}

También existe una aproximación uniformemente válida: para todo k tal que 1 < k < n , se tiene

${\displaystyle \left\{{n \atop k}\right\}\sim {\sqrt {\frac {v-1}{v(1-G)}}}\left({\frac {v-1}{v-G}}\right)^{n-k}{\frac {k^{n}}{n^{k}}}e^{k(1-G)}\left({n \atop k}\right),}$

dónde${\displaystyle v=n/k}$, y${\displaystyle G\in (0,1)}$es la solución única para${\displaystyle G=ve^{G-v}}$. ^{[ 17 ]} El error relativo está acotado por aproximadamente${\displaystyle 0.066/n}$.

Para fijo${\displaystyle n}$,${\displaystyle \left\{{n \atop k}\right\}}$es unimodal, es decir, la secuencia aumenta y luego disminuye. El máximo se alcanza para como máximo dos valores consecutivos de k . Es decir, hay un entero${\displaystyle k_{n}}$de tal manera que

${\displaystyle \left\{{n \atop 1}\right\}<\left\{{n \atop 2}\right\}<\cdots <\left\{{n \atop k_{n}}\right\}\geq \left\{{n \atop k_{n}+1}\right\}>\cdots >\left\{{n \atop n}\right\}.}$

Al observar la tabla de valores anterior, los primeros valores para${\displaystyle k_{n}}$son${\displaystyle 0,1,1,2,2,3,3,4,4,4,5,\ldots }$

Cuando${\displaystyle n}$es grande

${\displaystyle k_{n}{\underset {n\to \infty }{\sim }}{\frac {n}{\log n}},}$

y el valor máximo del número de Stirling se puede aproximar con

${\displaystyle \log \left\{{n \atop k_{n}}\right\}=n\log n-n\log \log n-n+O(n\log \log n/\log n).}$^{[ 15 ]}

Si X es una variable aleatoria con una distribución de Poisson con valor esperado λ, entonces su n- ésimo momento es

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

En particular, el n -ésimo momento de la distribución de Poisson con valor esperado 1 es precisamente el número de particiones de un conjunto de tamaño n , es decir, es el n -ésimo número de Bell (este hecho es la fórmula de Dobiński ).

Sea X la variable aleatoria que representa el número de puntos fijos de una permutación aleatoria uniformemente distribuida de un conjunto finito de tamaño m . Entonces, el n -ésimo momento de X es

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

Nota: El límite superior de la sumatoria es m , no n .

En otras palabras, el n -ésimo momento de esta distribución de probabilidad es el número de particiones de un conjunto de tamaño n en no más de m partes. Esto se demuestra en el artículo sobre estadística de permutaciones aleatorias , aunque la notación es ligeramente diferente.

Los números de Stirling de segundo tipo pueden representar el número total de esquemas de rima para un poema de n versos.${\displaystyle S(n,k)}$Indica el número de esquemas de rima posibles para n versos utilizando k sílabas que riman únicas. Por ejemplo, para un poema de 3 versos, hay 1 esquema de rima con una sola rima (aaa), 3 esquemas de rima con dos rimas (aab, aba, abb) y 1 esquema de rima con tres rimas (abc).

El número r -Stirling de segundo tipo${\displaystyle \left\{{n \atop k}\right\}_{r}}$cuenta el número de particiones de un conjunto de n objetos en k subconjuntos disjuntos no vacíos, de tal manera que los primeros r elementos estén en subconjuntos distintos. ^{[ 18 ]} Estos números satisfacen la relación de recurrencia

${\displaystyle \left\{{n \atop k}\right\}_{r}=k\left\{{n-1 \atop k}\right\}_{r}+\left\{{n-1 \atop k-1}\right\}_{r}}$

Algunas identidades combinatorias y una conexión entre estos números y las gramáticas libres de contexto se pueden encontrar en ^{[ 19 ].}

Un número de Stirling de segundo tipo asociado a r es el número de maneras de particionar un conjunto de n objetos en k subconjuntos, donde cada subconjunto contiene al menos r elementos. ^{[ 20 ]} Se denota por${\displaystyle S_{r}(n,k)}$y obedece la relación de recurrencia

${\displaystyle S_{r}(n+1,k)=k\ S_{r}(n,k)+{\binom {n}{r-1}}S_{r}(n-r+1,k-1)}$

Los números asociados al 2 (secuencia A008299 en el OEIS ) aparecen en otros lugares como "números de Ward" y como las magnitudes de los coeficientes de los polinomios de Mahler .

Denotemos los n objetos a particionar por los enteros 1, 2, ..., n . Definamos los números de Stirling reducidos de segundo tipo, denotados${\displaystyle S^{d}(n,k)}$, para ser el número de maneras de particionar los enteros 1, 2, ..., n en k subconjuntos no vacíos de tal manera que todos los elementos en cada subconjunto tengan una distancia por pares de al menos d . Es decir, para cualesquiera enteros i y j en un subconjunto dado, se requiere que${\displaystyle |i-j|\geq d}$Se ha demostrado que estos números satisfacen

${\displaystyle S^{d}(n,k)=S(n-d+1,k-d+1),n\geq k\geq d}$

(de ahí el nombre "reducido"). ^{[ 21 ]} Obsérvese (tanto por definición como por la fórmula de reducción) que${\displaystyle S^{1}(n,k)=S(n,k)}$, los conocidos números Stirling de segunda especie.