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 n th central binomial coefficient is the particular binomial coefficient
( 2 n n ) = ( 2 n ) ! ( n ! ) 2 = ∏ k = 1 n n + k k for all n ≥ 0. {\displaystyle {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 [ edit ] 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 ( 2 n n ) {\displaystyle {\binom {2n}{n}}} is the number of arrangements where there are an equal number of two types of objects. For example, when n = 2 {\displaystyle n=2} , the binomial coefficient ( 2 ⋅ 2 2 ) {\displaystyle {\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 ( 2 n n ) {\displaystyle {\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 {\displaystyle 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 ( 2 n n ) {\displaystyle {\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 [ edit ] The ordinary generating function for the central binomial coefficients is
1 1 − 4 x = ∑ n = 0 ∞ ( 2 n n ) x n = 1 + 2 x + 6 x 2 + 20 x 3 + 70 x 4 + 252 x 5 + ⋯ . {\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 .} This can be proved using the
binomial series and the relation
( 2 n n ) = ( − 1 ) n 4 n ( − 1 / 2 n ) , {\displaystyle {\binom {2n}{n}}=(-1)^{n}4^{n}{\binom {-1/2}{n}},} where
( − 1 / 2 n ) {\displaystyle \textstyle {\binom {-1/2}{n}}} is a
generalized binomial coefficient .
[2] The central binomial coefficients have exponential generating function
∑ n = 0 ∞ ( 2 n n ) x n n ! = e 2 x I 0 ( 2 x ) , {\displaystyle \sum _{n=0}^{\infty }{\binom {2n}{n}}{\frac {x^{n}}{n!}}=e^{2x}I_{0}(2x),} where
I 0 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 ]
∑ n = 0 ∞ ( 2 n n ) 2 x n = 4 π ( 1 + 1 − 16 x ) K ( 1 − 1 − 16 x 1 + 1 − 16 x ) . {\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).} Asymptotic growth [ edit ] Simple bounds that immediately follow from 4 n = ( 1 + 1 ) 2 n = ∑ k = 0 2 n ( 2 n k ) {\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{\binom {2n}{k}}} are[citation needed ]
4 n 2 n + 1 ≤ ( 2 n n ) ≤ 4 n for all n ≥ 0. {\displaystyle {\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] ( 2 n n ) = 4 n π n ( 1 − 1 8 n + 1 128 n 2 + 5 1024 n 3 + O ( n − 4 ) ) . {\displaystyle {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 [ edit ] The closely related Catalan numbers C n are given by:
C n = 1 n + 1 ( 2 n n ) = ( 2 n n ) − ( 2 n n + 1 ) for all n ≥ 0. {\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 Γ ( 2 n + 1 ) Γ ( n + 1 ) 2 = 1 n B ( n + 1 , n ) {\displaystyle {\frac {\Gamma (2n+1)}{\Gamma (n+1)^{2}}}={\frac {1}{n\mathrm {B} (n+1,n)}}} , with appropriate real numbers n , where Γ ( x ) {\displaystyle \Gamma (x)} is the gamma function and B ( x , y ) {\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 n th element is the number of odd integers in row n of Pascal's triangle.
Squaring the generating function gives
1 1 − 4 x = ( ∑ n = 0 ∞ ( 2 n n ) x n ) ( ∑ n = 0 ∞ ( 2 n n ) x n ) {\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)} Comparing the coefficients of x n {\displaystyle x^{n}} gives
∑ k = 0 n ( 2 k k ) ( 2 n − 2 k n − k ) = 4 n {\displaystyle \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 ) {\displaystyle 64=1(20)+2(6)+6(2)+20(1)} . (sequence A000302 in the OEIS )
Similarly,
∑ k = 0 n ( 2 k k ) ( 2 n − 2 k n − k ) ( 2 n 2 k ) = ( 2 n n ) 2 {\displaystyle \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 [ edit ] Half the central binomial coefficient 1 2 ( 2 n n ) = ( 2 n − 1 n − 1 ) {\displaystyle \textstyle {\frac {1}{2}}{2n \choose n}={2n-1 \choose n-1}} (for n > 0 {\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 .
( 2 n n ) {\displaystyle \textstyle {\binom {2n}{n}}} is the sum of the squares of the n -th row of Pascal's Triangle:[3]
( 2 n n ) = ∑ k = 0 n ( n k ) 2 {\displaystyle {2n \choose n}=\sum _{k=0}^{n}{\binom {n}{k}}^{2}} For example, ( 6 3 ) = 20 = 1 2 + 3 2 + 3 2 + 1 2 {\displaystyle {\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 ) … ( 2 n ) {\displaystyle (n+1)\dots (2n)} is exactly n .
See also [ edit ] References [ edit ] ^ 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 [ edit ]