Números de Stirling y funciones generadoras exponenciales en combinatoria simbólica

El uso de funciones generadoras exponenciales (EGF) para estudiar las propiedades de los números de Stirling es un ejercicio clásico de matemática combinatoria y posiblemente el ejemplo canónico de cómo se usa la combinatoria simbólica . También ilustra los paralelos en la construcción de estos dos tipos de números, apoyando la notación de estilo binomial que se usa para ellos.

Este artículo utiliza el operador de extracción de coeficientes ${\displaystyle [z^{n}]}$para series de potencias formales , así como los operadores (etiquetados)${\displaystyle {\mathfrak {C}}}$ (para ciclos) y ${\displaystyle {\mathfrak {P}}}$(para conjuntos) sobre clases combinatorias, que se explican en la página de combinatoria simbólica . Dada una clase combinatoria, el operador de ciclo crea la clase obtenida colocando objetos de la clase fuente a lo largo de un ciclo de cierta longitud, donde se tienen en cuenta las simetrías cíclicas, y el operador conjunto crea la clase obtenida colocando objetos de la clase fuente en un conjunto (simetrías del grupo simétrico, es decir, una "bolsa no estructurada"). Las dos clases combinatorias (mostradas sin marcadores adicionales) son

• permutaciones (para números de Stirling sin signo del primer tipo):

${\displaystyle {\mathcal {P}}=\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}})),}$

y

• establecer particiones en subconjuntos no vacíos (para números Stirling del segundo tipo):

${\displaystyle {\mathcal {B}}=\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})),}$

donde ${\displaystyle {\mathcal {Z}}}$ es la clase singleton.

Advertencia : La notación utilizada aquí para los números de Stirling no es la de los artículos de Wikipedia sobre números de Stirling; los corchetes indican aquí los números de Stirling firmados.

Números de Stirling del primer tipo

Los números de Stirling sin signo del primer tipo cuentan el número de permutaciones de [ n ] con k ciclos. Una permutación es un conjunto de ciclos y, por tanto, el conjunto${\displaystyle {\mathcal {P}}\,}$ de permutaciones viene dada por

${\displaystyle {\mathcal {P}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {CYC} ({\mathcal {Z}})),\,}$

donde el singleton ${\displaystyle {\mathcal {U}}}$ciclos de marcas. Esta descomposición se examina con cierto detalle en la página sobre las estadísticas de permutaciones aleatorias .

Traduciendo a funciones generadoras obtenemos la función generadora mixta de los números de Stirling sin signo del primer tipo:

${\displaystyle G(z,u)=\exp \left(u\log {\frac {1}{1-z}}\right)=\left({\frac {1}{1-z}}\right)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.}$

Ahora los números de Stirling firmados del primer tipo se obtienen de los no firmados a través de la relación

${\displaystyle (-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right].}$

De ahí la función generadora ${\displaystyle H(z,u)}$ de estos números es

${\displaystyle H(z,u)=G(-z,-u)=\left({\frac {1}{1+z}}\right)^{-u}=(1+z)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.}$

Se puede derivar una variedad de identidades manipulando esta función generadora :

${\displaystyle (1+z)^{u}=\sum _{n=0}^{\infty }{u \choose n}z^{n}=\sum _{n=0}^{\infty }{\frac {z^{n}}{n!}}\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=e^{u\log(1+z)}.}$

En particular, el orden de adición puede ser intercambiada, y derivados tomada, y entonces z o u puede ser fija.

Sumas finitas

Una simple suma es

${\displaystyle \sum _{k=0}^{n}(-1)^{k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=(-1)^{n}n!.}$

Esta fórmula es válida porque la función generadora exponencial de la suma es

${\displaystyle H(z,-1)={\frac {1}{1+z}}\quad {\mbox{and hence}}\quad n![z^{n}]H(z,-1)=(-1)^{n}n!.}$

Sumas infinitas

Algunas sumas infinitas incluyen

${\displaystyle \sum _{n=k}^{\infty }\left[{\begin{matrix}n\\k\end{matrix}}\right]{\frac {z^{n}}{n!}}={\frac {\left(\log(1+z)\right)^{k}}{k!}}}$

donde ${\displaystyle |z|<1}$ (la singularidad más cercana a ${\displaystyle z=0}$de ${\displaystyle \log(1+z)}$ Me senté ${\displaystyle z=-1.}$)

Esta relación se mantiene porque

${\displaystyle [u^{k}]H(z,u)=[u^{k}]\exp \left(u\log(1+z)\right)={\frac {\left(\log(1+z)\right)^{k}}{k!}}.}$

Números de Stirling del segundo tipo

Estos números cuentan el número de particiones de [ n ] en k subconjuntos no vacíos. Primero considere el número total de particiones, es decir, B _n donde

${\displaystyle B_{n}=\sum _{k=1}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}{\mbox{ and }}B_{0}=1,}$

es decir, los números de Bell . Se aplica el teorema fundamental de Flajolet-Sedgewick (caso etiquetado). El conjunto${\displaystyle {\mathcal {B}}\,}$ de particiones en subconjuntos no vacíos viene dado por ("conjunto de conjuntos no vacíos de singletons")

${\displaystyle {\mathcal {B}}=\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})).}$

Esta descomposición es completamente análoga a la construcción del conjunto ${\displaystyle {\mathcal {P}}\,}$ de permutaciones de ciclos, que viene dada por

${\displaystyle {\mathcal {P}}=\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}})).}$

y produce los números de Stirling del primer tipo. De ahí el nombre de "números de Stirling del segundo tipo".

La descomposición es equivalente al EGF

${\displaystyle B(z)=\exp \left(\exp z-1\right).}$

Diferenciar para obtener

${\displaystyle {\frac {d}{dz}}B(z)=\exp \left(\exp z-1\right)\exp z=B(z)\exp z,}$

lo que implica que

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k},}$

por convolución de las funciones de generación de exponenciales y debido a la diferenciación de un EGF cae el primer coeficiente y los cambios B _{n 1} a z ⁿ / n !. 

El EGF de los números de Stirling del segundo tipo se obtiene marcando cada subconjunto que entra en la partición con el término ${\displaystyle {\mathcal {U}}\,}$, donación

${\displaystyle {\mathcal {B}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {SET} _{\geq 1}({\mathcal {Z}})).}$

Traduciendo a funciones generadoras, obtenemos

${\displaystyle B(z,u)=\exp \left(u\left(\exp z-1\right)\right).}$

Este EGF produce la fórmula para los números de Stirling del segundo tipo:

${\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=n![u^{k}][z^{n}]B(z,u)=n![z^{n}]{\frac {(\exp z-1)^{k}}{k!}}}$

o

${\displaystyle n![z^{n}]{\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}\exp(jz)(-1)^{k-j}}$

que simplifica a

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

Referencias

• Ronald Graham , Donald Knuth , Oren Patashnik (1989): Matemáticas concretas , Addison-Wesley, ISBN  0-201-14236-8
• DS Mitrinovic , Sur une classe de nombre se basa en los nombres de Stirling , CR Acad. Sci. Paris 252 (1961), 2354-2356.
• ACR Belton, El proceso monótono de Poisson , en: Probabilidad cuántica (M. Bozejko, W. Mlotkowski y J. Wysoczanski, eds.), Publicaciones del Centro Banach 73, Academia Polaca de Ciencias, Varsovia, 2006
• Milton Abramowitz e Irene A. Stegun , Manual de funciones matemáticas con fórmulas, gráficos y tablas matemáticas , USGPO, 1964, Washington DC, ISBN 0-486-61272-4