中心三項式係数の母関数の導出

Question

しましょう $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シーケンスの最後の2つのリストされた用語の連続する比率です）。

また、収束（および発散）の間隔はどのくらいですか？幾何学的限界に基づくと、$G(1/3)$ 収束します。

編集：母関数は $$G(x)=\frac{1}{\sqrt{1-2x-3x^2}}$$ この答えがどのように導き出されるかについて何か考えはありますか？

Answer 1

$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}$。二変量有理母関数の対角線は代数的であり、周回積分を使用して計算できるというのは一般的な事実です（たとえば、Stanley's Enumerative Combinatorics、Vol。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}$$

これは、の有理型関数として $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 }.$$

これは、Vaclav KotesovecがOEISページに残したコメントと一致しており、特に、 $\lim_{n \to \infty} \frac{c_{n+1}}{c_n}$ です $3$丁度。このトピックの詳細については、Flajolet andSedgewickのAnalyticCombinatoricsの第VI.1章を参照してください。

Answer 2

これは、GP Egorychevのクラシックに基づくバリエーションです：積分表現と組み合わせ合計の計算。中央の三項式係数から始めます。\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)}$これで、GP Egorychevの本のセクション1.2.2の置換規則（規則5、1次元の場合）を次のように適用できます。\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*}