Dérivation de la fonction de génération pour les coefficients trinomiaux centrés

Dec 29 2020

Laisser $c_n$ dénotent le $n$-ème coefficient trinomial central (séquence OEIS ici ).

Il semble qu'ils ne peuvent pas être générés par une relation de récurrence linéaire, alors comment dois-je procéder pour trouver la fonction génératrice $G(x)$ pour la séquence?

$$G(x)=\sum_{n=0}^{∞}c_nx^n=1+x+3x^2+7x^3+19x^4+51x^5+141x^6+...$$

Le rapport géométrique semble avoir une limite proche de $$\lim_{n\to ∞}\frac{c_{n+1}}{c_n}=2.95...$$ (ce sont les rapports successifs des deux derniers termes listés dans la séquence OEIS).

Aussi, quel est l'intervalle de convergence (et de divergence)? Sur la base de la limite géométrique, il semble que$G(1/3)$ convergeront.

Edit: La fonction de génération est $$G(x)=\frac{1}{\sqrt{1-2x-3x^2}}$$ Une idée de la façon dont cette réponse est dérivée?

Réponses

3 QiaochuYuan Dec 29 2020 at 12:15

$c_n$ est le coefficient de $x^n$ dans $(1 + x + x^2)^n$. Il s'ensuit que sa fonction génératrice est la diagonale de la fonction génératrice rationnelle

$$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$$

dans le sens où $c_n = f_{n, n}$. C'est un fait général (que vous pouvez trouver indiqué, par exemple, comme le théorème 6.3.3 dans Stanley's Enumerative Combinatorics, Vol.II ) que la diagonale d'une fonction génératrice rationnelle bivariée est algébrique et peut être calculée en utilisant l'intégration de contour, comme expliqué dans Stanley, et vous pouvez également voir mon article de blog Extraire la diagonale . Nous pouvons faire le calcul comme suit. Écrire$C(r) = \sum c_n r^n$. Puis pour suffisamment petit$r$ nous avons

$$\frac{1}{2 \pi i} \int_{\gamma} \frac{F(rz, rz^{-1})}{z} \, dz = C(r^2)$$

$\gamma$est le contour donné par le cercle unité. Dans notre cas, l'intégrande est

$$\frac{F(rz, rz^{-1})}{z} = \frac{1}{z - r - r^2 z - r^3 z^2}$$

qui, en tant que fonction méromorphe de $z$, a des pôles donnés par les zéros du dénominateur. Ce sont les zéros d'un quadratique$r^3 z^2 + (r^2 - 1) z + r$, qui sont alors

$$z_0, z_1 = \frac{(1 - r^2) \pm \sqrt{1 - 2r^2 - 3r^4}}{2r^3}$$

par la formule quadratique. Nous devons seulement considérer le résidu à un pôle à l'intérieur de notre contour pour les petits$r$, et comme $r \to 0$ la $+$ zéro va à l'infini, il suffit donc de considérer le $-$ zéro

$$z_0 = \frac{(1 - r^2) - \sqrt{1 - 2r^2 - 3r^4}}{2r^3}.$$

Le résidu à ce pôle est

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

donc le théorème des résidus donne

$$C(r^2) = \frac{1}{\sqrt{1 - 2r^2 - 3r^4}}$$

comme voulu.

Maintenant, des faits plus généraux peuvent être utilisés pour déduire les asymptotiques. La singularité dominante de$C(z) = \frac{1}{\sqrt{1 - 2z - 3z^2}} = \frac{1}{\sqrt{(1 - 3z)(1 + z)}}$ se produit à $z = \frac{1}{3}$. Autour de cette singularité$C(z)$ ressemble à $\frac{1}{\sqrt{\frac{4}{3}(1 - 3z)}}$ce qui donne (en utilisant par exemple l'expansion binomiale avec la formule de Stirling ) que l'ordre principal asymptotique de$c_n$ est

$$\boxed{ c_n \sim \sqrt{\frac{3}{4 \pi n}} \, 3^n }.$$

Ceci est en accord avec le commentaire laissé par Vaclav Kotesovec sur la page OEIS, et implique en particulier que la vraie valeur de $\lim_{n \to \infty} \frac{c_{n+1}}{c_n}$ est $3$exactement. Pour plus d'informations sur ce sujet, voir le chapitre VI.1 de la combinatoire analytique de Flajolet et Sedgewick .

4 MarkusScheuer Dec 30 2020 at 02:24

Voici une variante basée sur le classique de GP Egorychev: représentation intégrale et calcul des sommes combinatoires . Nous commençons par les coefficients trinomiaux centraux :\begin{align*} [x^n](1+x+x^2)^n\qquad\qquad n\geq 0 \end{align*} Nous considérons la fonction \begin{align*} f(x)=1+x+x^2\tag{1} \end{align*} et dériver une fonction $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*}

Avec $f(x)$ et $y(x)=\frac{x}{f(x)}$nous pouvons maintenant appliquer la règle de substitution (règle 5, cas unidimensionnel) de la section 1.2.2 du livre de GP Egorychev comme suit:\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*} avec $g(y)$ la fonction inversée donnée par $y=y(x)$ en 2).

On obtient 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*} et la réclamation suit.

Dans (4) nous utilisons l'identité \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*}