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

El uso de funciones generadoras exponenciales (FGE) 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 utiliza la combinatoria simbólica . También ilustra los paralelismos en la construcción de estos dos tipos de números, lo que respalda la notación de estilo binomial que se utiliza para ellos.

Este artículo utiliza el operador de extracción de coeficientes para series de potencias formales , así como los operadores (etiquetados) (para ciclos) y (para conjuntos) en 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 al colocar 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 de conjunto crea la clase obtenida al colocar 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 ${\displaystyle [z^{n}]}$ ${\displaystyle {\mathfrak {C}}}$ ${\displaystyle {\mathfrak {P}}}$

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

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

y

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

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

¿Dónde está la clase singleton? ${\displaystyle {\mathcal {Z}}}$

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 los números de Stirling con signo aquí.

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 lo tanto, el conjunto de permutaciones está dado por ${\displaystyle {\mathcal {P}}\,}$

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

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

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 con signo del primer tipo se obtienen a partir de los sin signo mediante la relación

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

Por lo tanto, la función generadora de estos números es ${\displaystyle H(z,u)}$

${\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 pueden derivar diversas 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, se puede intercambiar el orden de suma y tomar derivadas, y luego se puede fijar z o u .

Sumas finitas

Una suma simple 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 (la singularidad más cercana a de está en ) ${\displaystyle |z|<1}$ ${\displaystyle z=0}$ ${\displaystyle \log(1+z)}$ ${\displaystyle z=-1.}$

Esta relación se cumple 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 de particiones en subconjuntos no vacíos viene dado por ("conjunto de conjuntos no vacíos de singletons") ${\displaystyle {\mathcal {B}}\,}$

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

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

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

y da como resultado 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 funciones generadoras exponenciales y porque al diferenciar una EGF se elimina el primer coeficiente y se desplaza B _{n +1} a z ⁿ / n !. 

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

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

Lo cual se 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 relies aux nombres de Stirling , CR Acad. Ciencia. París 252 (1961), 2354–2356.
• ACR Belton, El proceso monótono de Poisson , en: Probabilidad cuántica (M. Bozejko, W. Mlotkowski y J. Wysoczanski, eds.), Banach Center Publications 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