Central binomial coefficient

The central binomial coefficients represent the number of combinations of a set where there are an equal number of two types of objects.

For example, ${\displaystyle n=2}$ represents AABB, ABAB, ABBA, BAAB, BABA, BBAA.

The number of factors of 2 in ${\displaystyle {\binom {2n}{n}}}$ is equal to the number of ones in the binary representation of n,[1] so 1 is the only odd central binomial coefficient.

The central binomial coefficients satisfy the recurrence

${\displaystyle {\binom {2n+2}{n+1}}={\frac {4n+2}{n+1}}{\binom {2n}{n}}}$

Since ${\displaystyle \textstyle {\binom {-1/2}{n+1}}={\frac {-1/2-n}{n+1}}{\binom {-1/2}{n}}}$ (and so ${\displaystyle \textstyle -4{\binom {-1/2}{n+1}}={\frac {4n+2}{n+1}}{\binom {-1/2}{n}}}$), we prove

${\displaystyle {\binom {2n}{n}}=(-1)^{n}4^{n}{\binom {-1/2}{n}}}$

by induction.

Together with the binomial series we obtain the generating function

${\displaystyle {\frac {1}{\sqrt {1-4x}}}=\sum _{n=0}^{\infty }{\binom {-{\tfrac {1}{2}}}{n}}(-4x)^{n}=\sum _{n=0}^{\infty }{\binom {2n}{n}}x^{n}=1+2x+6x^{2}+20x^{3}+70x^{4}+252x^{5}+\cdots }$

and exponential generating function

${\displaystyle \sum _{n=0}^{\infty }{\binom {2n}{n}}{\frac {x^{n}}{n!}}=e^{2x}I_{0}(2x),}$

where I₀ is a modified Bessel function of the first kind.[2]

The generating function of the squares of the central binomial coefficients gives the complete elliptic integral of the first kind:

${\displaystyle \sum _{n=0}^{\infty }{\binom {2n}{n}}^{2}x^{n}={\frac {4}{\pi (1+{\sqrt {1-16x}})}}K{\bigl (}{\frac {1-{\sqrt {1-16x}}}{1+{\sqrt {1-16x}}}}{\bigr )}}$

The Wallis product can be written using limits:

${\displaystyle {\frac {\pi }{2}}=\lim _{n\to \infty }\prod _{k=1}^{n}{\frac {2k\cdot 2k}{(2k-1)(2k+1)}}=\lim _{n\to \infty }{\frac {4^{n}n!^{2}}{(2n-1)!!(2n+1)!!}}=\lim _{n\to \infty }4^{n}n!^{2}{\frac {2^{2n}n!^{2}}{(2n)!^{2}(2n+1)}}}$

because ${\displaystyle (2n)!=2^{n}n!(2n-1)!!}$.

Taking the square root of both sides gives the asymptote for the central binomial coefficient:

${\displaystyle {2n \choose n}\sim {\frac {4^{n}}{\sqrt {\pi n}}}}$.

The latter can also be established by means of Stirling's formula. On the other hand, it can also be used as a means to determine the constant ${\displaystyle {\sqrt {2\pi }}}$ in front of the Stirling formula.

Simple bounds that immediately follow from ${\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{\binom {2n}{k}}}$ are

${\displaystyle {\frac {4^{n}}{2n+1}}\leq {2n \choose n}\leq 4^{n}{\text{ for all }}n\geq 0}$

Some better bounds are

${\displaystyle {\frac {4^{n}}{\sqrt {\pi (n+{\frac {1}{2}})}}}\leq {2n \choose n}\leq {\frac {4^{n}}{\sqrt {\pi n}}}{\text{ for all }}n\geq 1}$

The closely related Catalan numbers C_n are given by:

${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={2n \choose n}-{2n \choose n+1}{\text{ for all }}n\geq 0.}$

A slight generalization of central binomial coefficients is to take them as ${\displaystyle {\frac {\Gamma (2n+1)}{\Gamma (n+1)^{2}}}={\frac {1}{n\mathrm {B} (n+1,n)}}}$, with appropriate real numbers n, where ${\displaystyle \Gamma (x)}$ is the gamma function and ${\displaystyle \mathrm {B} (x,y)}$ is the beta function.

The powers of two that divide the central binomial coefficients are given by Gould's sequence, whose nth element is the number of odd integers in row n of Pascal's triangle.

Squaring the generating function gives

${\displaystyle {\frac {1}{1-4x}}=\sum _{n=0}^{\infty }{\binom {2n}{n}}x^{n}\sum _{n=0}^{\infty }{\binom {2n}{n}}x^{n}}$

Comparing the coefficients of ${\displaystyle x^{n}}$ gives

${\displaystyle \sum _{k=0}^{n}{\binom {2k}{k}}{\binom {2n-2k}{n-k}}=4^{n}}$

For example, ${\displaystyle 64=1(20)+2(6)+6(2)+20(1)}$. (sequence A000302 in the OEIS)

A combinatorial interpretation of this uses the fact that the number of paths on the binomial triangle that start at the origin, never cross the central line again, and terminate at level n, is given by ${\displaystyle \textstyle 2{\binom {2k}{k}}}$ for n=2k+1, and ${\displaystyle \textstyle {\binom {2k}{k}}}$ for n=2k.

As the row sum of level 2n is ${\displaystyle 2^{2n}}$, each path from the origin to level 2n can be considered to be a path which crosses the central line with a path that doesn't appended to it after the last crossing of the central line.

Half the central binomial coefficient ${\displaystyle \textstyle {\frac {1}{2}}{2n \choose n}={2n-1 \choose n-1}}$ (for ${\displaystyle n>0}$) (sequence A001700 in the OEIS) is seen in Wolstenholme's theorem.

By the Erdős squarefree conjecture, proved in 1996, no central binomial coefficient with n > 4 is squarefree.

${\displaystyle \textstyle {\binom {2n}{n}}}$ is the sum of the squares of the n-th row of Pascal's Triangle:[2]

${\displaystyle {2n \choose n}=\sum _{k=0}^{n}{\binom {n}{k}}^{2}}$

For example, ${\displaystyle {\tbinom {6}{3}}=20=1^{2}+3^{2}+3^{2}+1^{2}}$.

Erdos uses central binomial coefficients extensively in his proof of Bertrand's postulate.

Substituting ${\displaystyle x\to kx}$ in the generating function gives

${\displaystyle {\frac {1}{\sqrt {1-4kx}}}=\sum _{k=0}^{\infty }{\binom {2n}{n}}(kx)^{n}}$.

• Koshy, Thomas (2008), Catalan Numbers with Applications, Oxford University Press, ISBN 978-0-19533-454-8.

• Central binomial coefficient at PlanetMath.