Turunkan fungsi Pembangkitan untuk koefisien trinomial terpusat
Membiarkan $c_n$ menunjukkan $n$Koefisien trinomial tengah ke-4 (urutan OEIS di sini ).
Tampaknya mereka tidak dapat dihasilkan oleh relasi pengulangan linier, jadi bagaimana saya harus mencari fungsi pembangkit $G(x)$ untuk urutannya?
$$G(x)=\sum_{n=0}^{∞}c_nx^n=1+x+3x^2+7x^3+19x^4+51x^5+141x^6+...$$
Rasio geometris tampaknya memiliki batas yang mendekati $$\lim_{n\to ∞}\frac{c_{n+1}}{c_n}=2.95...$$ (ini adalah rasio berturut-turut dari dua istilah terakhir yang terdaftar dalam urutan OEIS).
Juga, berapa interval konvergensi (dan divergensi)? Berdasarkan batas geometris, nampaknya$G(1/3)$ akan bertemu.
Edit: Fungsi pembangkit adalah $$G(x)=\frac{1}{\sqrt{1-2x-3x^2}}$$ Ada ide tentang bagaimana jawaban ini diturunkan?
Jawaban
$c_n$ adalah koefisien $x^n$ di $(1 + x + x^2)^n$. Oleh karena itu, fungsi pembangkitannya adalah diagonal dari fungsi pembangkitan rasional
$$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$$
dalam arti itu $c_n = f_{n, n}$. Ini adalah fakta umum (yang dapat Anda temukan dinyatakan, misalnya, sebagai Teorema 6.3.3 dalam Kombinatorika Enumeratif Stanley , Vol. II ) bahwa diagonal dari fungsi pembangkit rasional bivariat adalah aljabar dan dapat dihitung menggunakan integrasi kontur, seperti yang dijelaskan dalam Stanley, dan Anda juga dapat melihat posting blog saya Mengekstrak diagonal . Perhitungannya bisa kita lakukan sebagai berikut. Menulis$C(r) = \sum c_n r^n$. Lalu agar cukup kecil$r$ kita punya
$$\frac{1}{2 \pi i} \int_{\gamma} \frac{F(rz, rz^{-1})}{z} \, dz = C(r^2)$$
dimana $\gamma$adalah kontur yang diberikan oleh lingkaran satuan. Dalam kasus kami, integrand adalah
$$\frac{F(rz, rz^{-1})}{z} = \frac{1}{z - r - r^2 z - r^3 z^2}$$
yang, sebagai fungsi meromorfik dari $z$, memiliki kutub yang diberikan oleh nol penyebut. Ini adalah nol dari sebuah kuadrat$r^3 z^2 + (r^2 - 1) z + r$, yang kemudian
$$z_0, z_1 = \frac{(1 - r^2) \pm \sqrt{1 - 2r^2 - 3r^4}}{2r^3}$$
dengan rumus kuadrat. Kami hanya perlu mempertimbangkan residu di tiang di dalam kontur kami untuk yang kecil$r$, dan sebagai $r \to 0$ itu $+$ nol menjadi tak terhingga jadi kita hanya perlu mempertimbangkan $-$ nol
$$z_0 = \frac{(1 - r^2) - \sqrt{1 - 2r^2 - 3r^4}}{2r^3}.$$
Residu di tiang ini adalah
$$\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}}$$
sehingga teorema residu memberi
$$C(r^2) = \frac{1}{\sqrt{1 - 2r^2 - 3r^4}}$$
seperti yang diinginkan.
Sekarang beberapa fakta yang lebih umum dapat digunakan untuk menyimpulkan asimtotik. Singularitas dominan dari$C(z) = \frac{1}{\sqrt{1 - 2z - 3z^2}} = \frac{1}{\sqrt{(1 - 3z)(1 + z)}}$ terjadi pada $z = \frac{1}{3}$. Sekitar singularitas ini$C(z)$ seperti $\frac{1}{\sqrt{\frac{4}{3}(1 - 3z)}}$yang memberikan (menggunakan misalnya ekspansi binomial bersama dengan rumus Stirling ) bahwa urutan utama asimtotik$c_n$ aku s
$$\boxed{ c_n \sim \sqrt{\frac{3}{4 \pi n}} \, 3^n }.$$
Ini sesuai dengan komentar yang ditinggalkan oleh Vaclav Kotesovec di halaman OEIS, dan secara khusus menyiratkan bahwa nilai sebenarnya dari $\lim_{n \to \infty} \frac{c_{n+1}}{c_n}$ aku s $3$persis. Untuk lebih tentang topik ini lihat Bab VI.1 dari Flajolet dan Sedgewick ini Analytic Kombinasi .
Berikut adalah variasi berdasarkan Klasik GP Egorychev: Representasi Integral dan Perhitungan Jumlah Kombinatorial . Kami mulai dengan koefisien trinomial pusat :\begin{align*} [x^n](1+x+x^2)^n\qquad\qquad n\geq 0 \end{align*} Kami mempertimbangkan fungsinya \begin{align*} f(x)=1+x+x^2\tag{1} \end{align*} dan mendapatkan fungsi $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*}
Dengan $f(x)$ dan $y(x)=\frac{x}{f(x)}$kita sekarang dapat menerapkan aturan substitusi (Aturan 5, kasus satu dimensi) dari bagian 1.2.2 dalam buku GP Egorychev sebagai berikut:\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*} dengan $g(y)$ fungsi terbalik yang diberikan oleh $y=y(x)$ di (2).
Kami memperoleh dari (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*} dan klaim mengikuti.
Dalam (4) kami menggunakan identitas \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*}