central binomial coefficient

File:Central_binomial_coefficient_sports.svg

The central binomial coefficient $\backslash 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 $\backslash binom\{2\; \backslash 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 $\backslash 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 $\backslash binom\{2n\}\{n\}$ is equal to the number of 1s in the binary representation of n.{{Cite OEIS|sequencenumber=A000120}} As a consequence, 1 is the only odd central binomial coefficient.

The ordinary generating function for the central binomial coefficients is

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

This can be proved using the binomial series and the relation

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

where $\backslash textstyle\backslash binom\{-1/2\}\{n\}$ is a generalized binomial coefficient.{{citation | last = Stanley | first = Richard P. | authorlink = Richard P. Stanley | title = Enumerative Combinatorics | volume = 1 | edition = 2 | at = Example 1.1.15 | publisher = Cambridge University Press | year = 2012 | isbn = 978-1-107-60262-5}}

The central binomial coefficients have exponential generating function

$$\backslash sum\_\{n=0\}^\backslash infty\; \backslash binom\{2n\}\{n\}\backslash frac\{x^n\}\{n!\}\; =\; e^\{2x\}\; I\_0(2x),$$

where I₀ is a modified Bessel function of the first kind.{{Cite OEIS|sequencenumber=A000984|name=Central binomial coefficients}}

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:{{cite OEIS|A002894}}

:$\backslash sum\_\{n=0\}^\{\backslash infty\}\; \backslash binom\{2n\}\{n\}^2\; x^\{n\}\; =\; \backslash frac\{2\}\{\backslash pi\}K(4\backslash sqrt\{x\}).$

The asymptotic behavior can be described quite accurately:{{cite book |last1=Luke |first1=Yudell L. |authorlink = Yudell Luke |title=The Special Functions and their Approximations, Vol. 1 |date=1969 |publisher=Academic Press, Inc. |location=New York, NY, USA |page=35}}

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

The closely related Catalan numbers C_n are given by:

:$C\_n\; =\; \backslash frac\{1\}\{n+1\}\; \{2n\; \backslash choose\; n\}\; =\; \{2n\; \backslash choose\; n\}\; -$

{2n \choose n+1}\text{ for all }n \geq 0.

A slight generalization of central binomial coefficients is to take them as

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

The number lattice paths of length 2n that start and end at the origin is

\sum_{k=0}^n \binom{2k}{k}\binom{2n-2k}{n-k}\binom{2n}{2k}

= \sum_{k=0}^n \frac{(2n)!}{k!k!(n-k)!(n-k)!}

= \sum_{k=0}^n \frac{n!n!}{k!k!(n-k)!(n-k)!}\frac{(2n)!}{n!n!}

= \binom{2n}{n}\sum_{k=0}^n \binom{n}{k}^2

= \binom{2n}{n}^2

{{OEIS|A002894}}.

Half the central binomial coefficient $\backslash textstyle\backslash frac12\{2n\; \backslash choose\; n\}\; =\; \{2n-1\; \backslash choose\; n-1\}$ (for $n>0$) {{OEIS|id=A001700}} is seen in Wolstenholme's theorem.

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

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

:$\{2n\; \backslash choose\; n\}=\backslash sum\_\{k=0\}^n\; \backslash binom\{n\}\{k\}^2$

For example, $\backslash 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)\backslash dots(2n)$ is exactly {{mvar|n}}.

• Central trinomial coefficient

{{Reflist}}

• {{citation

| last = Koshy

| first = Thomas

| title = Catalan Numbers with Applications

| publisher = Oxford University Press

| year = 2008

| isbn = 978-0-19533-454-8

}}.

• {{planetmath|urlname=centralbinomialcoefficient|title=Central binomial coefficient}}

Category:Factorial and binomial topics