Wyprowadzenie Funkcja generująca dla wyśrodkowanych współczynników trójmianowych

Dec 29 2020

Pozwolić $c_n$ oznaczają $n$-ty współczynnik trójmianu środka ( tutaj sekwencja OEIS ).

Wygląda na to, że nie mogą być wygenerowane przez liniową relację powtarzania, więc jak mam znaleźć funkcję generującą $G(x)$ do sekwencji?

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

Wydaje się, że stosunek geometryczny ma granicę bliską $$\lim_{n\to ∞}\frac{c_{n+1}}{c_n}=2.95...$$ (są to kolejne stosunki dwóch ostatnich wyszczególnionych terminów w sekwencji OEIS).

Jaki jest także przedział zbieżności (i rozbieżności)? Na podstawie granicy geometrycznej wydaje się, że$G(1/3)$ zbiegną się.

Edycja: funkcja generująca to $$G(x)=\frac{1}{\sqrt{1-2x-3x^2}}$$ Masz jakiś pomysł, jak wyprowadza się tę odpowiedź?

Odpowiedzi

3 QiaochuYuan Dec 29 2020 at 12:15

$c_n$ jest współczynnikiem $x^n$ w $(1 + x + x^2)^n$. Wynika z tego, że jego funkcją generującą jest przekątna racjonalnej funkcji generującej

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

w tym sensie $c_n = f_{n, n}$. Jest to ogólny fakt (który można znaleźć na przykład jako twierdzenie 6.3.3 w Enumerative Combinatorics Stanleya , tom II ), że przekątna dwuwymiarowej wymiernej funkcji generującej jest algebraiczna i można ją obliczyć za pomocą całkowania konturowego, jak wyjaśniono w Stanley, a także mój wpis na blogu Wyodrębnianie przekątnej . Możemy wykonać obliczenia w następujący sposób. pisać$C(r) = \sum c_n r^n$. Następnie za wystarczająco mały$r$ mamy

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

gdzie $\gamma$to kontur określony przez okrąg jednostkowy. W naszym przypadku integrand jest

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

który jako funkcja meromorficzna $z$, ma bieguny podane przez zera w mianowniku. To są zera kwadratu$r^3 z^2 + (r^2 - 1) z + r$, które są wtedy

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

według wzoru kwadratowego. Musimy tylko rozważyć pozostałości na biegunie wewnątrz naszego konturu za małe$r$, i jako $r \to 0$ the $+$ zero idzie do nieskończoności, więc musimy wziąć pod uwagę tylko $-$ zero

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

Pozostałość na tym biegunie jest

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

więc twierdzenie o resztach daje

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

zgodnie z życzeniem.

Teraz można wykorzystać bardziej ogólne fakty, aby wydedukować asymptotyki. Dominująca osobliwość$C(z) = \frac{1}{\sqrt{1 - 2z - 3z^2}} = \frac{1}{\sqrt{(1 - 3z)(1 + z)}}$ występuje o godz $z = \frac{1}{3}$. Wokół tej osobliwości$C(z)$ wygląda jak $\frac{1}{\sqrt{\frac{4}{3}(1 - 3z)}}$co daje (używając np. dwumianowego rozwinięcia razem ze wzorem Stirlinga ), że wiodący porządek asymptotyczny$c_n$ jest

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

Jest to zgodne z komentarzem Vaclava Kotesovca na stronie OEIS, aw szczególności oznacza, że ​​prawdziwa wartość $\lim_{n \to \infty} \frac{c_{n+1}}{c_n}$ jest $3$dokładnie. Więcej informacji na ten temat można znaleźć w rozdziale VI.1 książki Flajolet and Sedgewick's Analytic Combinatorics .

4 MarkusScheuer Dec 30 2020 at 02:24

Oto wariacja oparta na Klasie GP Egorycheva: Reprezentacja całkowa i Obliczanie sum kombinatorycznych . Zaczynamy od centralnych współczynników trójmianu :\begin{align*} [x^n](1+x+x^2)^n\qquad\qquad n\geq 0 \end{align*} Rozważamy funkcję \begin{align*} f(x)=1+x+x^2\tag{1} \end{align*} i wyprowadzić funkcję $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*}

Z $f(x)$ i $y(x)=\frac{x}{f(x)}$możemy teraz zastosować regułę podstawiania (Reguła 5, przypadek jednowymiarowy) z sekcji 1.2.2 w książce GP Egorycheva w następujący sposób:\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*} z $g(y)$ funkcja odwrócona dana przez $y=y(x)$ w 2).

Otrzymujemy z (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*} a roszczenie następuje.

W (4) używamy tożsamości \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*}