Merkezlenmiş üç terimli katsayılar için türetme işlevi

Dec 29 2020

İzin Vermek $c_n$ belirtmek $n$-th merkez trinom katsayısı ( burada OEIS dizisi ).

Doğrusal bir tekrarlama ilişkisi ile oluşturulamayacakları anlaşılıyor, bu yüzden üreten işlevi nasıl bulmalıyım? $G(x)$ sıra için?

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

Geometrik oranın yaklaşık bir limiti var gibi görünüyor. $$\lim_{n\to ∞}\frac{c_{n+1}}{c_n}=2.95...$$ (bunlar, OEIS dizisinde listelenen son iki terimin ardışık oranlarıdır).

Ayrıca, yakınsama (ve ıraksama) aralığı nedir? Geometrik sınıra göre öyle görünüyor ki$G(1/3)$ yakınlaşacak.

Düzenleme: Oluşturma işlevi $$G(x)=\frac{1}{\sqrt{1-2x-3x^2}}$$ Bu cevabın nasıl elde edildiği hakkında bir fikriniz var mı?

Yanıtlar

3 QiaochuYuan Dec 29 2020 at 12:15

$c_n$ katsayısı $x^n$ içinde $(1 + x + x^2)^n$. Oluşturma işlevinin, rasyonel üretme işlevinin köşegeni olduğu sonucu çıkar.

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

anlamda olduğu $c_n = f_{n, n}$. İki değişkenli rasyonel üretme fonksiyonunun köşegeninin cebirsel olduğu ve aşağıda açıklandığı gibi kontur entegrasyonu kullanılarak hesaplanabileceği genel bir gerçektir (örneğin, Stanley's Enumerative Combinatorics, Cilt II'de Teorem 6.3.3'te belirtildiği gibi) Stanley ve ayrıca Köşegen Çıkarma blog yazımı da görebilirsiniz . Hesaplamayı aşağıdaki gibi yapabiliriz. Yazmak$C(r) = \sum c_n r^n$. O zaman yeterince küçük$r$ sahibiz

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

nerede $\gamma$birim çember tarafından verilen kontur. Bizim durumumuzda integrand

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

meromorfik bir fonksiyon olarak $z$, paydanın sıfırları ile verilen kutuplara sahiptir. Bunlar ikinci dereceden bir sıfırın$r^3 z^2 + (r^2 - 1) z + r$, hangileri o zaman

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

ikinci dereceden formülle. Küçük için sadece konturumuzun içindeki bir kutupta bulunan kalıntıyı düşünmemiz gerekir$r$, ve benzeri $r \to 0$ $+$ sıfır sonsuza gider, bu yüzden sadece $-$ sıfır

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

Bu kutuptaki kalıntı

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

yani kalıntı teoremi verir

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

istediğiniz gibi.

Şimdi asimptotikleri çıkarmak için daha genel gerçekler kullanılabilir. Baskın tekilliği$C(z) = \frac{1}{\sqrt{1 - 2z - 3z^2}} = \frac{1}{\sqrt{(1 - 3z)(1 + z)}}$ meydana gelir $z = \frac{1}{3}$. Bu tekilliğin etrafında$C(z)$ gibi görünüyor $\frac{1}{\sqrt{\frac{4}{3}(1 - 3z)}}$bu (örneğin, Stirling formülü ile birlikte binom açılımını kullanarak ), ön sıranın asimtotik olduğunu verir$c_n$ dır-dir

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

Bu, Vaclav Kotesovec'in OEIS sayfasında bıraktığı yorumla uyum içindedir ve özellikle $\lim_{n \to \infty} \frac{c_{n+1}}{c_n}$ dır-dir $3$kesinlikle. Bu konu hakkında daha fazla bilgi için Flajolet ve Sedgewick'in Analitik Kombinatorikleri Bölüm VI.1'e bakın .

4 MarkusScheuer Dec 30 2020 at 02:24

İşte GP Egorychev'in Klasik: İntegral Gösterimi ve Kombinatoryal Toplamların Hesaplanmasına dayanan bir varyasyon . Merkezi üç terimli katsayılarla başlıyoruz :\begin{align*} [x^n](1+x+x^2)^n\qquad\qquad n\geq 0 \end{align*} İşlevi düşünüyoruz \begin{align*} f(x)=1+x+x^2\tag{1} \end{align*} ve bir fonksiyon türetmek $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*}

İle $f(x)$ ve $y(x)=\frac{x}{f(x)}$şimdi GP Egorychev'in kitabındaki 1.2.2 numaralı bölümdeki ikame kuralını (Kural 5, tek boyutlu durum) aşağıdaki gibi uygulayabiliriz:\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*} ile $g(y)$ tarafından verilen ters fonksiyon $y=y(x)$ (2).

(1) - (3) 'den elde ediyoruz: \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*} ve iddia takip eder.

(4) 'te kimliği kullanıyoruz \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*}