Diferencia entre funciones generadoras y series de potencias formales

Existe una estrecha relación entre las funciones generadoras y las series de potencias formales. Sin embargo, no son lo mismo. Dada una secuencia,$\,a_0,a_1,a_2,\dots,\,$definir la serie de potencia formal$\,f(x):=a_0+a_1x+a_2x^2+\dots\,$asociado a la secuencia. La secuencia y la serie formal de potencias son casi exactamente iguales excepto por la$\,x\,$asociado a la serie de potencias. Tenga en cuenta que el$\,f(x)\,$y las series de potencias se definen como exactamente iguales. la notación$\,f(x)\,$sugiere que es una función, pero con restricciones ya que la serie puede no converger para todos$\,x,\,$de ahí la razón del "formal" en el nombre. Por ejemplo,$\,f(rx) = a_0+a_1rx+a_2r^2x^2+\dots\,$se define pero$\,f(1+x)\,$no está definido Entonces$\,f(y)\,$se define para$\,y\,$siendo una serie formal de potencias con término constante de$\,0.$Es una función definida sobre un subconjunto de series de potencias formales. Más precisamente, hay una operación de sustitución definida sobre series de potencias formales, con restricciones, y si$\,y:=b_1x+b_2x^2+\dots,\,$entonces$\,f(y)\,$denota la sustitución de$\,y\,$en$\,f(x).\,$De este modo,$\,f(x)\,$es una serie de potencia formal ordinaria, pero la operación de sustitución (también conocida como evaluación) que mapea$\,y\,$a$\,f(y)\,$es la "función" asociada con$\,f(x).\,$

La idea es que una expresión algebraica ordinaria, por ejemplo,$\,\frac{1}{1-rx}\,$puede ser "expandido" en la serie de potencias$\,1+rx+rx^2+\dots\,$asociado con la secuencia$\,1,r,r^2,\dots\,$y por lo tanto$\,\frac{1}{1-rx}\,$es la función generadora de la sucesión. La idea es que la función generadora a veces se puede determinar algebraicamente usando alguna recurrencia satisfecha por la secuencia y que esto puede ayudar a determinar una expresión para la secuencia misma. En el ejemplo, la relación de recurrencia$\,a_{n+1}=r\,a_n\,$con valor inicial de$\,a_0=1\,$se traduce a la ecuación algebraica$\,\frac{f(x)-1}x=r\,f(x)\,$cuya única solución es$\,f(x)=\frac{1}{1-rx}.\,$

Hay variaciones de funciones generadoras además de la habitual y ordinaria. Por ejemplo,$\,f(x):= a_0 + a_1\frac{x^1}{1!} + a_2\frac{x^2}{2!}+\dots\,$se llama función generadora exponencial de la sucesión. Otro ejemplo,$\,f(s):= \frac{a_1}{1^s}+\frac{a_2}{2^s}+\frac{a_3}{3^s}\dots\,$se llama la función generadora de Dirichlet de la secuencia.

Las funciones generadoras vienen en dos sabores diferentes. Dada una función de conteo$a:\mathbb{N}_{0}\to\mathbb{C}$a menudo escrito como secuencia$(a_n)_{n\geq 0}$podemos asociarle una serie de potencias

$$\begin{align*} A(z)=\sum_{n=0}^\infty a_nz^n\tag{1} \end{align*}$$ que se llama función generadora (GF) de la secuencia. Podemos ver un GF como un objeto puramente formal, es decir, algebraico.

GF como objeto algebraico:

Aquí consideramos el anillo (o álgebra)$\left(K[[z]],+.\cdot\right)$de series de potencias formales

$$\begin{align*} A(z)=\sum_{n=0}^\infty a_nz^n \end{align*}$$ los cuales están sujetos a suma, multiplicación, composición, etc. obedeciendo reglas correspondientes. El término formal se usa para referirse a objetos puramente algebraicos. el indeterminado$z^n$es solo una marca de dónde está el$n$-ésimo coeficiente$a_n$es colocado.

