व्युत्पन्न ट्रिनोमियल गुणांक के लिए जनरेटिंग फ़ंक्शन
चलो $c_n$ निंदा करना $n$-th सेंटर ट्रिनोमियल गुणांक (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}$। यह एक सामान्य तथ्य है (जिसे आप उदाहरण के लिए कहा जा सकता है, जैसा कि स्टैनली के एन्यूमेरेटिव कॉम्बिनेटर, वॉल्यूम II में प्रमेय 6.3.3 ) है कि द्विभाजित तर्कसंगत निर्माण कार्य का विकर्ण बीजगणितीय है और समोच्च एकीकरण का उपयोग करके गणना की जा सकती है, जैसा कि समझाया गया है। स्टेनली, और तुम भी विकर्ण निकालने मेरे ब्लॉग पोस्ट देख सकते हैं । हम गणना निम्नानुसार कर सकते हैं। लिखो$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$इकाई चक्र द्वारा दिया गया समोच्च है। हमारे मामले में अभिन्न है
$$\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}}$$
जैसी इच्छा।
अब कुछ और सामान्य तथ्यों का उपयोग स्पर्शोन्मुखता को कम करने के लिए किया जा सकता है। की प्रमुख विलक्षणता$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 }.$$
यह OEIS पृष्ठ पर Vaclav Kotesovec द्वारा छोड़ी गई टिप्पणी के अनुरूप है, और विशेष रूप से इसका वास्तविक मूल्य है $\lim_{n \to \infty} \frac{c_{n+1}}{c_n}$ है $3$ठीक ठीक। इस विषय पर बहुत अधिक जानने के लिए Flajolet और Sedgewick के एनालिटिकल कॉम्बिनेटरिक्स के अध्याय VI.1 देखें ।
यहाँ जीपी एगोरीचेव के क्लासिक: इंटीग्रल रिप्रेजेंटेशन और कंबाइनटोरियल सोम्स की गणना के आधार पर भिन्नता है । हम केंद्रीय ट्रिनोमियल गुणांक के साथ शुरू करते हैं :\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 सेक्शन में लागू कर सकते हैं :\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)$ दो में)।
हम (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*}