Central binomial coefficient

From HandWiki
Short description: Sequence of numbers ((2n) choose (n))
Pascal's triangle, rows 0 through 7. The numbers in the central column are the central binomial coefficients.

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

[math]\displaystyle{ {2n \choose n} = \frac{(2n)!}{(n!)^2} = \prod\limits_{k=1}^{n}\frac{n+k}{k} \text{ for all }n \geq 0. }[/math]

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 coefficients give the number of possible number of assignments of n-a-side sports teams from 2n players, taking into account the playing area side

The central binomial coefficient [math]\displaystyle{ \binom{2n}{n} }[/math] is the number of arrangements where there are an equal number of two types of objects. For example, when [math]\displaystyle{ n=2 }[/math], the binomial coefficient [math]\displaystyle{ \binom{2 \cdot 2}{2} }[/math] 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 [math]\displaystyle{ \binom{2n}{n} }[/math] 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 [math]\displaystyle{ n=2 }[/math], 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 [math]\displaystyle{ \binom{2n}{n} }[/math] 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 [math]\displaystyle{ \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. }[/math] This can be proved using the binomial series and the relation [math]\displaystyle{ \binom{2n}{n} = (-1)^n 4^n \binom{-1/2}{n}, }[/math] where [math]\displaystyle{ \textstyle\binom{-1/2}{n} }[/math] is a generalized binomial coefficient.[2]

The central binomial coefficients have exponential generating function [math]\displaystyle{ \sum_{n=0}^\infty \binom{2n}{n}\frac{x^n}{n!} = e^{2x} I_0(2x), }[/math] where I0 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]

[math]\displaystyle{ \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). }[/math]

Asymptotic growth

Simple bounds that immediately follow from [math]\displaystyle{ 4^n=(1+1)^{2n}= \sum_{k=0}^{2n} \binom{2n}{k} }[/math] are[citation needed] [math]\displaystyle{ \frac{4^n}{2n+1} \leq {2n \choose n} \leq 4^n\text{ for all }n \geq 0. }[/math] The asymptotic behavior can be described more precisely:[4] [math]\displaystyle{ {2n \choose n} = \frac{4^n}{\sqrt{\pi n}}\left(1-\frac{1}{8n}+\frac{1}{128 n^2}+\frac{5}{1024 n^3} + O(n^{-4})\right). }[/math]

Related sequences

The closely related Catalan numbers Cn are given by:

[math]\displaystyle{ C_n = \frac{1}{n+1} {2n \choose n} = {2n \choose n} - {2n \choose n+1}\text{ for all }n \geq 0. }[/math]

A slight generalization of central binomial coefficients is to take them as [math]\displaystyle{ \frac{\Gamma(2n+1)}{\Gamma(n+1)^2}=\frac{1}{n \Beta(n+1,n)} }[/math], with appropriate real numbers n, where [math]\displaystyle{ \Gamma(x) }[/math] is the gamma function and [math]\displaystyle{ \Beta(x,y) }[/math] 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

[math]\displaystyle{ \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) }[/math]

Comparing the coefficients of [math]\displaystyle{ x^n }[/math] gives

[math]\displaystyle{ \sum_{k=0}^n \binom{2k}{k}\binom{2n-2k}{n-k} = 4^n }[/math]

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

Similarly,

[math]\displaystyle{ \sum_{k=0}^n \binom{2k}{k}\binom{2n-2k}{n-k}\binom{2n}{2k} = \binom{2n}{n}^2 }[/math]

(sequence A002894 in the OEIS)

Other information

Half the central binomial coefficient [math]\displaystyle{ \textstyle\frac12{2n \choose n} = {2n-1 \choose n-1} }[/math] (for [math]\displaystyle{ n\gt 0 }[/math]) (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.

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

[math]\displaystyle{ {2n \choose n}=\sum_{k=0}^n \binom{n}{k}^2 }[/math]

For example, [math]\displaystyle{ \tbinom{6}{3}=20=1^2+3^2+3^2+1^2 }[/math].

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

Another noteworthy fact is that the power of 2 dividing [math]\displaystyle{ (n+1)\dots(2n) }[/math] is exactly n.

See also

  • Central trinomial coefficient

References

  1. Sloane, N. J. A., ed. "Sequence A000120". OEIS Foundation. https://oeis.org/A000120. 
  2. Stanley, Richard P. (2012), Enumerative Combinatorics, 1 (2 ed.), Cambridge University Press, Example 1.1.15, ISBN 978-1-107-60262-5 
  3. 3.0 3.1 Sloane, N. J. A., ed. "Sequence A000984 (Central binomial coefficients)". OEIS Foundation. https://oeis.org/A000984. 
  4. 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