Catalan number and its closed formula

By | April 17, 2015

이 글에서는 카탈란 수의 closed formula를 증명한다. 우선 이 글에서 카탈란 수의 정의는 다음과 같다.

Definition 1 The Catalan numbers are a sequence defined by the following recurrence relation:

\displaystyle c_{0}=1\quad\text{and\quad}c_{n+1}=\sum_{k=0}^{n}c_{k}c_{n-k}.

카탈란 수를 정의했으니, 다음 질문은 이 카탈란 수를 표현할 수 있는 일반식이 무엇인지다.

일반항을 구하는 방법은 여러가지가 있지만, Generating function을 이용해서 찾고자 한다. 잠시 Cauchy product 공식을 기억하도록 하자. 이는 Generating function theory에서 꽤 유용하게 쓰인다.

Theorem 2 (Cauchy Product Formula) Suppose that {\sum a_{n},\sum b_{n},\sum c_{n}} where {c_{n}=\sum_{k=0}^{n}a_{n-k}b_{k}} converges to {A,B,C} respectively. Then {C=AB}.

Proof: Summation by part를 사용해보도록 하자. 잠시 {\sum a_{n}}이 converge absolutely라 하고 {A_{n}=\sum_{k=0}^{n}a_{k}}, {B_{n}=\sum_{k=0}^{n}b_{k}}라 하자. 그러면

    \begin{align*} C_{n} & =\sum_{k=0}^{n}c_{k}\\ & =a_{0}B_{n}+a_{1}B_{n-1}+\cdots+a_{n}B_{0}\\ & =a_{0}\left(B+B_{n}-B\right)+\cdots+a_{n}\left(B+B_{0}-B\right)\\ & =A_{n}B+\sum_{k=0}^{n}a_{n-k}\left(B_{k}-B\right) \end{align*}

를 얻는다. 이제 수렴하는 작업을 시작해보도록 하자. {a_{k}}{B_{k}}가 모두 수렴하므로 모든 {k}에 대하여 {\left|a_{k}\right|\le M_{A}}, {\left|B_{k}\right|<M_{B}}{M_{A},M_{B}}가 존재한다.

{\varepsilon>0}이 주어졌다고 하자. {\sum_{n=1}^{\infty}\left|a_{k}\right|<\infty}이므로 {\sum_{n=N_{1}}^{\infty}\left|a_{n}\right|<\frac{\varepsilon}{M_{B}}}{N_{1}}이 존재한다. 또, {k\le N_{1}}{k}에 대하여

\displaystyle \left|B_{n}-B\right|<\frac{\varepsilon}{N_{1}M_{A}}

인 충분히 큰 {n}을 잡을 수 있다. 그러므로 충분히 큰 {n}에 대하여

    \begin{align*} \left|\sum_{k=0}^{n}a_{n-k}\left(B_{k}-B\right)\right| & \le\sum_{k=0}^{N_{1}-1}\left|a_{n-k}\right|\left|B_{k}-B\right|+\sum_{k=N_{1}}^{n}\left|a_{n-k}\right|\left|B_{k}-B\right|\\ & \le\sum_{k=N_{1}}^{n}\left|a_{k}\right|M_{B}+\sum_{k=0}^{N_{1}}M_{A}\left|B_{n-k}-B\right|<2\varepsilon \end{align*}

이므로 {n}이 한없이 커질 때,

\displaystyle C_{n}\rightarrow AB

임을 얻는다.

이제 Abel’s theorem을 이용해서 정리를 증명한다. {\left|x\right|<1}에서 {f\left(x\right)=\sum_{n=0}^{\infty}a_{n}x^{n}}, {g\left(x\right)=\sum_{n=0}^{\infty}b_{n}x^{n}}이라 하고 {h\left(x\right)=\sum_{n=0}^{\infty}c_{n}x^{n}}이라 하자. {f\left(1\right)=\sum a_{n}}, {g\left(1\right)=\sum b_{n}}, {h\left(1\right)=\sum c_{n}}이라 정의하면, {f\left(x\right),g\left(x\right)}{\left|x\right|<1}에서 converges absolutely이므로

\displaystyle f\left(x\right)g\left(x\right)=h\left(x\right)

를 얻는다. 이제 Abel’s theorem을 적용하면

\displaystyle AB=\lim_{x\rightarrow1}f\left(x\right)g\left(x\right)=\lim_{x\rightarrow1}h\left(x\right)=h\left(1\right)=C

이다. \Box

이제 이를 바탕으로 보이고자 하는 정리를 증명하자.

