Central_binomial_coefficient References

In mathematics the nth central binomial coefficient is the particular binomial coefficient

{2n \choose n}={\frac {(2n)!}{(n!)^{2}}}=\prod \limits _{k=1}^{n}{\frac {n+k}{k}}{\text{ for all }}n\geq 0.

They are called central since they show up exactly in the middle of the even-numbered rows in Pascal's triangle. The first few central binomial coefficients starting at n = 0 are:

1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, ...; (sequence A000984 in the OEIS)

Combinatorial interpretations and other properties

The central binomial coefficient ${\binom {2n}{n}}$ is the number of arrangements where there are an equal number of two types of objects. For example, when $n=2$ , the binomial coefficient ${\binom {2\cdot 2}{2}}$ is equal to 6, and there are six arrangements of two copies of A and two copies of B: AABB, ABAB, ABBA, BAAB, BABA, BBAA.

The same central binomial coefficient ${\binom {2n}{n}}$ is also the number of words of length 2n made up of A and B within which, as one reads from left to right, there are never more B's than A's at any point. For example, when $n=2$ , there are six words of length 4 in which each prefix has at least as many copies of A as of B: AAAA, AAAB, AABA, AABB, ABAA, ABAB.

The number of factors of 2 in ${\binom {2n}{n}}$ is equal to the number of 1s in the binary representation of n.^[1] As a consequence, 1 is the only odd central binomial coefficient.

Generating function

The ordinary generating function for the central binomial coefficients is

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

This can be proved using the binomial series and the relation

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

where

\textstyle {\binom {-1/2}{n}}

is a generalized binomial coefficient.^[2]

The central binomial coefficients have exponential generating function

\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.^[3]

The generating function of the squares of the central binomial coefficients can be written in terms of the complete elliptic integral of the first kind:^{[
citation needed]}

\sum _{n=0}^{\infty }{\binom {2n}{n}}^{2}x^{n}={\frac {4}{\pi (1+{\sqrt {1-16x}})}}K\left({\frac {1-{\sqrt {1-16x}}}{1+{\sqrt {1-16x}}}}\right).

Asymptotic growth

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

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

The asymptotic behavior can be described more precisely:^[4]

{2n \choose n}={\frac {4^{n}}{\sqrt {\pi n}}}\left(1-{\frac {1}{8n}}+{\frac {1}{128n^{2}}}+{\frac {5}{1024n^{3}}}+O(n^{-4})\right).

Related sequences

The closely related Catalan numbers C_n are given by:

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 ${\frac {\Gamma (2n+1)}{\Gamma (n+1)^{2}}}={\frac {1}{n\mathrm {B} (n+1,n)}}$ , with appropriate real numbers n, where $\Gamma (x)$ is the gamma function and $\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

{\frac {1}{1-4x}}=\left(\sum _{n=0}^{\infty }{\binom {2n}{n}}x^{n}\right)\left(\sum _{n=0}^{\infty }{\binom {2n}{n}}x^{n}\right)

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

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

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

Similarly,

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

(sequence A002894 in the OEIS)

Other information

Half the central binomial coefficient $\textstyle {\frac {1}{2}}{2n \choose n}={2n-1 \choose n-1}$ (for $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.

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

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

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

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

Another noteworthy fact is that the power of 2 dividing $(n+1)\dots (2n)$ is exactly $n$ .

References

^ Sloane, N. J. A. (ed.). "Sequence A000120". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Stanley, Richard P. (2012), Enumerative Combinatorics, vol. 1 (2 ed.), Cambridge University Press, Example 1.1.15, ISBN 978-1-107-60262-5
^ ^a ^b Sloane, N. J. A. (ed.). "Sequence A000984 (Central binomial coefficients)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Luke, Yudell L. (1969). The Special Functions and their Approximations, Vol. 1. New York, NY, USA: Academic Press, Inc. p. 35.

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

External links

Central binomial coefficient at PlanetMath.

[1] Sloane, N. J. A. (ed.). "Sequence A000120". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[2] Stanley, Richard P. (2012), Enumerative Combinatorics, vol. 1 (2 ed.), Cambridge University Press, Example 1.1.15, ISBN 978-1-107-60262-5

[Sloanes-3] Sloane, N. J. A. (ed.). "Sequence A000984 (Central binomial coefficients)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[4] Luke, Yudell L. (1969). The Special Functions and their Approximations, Vol. 1. New York, NY, USA: Academic Press, Inc. p. 35.

[1]

[2]

[3]

[4]