Ableiten der Erzeugungsfunktion für zentrierte Trinomialkoeffizienten

Dec 29 2020

Lassen $c_n$ bezeichnen die $n$-th Center Trinomial Coeffizient (OEIS-Sequenz hier ).

Es scheint, dass sie nicht durch eine lineare Wiederholungsbeziehung erzeugt werden können. Wie soll ich also vorgehen, um die Erzeugungsfunktion zu finden? $G(x)$ für die Sequenz?

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

Das geometrische Verhältnis scheint eine Grenze nahe zu haben $$\lim_{n\to ∞}\frac{c_{n+1}}{c_n}=2.95...$$ (Dies sind die aufeinanderfolgenden Verhältnisse der letzten beiden aufgelisteten Begriffe in der OEIS-Sequenz).

Wie groß ist auch das Konvergenzintervall (und die Divergenzintervall)? Basierend auf der geometrischen Grenze scheint es, dass$G(1/3)$ wird konvergieren.

Bearbeiten: Die generierende Funktion ist $$G(x)=\frac{1}{\sqrt{1-2x-3x^2}}$$ Irgendeine Idee, wie diese Antwort abgeleitet wird?

Antworten

3 QiaochuYuan Dec 29 2020 at 12:15

$c_n$ ist der Koeffizient von $x^n$ im $(1 + x + x^2)^n$. Daraus folgt, dass seine Erzeugungsfunktion die Diagonale der rationalen Erzeugungsfunktion ist

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

in dem Sinne, dass $c_n = f_{n, n}$. Es ist eine allgemeine Tatsache (die Sie beispielsweise als Satz 6.3.3 in Stanleys Enumerative Combinatorics, Band II finden können ), dass die Diagonale einer bivariaten rationalen Erzeugungsfunktion algebraisch ist und mithilfe der Konturintegration berechnet werden kann, wie in erläutert Stanley, und Sie können auch meinen Blog-Beitrag Extrahieren der Diagonale sehen . Wir können die Berechnung wie folgt durchführen. Schreiben$C(r) = \sum c_n r^n$. Dann für ausreichend klein$r$ wir haben

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

wo $\gamma$ist die Kontur, die durch den Einheitskreis gegeben ist. In unserem Fall ist der Integrand

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

welche als meromorphe Funktion von $z$hat Pole, die durch die Nullen des Nenners gegeben sind. Dies sind die Nullen eines Quadrats$r^3 z^2 + (r^2 - 1) z + r$, die dann sind

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

durch die quadratische Formel. Wir müssen nur die Rückstände an einer Stange innerhalb unserer Kontur für klein betrachten$r$, und wie $r \to 0$ das $+$ Null geht bis unendlich, also müssen wir nur die berücksichtigen $-$ Null

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

Der Rückstand an diesem Pol ist

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

so der Residuensatzes gibt

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

wie gewünscht.

Nun können einige allgemeinere Fakten verwendet werden, um Asymptotika abzuleiten. Die dominante Singularität von$C(z) = \frac{1}{\sqrt{1 - 2z - 3z^2}} = \frac{1}{\sqrt{(1 - 3z)(1 + z)}}$ tritt bei $z = \frac{1}{3}$. Um diese Singularität herum$C(z)$ sieht aus wie $\frac{1}{\sqrt{\frac{4}{3}(1 - 3z)}}$was ergibt (zB mit binomialer Expansion zusammen mit Stirlings Formel ), dass die führende Ordnung asymptotisch ist$c_n$ ist

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

Dies stimmt mit dem Kommentar von Vaclav Kotesovec auf der OEIS-Seite überein und impliziert insbesondere, dass der wahre Wert von $\lim_{n \to \infty} \frac{c_{n+1}}{c_n}$ ist $3$genau. Weitere Informationen zu diesem Thema finden Sie in Kapitel VI.1 der analytischen Kombinatorik von Flajolet und Sedgewick .

4 MarkusScheuer Dec 30 2020 at 02:24

Hier ist eine Variation, die auf GP Egorychevs Classic basiert: Integrale Repräsentation und Berechnung kombinatorischer Summen . Wir beginnen mit den zentralen Trinomialkoeffizienten :\begin{align*} [x^n](1+x+x^2)^n\qquad\qquad n\geq 0 \end{align*} Wir betrachten die Funktion \begin{align*} f(x)=1+x+x^2\tag{1} \end{align*} und eine Funktion ableiten $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*}

Mit $f(x)$ und $y(x)=\frac{x}{f(x)}$Wir können nun die Substitutionsregel (Regel 5, eindimensionaler Fall) aus Abschnitt 1.2.2 in GP Egorychevs Buch wie folgt anwenden:\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*} mit $g(y)$ die invertierte Funktion gegeben durch $y=y(x)$ in 2).

Wir erhalten aus (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*} und der Anspruch folgt.

In (4) verwenden wir die Identität \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*}