Theorem 3 If {n\ge0}, then the closed formula for {c_{n}} is

\displaystyle c_{n}=\frac{1}{n+1}\binom{2n}{n}.

Proof: {c_{n}}의 생성함수를 {C\left(x\right)}라 하자. 즉

\displaystyle C\left(x\right)=\sum_{n=0}^{\infty}c_{n}x^{n}.

그러면 {c_{n+1}=\sum_{k=0}^{n}c_{k}c_{n-k}}로부터

\displaystyle \sum_{n=0}^{\infty}c_{n+1}x^{n}=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}c_{k}c_{n-k}\right)x^{n}

를 얻고 {c_{0}=1}로부터

\displaystyle \frac{1}{x}\left(C\left(x\right)-1\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}c_{k}c_{n-k}\right)x^{n}

를 얻는다. Cauchy product formula에 의하여

    \begin{align*} \sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}c_{k}c_{n-k}\right)x^{n} & =\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}c_{k}x^{k}c_{n-k}x^{n-k}\right)\\ & =\left(\sum_{n=0}^{\infty}c_{n}x^{n}\right)\left(\sum_{n=0}^{\infty}c_{n}x^{n}\right)\\ & =C\left(x\right)^{2} \end{align*}

이다. 그러므로 근의 공식에 의하여

\displaystyle C\left(x\right)=\frac{1\pm\sqrt{1-4x}}{2x}

를 얻는다.

    \begin{align*} \sqrt{1-4x} & =\sum_{n=0}^{\infty}\binom{\frac{1}{2}}{n}\left(-4\right)^{n}x^{n} \end{align*}

이고,

    \begin{align*} & \mathrel{\phantom{{=}}}\binom{\frac{1}{2}}{n}\left(-4\right)^{n}\\ & =\frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\left(\frac{1}{2}-2\right)\cdots\left(\frac{1}{2}-n+1\right)}{n!}\left(-4\right)^{n}\\ & =\frac{\left(2-1\right)\left(4-1\right)\cdots\left(2\left(n-1\right)-1\right)}{\left(n!\right)^{2}}\left(-1\right)2^{n}\left(n!\right)\\ & =-\frac{\left(2n\right)!}{\left(n!\right)\left(2n-1\right)}\\ & =-\frac{1}{2n-1}\binom{2n}{n}. \end{align*}

이 결과로부터 {\pm}부호를 -로 하는 것이 원래 {C\left(x\right)}의 정의에 합당하다.

    \begin{align*} C\left(x\right) & =\frac{1-\sqrt{1-4x}}{2x}=\frac{1+\sum_{n=0}^{\infty}\frac{1}{2n-1}\binom{2n}{n}x^{n}}{2x}\\ & =\frac{1}{2x}\left\{ 1+\left(-1\right)+\sum_{n=1}^{\infty}\frac{1}{2n-1}\binom{2n}{n}x^{n}\right\} \\ & =\frac{1}{2}\sum_{n=0}^{\infty}\frac{1}{2n+1}\binom{2\left(n+1\right)}{n+1}x^{n}. \end{align*}

멱급수의 계수를 비교하고 계산을 통해

    \begin{align*} c_{n} & =\frac{1}{4n+2}\binom{2\left(n+1\right)}{n+1}\\ & =\frac{1}{4n+2}\frac{\left(2n+2\right)\left(2n+1\right)\left(2n\right)!}{\left(n+1\right)!\left(n+1\right)!}\\ & =\frac{1}{4n+2}\frac{\left(2n+2\right)\left(2n+1\right)}{\left(n+1\right)\left(n+1\right)}\cdot\frac{\left(2n\right)!}{n!n!}\\ & =\frac{\left(n+1\right)\left(2n+1\right)}{\left(2n+1\right)\left(n+1\right)}\times\binom{2n}{n}\\ & =\frac{1}{n+1}\binom{2n}{n} \end{align*}

를 얻는다. \Box

이 카탈란 수는 여러가지 조합론 적 모델이 있다. 자세한 내용은 Stanley의 Enumerative Combinatorics의 2권에 잘 설명되어 있다.

References

  1. R. P. Stanley, Enumerative combinatorics, Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics, 1999.
  2. The Catalan Numbers from Their Generating Function, https://mikespivey.wordpress.com/2013/03/19/the-catalan-numbers-from-their-generating-function/.
  3. Wikipedia, Catalan numberhttp://en.wikipedia.org/wiki/Catalan_number.

Leave a Reply

Your email address will not be published. Required fields are marked *