# Minggatu-Catalan Number

Minggatu-Catalan Number

First discovered by the Chinese Mathematician Minggatu 明安图 (清 康熙, 1730), later by the French (né Belgian) École Polytechnique mathematician Eugène Charles Catalan (1814 – 1894).

Proof: Consider ways of making sums with {0, 1, 2, 3, 4…} and +, ( , ).

0 = (0)
1 way for 0
$\boxed {C_{0} = 1}$

0+1 =(0+1) :
1 way for 1 $\boxed {C_{1} = 1}$

0 +1 +2 = ((0+(1+2)) = ((0+1)+2):
2 ways for 2 $\boxed {C_{2} = 2}$

0+1+2+3 = (0+(1+(2+3))) = (0+((1+2)+3))= ((0+1)+(2+3)) = ((0+(1+2))+3) = (((0+1)+2)+3) :
5 ways for 3 $\boxed {C_{3} = 5}$

0+1+2+3+…+n = ?
? ways for n $\boxed {C_{n} = ?}$

Try finding the pattern for $C_{4}$:

Let A represents {0, 1, 2, 3, 4}.
There are 4 cases:

Case 1:
($\underbrace{(A)}_{C_{0}}$ + $\underbrace{(A+ A+ A+ A)} _{C_{3}}$)

Case 2:
( $\underbrace{ (A+A ) }_{C_{1}}$ + $\underbrace{ (A+ A+ A) }_{C_{2}}$)

Case 3:
( $\underbrace{ (A+A+A ) }_{C_{2}}$ + $\underbrace{ ( A+ A) }_{C_{1}}$)

Case 4:
( $\underbrace{ (A+A+A+A) }_{C_{3}}$ + $\underbrace{ (A) }_{C_{0}}$ )

$C_{4} = C_{0}.C_{3} + C_{1}.C_{2} + C_{2}.C_{1}+ C_{3}.C_{0}$

Generalise:
$C_{n+1} = C_{0}.C_{n-0} + C_{1}.C_{n-1} + C_{2}.C_{n-2} + ...+ C_{k}.C_{n-k} + ...+ C_{n-0}.C_{0}$

Recurrence Sequence of $C_{n}$:
$\boxed{ \begin{cases} C_{0} =1, \\ C_{n+1} = \displaystyle\sum_{k=0}^{n}C_{k}C_{n-k} , & \text{( } n \geq {0} \text {)} \end{cases} }$

Step 1: Generating Function C(x) :
Let $C(x) =C_{0} + C_{1}x+ C_{2}x^2 + ...+ C_{n}x^n$

$\boxed {\displaystyle C(x) = \sum_{n=0}^{\infty} C_{n} x^n }$

$C(x)^{2} = (C_{0}C_{0})+ (C_{0}C_ {1} + C_{1}C_{0})x+ (C_{0}C_{2}+ C_{1}C_{1}+ C_{2}C_{0} ) x^2 + ...$

The coefficient for $x^{n}$: $\displaystyle \sum_{k=0}^{n}C_{k}C_{n-k}$

$\displaystyle C(x)^2 = \sum_{n=0}^{\infty} \underbrace{ \left (\sum_{k=0}^{n}C_{k}C_{n-k} \right)}_{\text {coeff of }x^{n}} x^n = \sum_{n=0}^{\infty} \underbrace{ C_{n+1}}_{\text {recurrence}} x^n$

$\displaystyle x.C(x)^{2} =x. \sum_{n=0}^{\infty} C_{n+1} x^n = \sum_{n=0}^{\infty} C_{n+1} x^{n +1}$
Change (n+1) to n by adjusting initial value from n= 0 to 1:
$\displaystyle x.C(x)^{2} = \sum_{n=1}^{\infty} C_{n} x^n$

Reset the initial value from n=1 to 0:
$\displaystyle x.C(x)^{2} = \sum_{n=0}^{\infty} C_{n} x^n - C_{0}$
We have seen
$C_{0}= 1$ and
$\displaystyle C(x) = \sum_{n=0}^{\infty} C_{n} x^n$

$\displaystyle x.C(x)^{2} - C(x) +1 = 0$
This is the quadratic equation on C (x):

$C(x)= \frac{1 \pm \sqrt{1-4x} }{2x}$

$2x.C(x)= 1 \pm \sqrt{1-4x}$

Case: $2x.C(x)= 1 + \sqrt{1-4x}$
When x $\rightarrow$ 0
$2x.C(x)= 0$
$1 + \sqrt{1-4x}= 1+1=2$
Impossible !

Case: $2x.C(x)= 1 - \sqrt{1-4x}$
When x $\rightarrow$ 0
$2x.C(x)= 0$
$1 - \sqrt{1-4x}= 1- 1=0$

Step 2: The closed form for the generating function C(x) :

$\boxed { C(x)= \frac{1 - \sqrt{1-4x} }{2x} }$

Step 3: The closed form for $C_{n}$

We expand $\sqrt{1-4x}$ into power series:

Let $\displaystyle \sqrt{1-4x}= K(x)= \sum_{k=0}^{\infty}K_{k}x^{k}$

$2xC(x)= 1 - \sqrt{1-4x}$
$\displaystyle 2xC(x)= 1 - \sum_{k=0}^{\infty}K_{k}x^{k}$

$\displaystyle 2x\sum_{k=0}^ {\infty}C_{k}x^{k} = 1 - \sum_{k=0}^{\infty}K_{k}x^{k}$

Move 2x inside the left sum:
$\displaystyle \sum_{k=0}^ {\infty}2C_{k}x^{k+1} = 1 - \sum_{k=0}^{\infty}K_{k}x^{k}$

Synchronise the indices k,
$\displaystyle \sum_{k=1}^ {\infty}2C_{k-1}x^{k} = 1 - K_{0} - \sum_{k=1}^{\infty}K_{k}x^{k}$

$\displaystyle \sum_{k=1}^ {\infty}2C_{k-1}x^{k} + \sum_{k=1}^{\infty}K_{k}x^{k} = 1 - K_{0}$

$\displaystyle \sum_{k=1}^ {\infty} (2C_{k-1} + K_{k})x^{k} = 1 - K_{0}$

We compare the coefficient of each term $x^{k}$ :

$x^{0}: 0 = 1- K_{0}$
$x^{1}: 2C_{0} + K_{1} = 0$
$x^{2}: 2C_{1} + K_{2} = 0$

$x^{n}: 2C_{n} + K_{n+1} = 0$

$\boxed{ \begin{cases} K_{0} =1, \\ C_{n} = \displaystyle - \frac {K_{n+1}}{2} , & \text{( } n \geq {0} \text {)} \end{cases} }$

We need to express $K_{n+1}$ in term of n only.

Go back to the definition of K(x):
$\displaystyle K(x)= \sum_{k=0}^{\infty}K_{k}x^{k}$

$\displaystyle K(x)= K_{0}+K_{1}x + K_{2}x^{2} + ...+ K_{n}x^{n}+...$

Differentiate:
$\displaystyle K'(x)=1.K_{1}x + 2K_{2}x^{1} + ...+ nK_{n}x^{n-1}+...$

$\displaystyle K'(0)= 1K_{1}$

Differentiate 2nd time:
$\displaystyle K''(x)=2.1K_{2} + ...+ n. (n-1)K_{n}x^{n-2}+...$

$\displaystyle K''(0)= 2.1K_{2}$

Continue …

$K^{(n)}(x)= n (n-1)(n-2)...2.1K_{n} + ...$

$K^{(n)}(0)= n! K_{n}$

$\boxed { K_{n} = \frac { K^{(n)}(0)}{n!} = \frac { K^{(n)}(0)}{n^{\underline {n}}} }$

Note: See blog on “Falling Factorial”: $x^{\underline {n}}$

Next step, we shall find $K^{(n)}(0)$ in term of n
Recall
$K(x) = (1-4x)^{\frac {1}{2}}$

$K'(x) = -2.(1-4x)^{-\frac {1}{2}}$
$K''(x) = -2.2(1-4x)^{-\frac {3}{2}}$
$K'''(x) = -2.4.3(1-4x)^{-\frac {5}{2}}$
$K''''(x) = -2.6.5.4(1-4x)^{-\frac {7}{2}}$

$K^{(n)}(x) = -2.(2n-2)^{\underline {n-1}}(1-4x)^{-\frac {2n-1}{2}}$

$K^{(n+1)}(x) = -2.(2n)^{\underline {n}}(1-4x)^{-\frac {2n+1}{2}}$

$\boxed { K^{(n+1)}(0) = -2.(2n)^{\underline {n}} }$

Also from above, we have seen:
$\boxed { K_{n} = \frac { K^{(n)}(0)}{n^{\underline {n}}} }$

Change n to (n+1):
$K_{n+1} = \frac { K^{(n+1)}(0)}{(n+1)^{\underline {n+1}}}$

$K_{n+1} = \frac { -2.(2n)^{\underline {n}} } {(n+1)^{\underline {n+1}}}$
From step 3 above, we also know:
$C_{n} = - \frac {K_{n+1}} {2}$

$C_{n} = \frac { (2n)^{\underline {n}} } {(n+1)^{\underline {n+1}}} = \frac {1}{n+1} \frac { (2n)^{\underline {n}} } {(n)^{\underline {n}}}$
since $(n+1)^{\underline {n+1}} = (n+1)!= (n+1).n! = (n+1). (n)^{\underline {n}}$
and
$\frac { (2n)^{\underline {n}}} {(n)^{\underline {n}}} = \binom {2n}{n}$ (by definition of Falling Factorial)

$\boxed {\displaystyle C_{n} = \frac {1}{n+1} \binom {2n}{n} }$ [QED]

Ref:

1. History:

3. Monoid

5. Ref:
Math Girls by Hiroshi Yuki et al.
http://www.amazon.co.uk/dp/0983951306/ref=cm_sw_r_udp_awd_UKSvtb1AXNWCE