• En este contexto, una función generadora y una serie formal de potencias se consideran lo mismo.

• Pero hay más que podemos hacer con la generación de funciones. También pueden verse como objetos analíticos .

GF como objeto analítico:

Para obtener información sobre el comportamiento de las sucesiones numéricas$a_n$para grandes $n$, estudiamos las funciones generadoras correspondientes$A(z)$. Aquí el análisis complejo juega un papel clave y el estudio asintótico de la función es esencial para obtener información.

Con respecto al comportamiento asintótico de los coeficientes de$A(z)$, P. Flajolet y R. Sedgewick motivan esto en Analytic Combinatorics de la siguiente manera:

Comparativamente, se obtienen pocos beneficios al asignar solo valores reales a la variable$z$que figura en una función generadora univariada. Por el contrario, la asignación de valores complejos resulta tener consecuencias fortuitas.

...

Cuando lo hacemos, una función generadora se convierte en una transformación geométrica del plano complejo. Esta transformación es muy regular cerca del origen; se dice que es analítica (u holomorfa). En otras palabras, cerca$0$, sólo efectúa una distorsión suave del plano complejo. Más lejos del origen, comienzan a aparecer algunas grietas en la imagen. Estas grietas —el digno nombre es singularidades— corresponden a la desaparición de la tersura. Resulta que las singularidades de una función brindan una gran cantidad de información sobre los coeficientes de la función, y especialmente sobre su tasa de crecimiento asintótico. Adoptar el punto de vista geométrico para generar funciones tiene una gran recompensa.

Me gustaría dar dos ejemplos que se presentan en la sección IV.1 Generación de funciones como objetos analíticos en el libro de P. Flajolet y R. Sedgewick. Consideran la función generadora ordinaria (OGF)$f(z)$de los números catalanes y la función generadora exponencial (EGF)$g(z)$de los desórdenes .

Estas funciones son

$$\begin{align*} \color{blue}{f(z)=\frac{1}{2}\left(1-\sqrt{1-4z}\right)\qquad\qquad g(z)=\frac{\exp(-z)}{1-z}} \end{align*}$$

En esta etapa, estas funciones generadoras son solo descripciones compactas de series de potencias formales construidas a partir de la serie elemental.

$$\begin{align*} &(1-y)^{-1}=1+y+y^2+\cdots,\qquad(1-y)^{1/2}=1-\frac{1}{2}y-\frac{1}{8}y^2-\cdots,\\ &\exp(y)=1+\frac{1}{1!}y+\frac{1}{2!}y^2+\cdots \end{align*}$$ por las reglas de composición estándar. En consecuencia, los coeficientes de ambos GF se conocen de forma explícita: $$\begin{align*} \color{blue}{ f_n}&\color{blue}{:=[z^n]f(z)=\frac{1}{n}\binom{2n-2}{n-1},}\\ \color{blue}{g_n}&\color{blue}{:=[z^n]g(z)=\frac{1}{0!}-\frac{1}{1!}+\cdots+\frac{(-1)^n}{n!}} \end{align*}$$ Pero, cuando cambiamos de opinión y consideramos$f$y$g$como objetos analíticos, obtenemos resultados asintóticos $$\begin{align*} \color{blue}{f_n\underset{n\to\infty}{\sim}\frac{4^{n-1}}{\sqrt{\pi n^3}},\qquad g_n\underset{n\to\infty}{\sim}\frac{1}{e}} \end{align*}$$

Nota: P. Flajolet y R. Sedgewick presentan muy bien los dos puntos de vista diferentes de las funciones generadoras en Analytic Combinatorics . Este libro contiene un

• Parte A - Métodos simbólicos donde las funciones generadoras se tratan como series de potencias formales y

• Parte B - Asintóticas complejas donde las funciones generadoras se tratan como objetos analíticos.