중심 삼항 계수에 대한 파생 생성 함수

Question

허락하다 $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}}$$ 이 답변이 어떻게 파생되는지에 대한 아이디어가 있습니까?

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의 Enumerative Combinatorics, Vol. II 의 Theorem 6.3.3에서 언급 됨 ) . Stanley, 내 블로그 게시물 Extracting the Diagonal을 볼 수도 있습니다 . 다음과 같이 계산할 수 있습니다. 쓰다$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$, 분모의 0으로 주어진 극점이 있습니다. 이것들은 이차의 0입니다$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$ 그만큼 $+$ 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)}}$이것은 (예를 들어 Stirling의 공식 과 함께 이항 확장을 사용하여 ) 선행 순서가 점근선임을 제공합니다.$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 's Analytic Combinatorics 의 VI.1 장을 참조하십시오 .

Answer 2

다음은 GP Egorychev의 Classic : Integral Representation and Computation of Combinatorial Sums를 기반으로 한 변형 입니다. 중앙 삼항 계수로 시작합니다 .\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*}