Derivación de la función generadora para coeficientes trinomiales centrados
Dejar $c_n$ denotar el $n$-ésimo coeficiente del trinomio central (secuencia OEIS aquí ).
Parece que no pueden ser generados por una relación de recurrencia lineal, entonces, ¿cómo debo buscar la función generadora? $G(x)$ para la secuencia?
$$G(x)=\sum_{n=0}^{∞}c_nx^n=1+x+3x^2+7x^3+19x^4+51x^5+141x^6+...$$
La razón geométrica parece tener un límite cercano a $$\lim_{n\to ∞}\frac{c_{n+1}}{c_n}=2.95...$$ (estas son las proporciones sucesivas de los dos últimos términos enumerados en la secuencia OEIS).
Además, ¿cuál es el intervalo de convergencia (y divergencia)? Basado en el límite geométrico, parece que$G(1/3)$ convergerá.
Editar: La función generadora es $$G(x)=\frac{1}{\sqrt{1-2x-3x^2}}$$ ¿Alguna idea de cómo se deriva esta respuesta?
Respuestas
$c_n$ es el coeficiente de $x^n$ en $(1 + x + x^2)^n$. De ello se deduce que su función generadora es la diagonal de la función generadora racional
$$F(x, y) = \frac{1}{1 - y(1 + x + x^2)} = \sum_{n \ge 0} y^n (1 + x + x^2)^n = \sum f_{n, m} x^n y^m$$
en el sentido de que $c_n = f_{n, n}$. Es un hecho general (que puede encontrar establecido, por ejemplo, como el Teorema 6.3.3 en la Combinatoria Enumerativa de Stanley , Vol. II ) que la diagonal de una función generadora racional bivariada es algebraica y se puede calcular usando la integración de contorno, como se explica en Stanley, y también puedes ver la publicación de mi blog Extrayendo la diagonal . Podemos hacer el cálculo de la siguiente manera. Escribir$C(r) = \sum c_n r^n$. Entonces para lo suficientemente pequeño$r$ tenemos
$$\frac{1}{2 \pi i} \int_{\gamma} \frac{F(rz, rz^{-1})}{z} \, dz = C(r^2)$$
dónde $\gamma$es el contorno dado por el círculo unitario. En nuestro caso, el integrando es
$$\frac{F(rz, rz^{-1})}{z} = \frac{1}{z - r - r^2 z - r^3 z^2}$$
que, como función meromórfica de $z$, tiene polos dados por los ceros del denominador. Estos son los ceros de una cuadrática$r^3 z^2 + (r^2 - 1) z + r$, que son entonces
$$z_0, z_1 = \frac{(1 - r^2) \pm \sqrt{1 - 2r^2 - 3r^4}}{2r^3}$$
por la fórmula cuadrática. Solo necesitamos considerar el residuo en un poste dentro de nuestro contorno para pequeños$r$, y como $r \to 0$ la $+$ cero va al infinito, por lo que solo debemos considerar el $-$ cero
$$z_0 = \frac{(1 - r^2) - \sqrt{1 - 2r^2 - 3r^4}}{2r^3}.$$
El residuo en este polo es
$$\lim_{z \to z_0} \frac{z - z_0}{-r^3(z - z_0)(z - z_1)} = \frac{1}{-r^3(z_0 - z_1)} = \frac{1}{\sqrt{1 - 2r^2 - 3r^4}}$$
entonces el teorema del residuo da
$$C(r^2) = \frac{1}{\sqrt{1 - 2r^2 - 3r^4}}$$
como se desee.
Ahora se pueden usar algunos hechos más generales para deducir asintóticos. La singularidad dominante de$C(z) = \frac{1}{\sqrt{1 - 2z - 3z^2}} = \frac{1}{\sqrt{(1 - 3z)(1 + z)}}$ ocurre en $z = \frac{1}{3}$. Alrededor de esta singularidad$C(z)$ parece $\frac{1}{\sqrt{\frac{4}{3}(1 - 3z)}}$que da (usando, por ejemplo, la expansión binomial junto con la fórmula de Stirling ) que el orden principal asintótico de$c_n$ es
$$\boxed{ c_n \sim \sqrt{\frac{3}{4 \pi n}} \, 3^n }.$$
Esto está de acuerdo con el comentario dejado por Vaclav Kotesovec en la página de la OEIS, y en particular implica que el verdadero valor de $\lim_{n \to \infty} \frac{c_{n+1}}{c_n}$ es $3$exactamente. Para obtener más información sobre este tema, consulte el Capítulo VI.1 de Combinatoria analítica de Flajolet y Sedgewick .
Aquí hay una variación basada en el clásico de GP Egorychev: representación integral y cálculo de sumas combinatorias . Partimos de los coeficientes del trinomio central :\begin{align*} [x^n](1+x+x^2)^n\qquad\qquad n\geq 0 \end{align*} Consideramos la función \begin{align*} f(x)=1+x+x^2\tag{1} \end{align*} y derivar una función $y=y(x)$: \begin{align*} y(x)=\frac{x}{f(x)}=\frac{x}{1+x+x^2}\qquad\qquad y^{\prime}(x)=\frac{1-x^2}{(1+x+x^2)^2 }\tag{2} \end{align*}
Con $f(x)$ y $y(x)=\frac{x}{f(x)}$ahora podemos aplicar la regla de sustitución (Regla 5, caso unidimensional) de la sección 1.2.2 en el libro de GP Egorychev de la siguiente manera:\begin{align*} \color{blue}{[x^n](f(x))^n=[y^n]\left.\left(\frac{1}{f(x)y^{\prime}(x)}\right)\right|_{x=g(y)}}\tag{3} \end{align*} con $g(y)$ la función invertida dada por $y=y(x)$ en 2).
Obtenemos de (1) - (3): \begin{align*} \color{blue}{[x^n]}&\color{blue}{\left(1+x+x^2\right)^n}\\ &=[y^n]\left.\left(\frac{1}{\left(1+x+x^2\right)\frac{d}{dx}\left(\frac{x}{1+x+x^2}\right)}\right)\right|_{x=g(y)}\\ &=[y^n]\left.\frac{1+x+x^2}{1-x^2}\right|_{x=g(y)}\\ &\,\,\color{blue}{=[y^n]\frac{1}{\sqrt{1-2y-3y^2}}}\tag{4} \end{align*} y el reclamo sigue.
En (4) usamos la identidad \begin{align*} 2y=\frac{2x}{1+x+x^2}&=1-3\left(\frac{x}{1+x+x^2}\right)^2-\left(\frac{1-x^2}{1+x+x^2}\right)^2\\ &=1-3y^2-\left(\frac{1-x^2}{1+x+x^2}\right)^2\\ \frac{1+x+x^2}{1-x^2}&=\left(1-2y-3y^2\right)^{-\frac{1}{2}} \end{align*}