ฟังก์ชัน Deriving Generating สำหรับสัมประสิทธิ์ไตรโนเมียลเป็นศูนย์กลาง
ปล่อย $c_n$ แสดงถึง $n$- สัมประสิทธิ์ไตรโนเมียลศูนย์ (ลำดับ OEIS ที่นี่ )
ดูเหมือนว่าไม่สามารถสร้างขึ้นโดยความสัมพันธ์การเกิดซ้ำเชิงเส้นได้ดังนั้นฉันจะไปหาฟังก์ชันสร้างได้อย่างไร $G(x)$ สำหรับลำดับ?
$$G(x)=\sum_{n=0}^{∞}c_nx^n=1+x+3x^2+7x^3+19x^4+51x^5+141x^6+...$$
อัตราส่วนทางเรขาคณิตดูเหมือนจะมีขีด จำกัด ใกล้เคียงกับ $$\lim_{n\to ∞}\frac{c_{n+1}}{c_n}=2.95...$$ (นี่คืออัตราส่วนต่อเนื่องของคำศัพท์สองคำสุดท้ายที่ระบุไว้ในลำดับ OEIS)
นอกจากนี้ช่วงเวลาของการลู่เข้า (และความแตกต่าง) คืออะไร? จากขีด จำกัด ทางเรขาคณิตดูเหมือนว่า$G(1/3)$ จะมาบรรจบกัน
แก้ไข: ฟังก์ชันการสร้างคือ $$G(x)=\frac{1}{\sqrt{1-2x-3x^2}}$$ มีความคิดอย่างไรว่าคำตอบนี้ได้มาอย่างไร?
คำตอบ
$c_n$ คือค่าสัมประสิทธิ์ของ $x^n$ ใน $(1 + x + x^2)^n$. ตามมาว่าฟังก์ชันการสร้างของมันคือเส้นทแยงมุมของฟังก์ชันสร้างเหตุผล
$$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$$
ในแง่ที่ว่า $c_n = f_{n, n}$. มันเป็นความจริงทั่วไป (ซึ่งคุณสามารถหาที่ระบุไว้เช่นเป็นทฤษฎีบท 6.3.3 ในสแตนลี่ย์enumerative Combinatorics ฉบับ II. ) ที่เส้นทแยงมุมของฟังก์ชั่นการสร้าง bivariate เหตุผลคือพีชคณิตและสามารถคำนวณโดยใช้การรวมรูปร่างตามที่อธิบายไว้ใน สแตนเลย์และคุณยังสามารถดูโพสต์บล็อกของฉันคลายเส้นทแยงมุม เราสามารถคำนวณได้ดังนี้ เขียน$C(r) = \sum c_n r^n$. จากนั้นให้มีขนาดเล็กเพียงพอ$r$ เรามี
$$\frac{1}{2 \pi i} \int_{\gamma} \frac{F(rz, rz^{-1})}{z} \, dz = C(r^2)$$
ที่ไหน $\gamma$คือเส้นโครงร่างที่กำหนดโดยวงกลมหน่วย ในกรณีของเรา integrand คือ
$$\frac{F(rz, rz^{-1})}{z} = \frac{1}{z - r - r^2 z - r^3 z^2}$$
ซึ่งเป็นฟังก์ชัน meromorphic ของ $z$มีขั้วที่กำหนดโดยศูนย์ของตัวส่วน นี่คือศูนย์ของกำลังสอง$r^3 z^2 + (r^2 - 1) z + r$ซึ่งก็คือ
$$z_0, z_1 = \frac{(1 - r^2) \pm \sqrt{1 - 2r^2 - 3r^4}}{2r^3}$$
โดยสูตรกำลังสอง เราจำเป็นต้องพิจารณาสิ่งตกค้างที่ขั้วภายในโครงร่างของเราเพียงเล็กน้อยเท่านั้น$r$และเป็น $r \to 0$ ที่ $+$ ศูนย์จะไปไม่มีที่สิ้นสุดดังนั้นเราจึงต้องพิจารณาเฉพาะ $-$ ศูนย์
$$z_0 = \frac{(1 - r^2) - \sqrt{1 - 2r^2 - 3r^4}}{2r^3}.$$
กากที่ขั้วนี้คือ
$$\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}}$$
ดังนั้นทฤษฎีบทตกค้างจึงให้
$$C(r^2) = \frac{1}{\sqrt{1 - 2r^2 - 3r^4}}$$
ตามต้องการ
ตอนนี้สามารถใช้ข้อเท็จจริงทั่วไปบางอย่างเพื่ออนุมาน asymptotics ได้ ความเป็นเอกฐานที่โดดเด่นของ$C(z) = \frac{1}{\sqrt{1 - 2z - 3z^2}} = \frac{1}{\sqrt{(1 - 3z)(1 + z)}}$ เกิดขึ้นที่ $z = \frac{1}{3}$. รอบเอกพจน์นี้$C(z)$ ดูเหมือน $\frac{1}{\sqrt{\frac{4}{3}(1 - 3z)}}$ซึ่งให้ (โดยใช้เช่นการขยายทวินามร่วมกับสูตรของสเตอร์ลิง ) ที่ลำดับนำหน้าของ$c_n$ คือ
$$\boxed{ c_n \sim \sqrt{\frac{3}{4 \pi n}} \, 3^n }.$$
นี่เป็นข้อตกลงกับความคิดเห็นที่ Vaclav Kotesovec ทิ้งไว้ในหน้า OEIS และโดยเฉพาะอย่างยิ่งหมายความว่ามูลค่าที่แท้จริงของ $\lim_{n \to \infty} \frac{c_{n+1}}{c_n}$ คือ $3$เป๊ะ สำหรับมากเพิ่มเติมในหัวข้อนี้โปรดดูบทที่ VI.1 ของ Flajolet และเซดจ์วิกของการวิเคราะห์ Combinatorics
นี่คือการเปลี่ยนแปลงขึ้นอยู่กับ GP Egorychev ของคลาสสิก: ตัวแทน Integral และการคำนวณผลรวม เราเริ่มต้นด้วยค่าสัมประสิทธิ์ไตรโนเมียลกลาง :\begin{align*} [x^n](1+x+x^2)^n\qquad\qquad n\geq 0 \end{align*} เราพิจารณาฟังก์ชั่น \begin{align*} f(x)=1+x+x^2\tag{1} \end{align*} และได้รับฟังก์ชัน $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*}
ด้วย $f(x)$ และ $y(x)=\frac{x}{f(x)}$ตอนนี้เราสามารถใช้กฎการแทนที่ (กฎ 5 กรณีมิติเดียว) จากหัวข้อ 1.2.2 ในหนังสือของ GP Egorychev ได้ดังนี้:\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*} ด้วย $g(y)$ ฟังก์ชันกลับด้านที่กำหนดโดย $y=y(x)$ ใน (2)
ได้รับจาก (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*} และการเรียกร้องดังต่อไปนี้
ใน (4) เราใช้ข้อมูลประจำตัว \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*}