Central binomial coefficient

In mathematics the nth central binomial coefficient is the particular binomial coefficient : {2n \choose n} = \frac{(2n)!}{(n!)^2} \text{ for all }n \geq 0.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Sequence of numbers ((2n) choose (n))

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

(2nn)=(2n)!(n!)2 for all n≥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 edit source

The central binomial coefficient (2nn) is the number of arrangements where there are an equal number of two types of objects. For example, when n=2, the binomial coefficient (2⋅22) 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 (2nn) 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 (2nn) 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 edit source

The ordinary generating function for the central binomial coefficients is 11−4x=∑n=0∞(2nn)xn=1+2x+6x2+20x3+70x4+252x5+⋯. This can be proved using the binomial series and the relation (2nn)=(−1)n4n(−1/2n), where (−1/2n) is a generalized binomial coefficient.[2]

The central binomial coefficients have exponential generating function ∑n=0∞(2nn)xnn!=e2xI0(2x), 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:[4]

∑n=0∞(2nn)2xn=2πK(4x).

Asymptotic growth

edit edit source

The asymptotic behavior can be described quite accurately:[5] (2nn)=4nπn(1−18n+1128n2+51024n3+O(n−4)).

edit edit source

The closely related Catalan numbers Cn are given by:

Cn=1n+1(2nn)=(2nn)−(2nn+1) for all n≥0.

A slight generalization of central binomial coefficients is to take them as Γ(2n+1)Γ(n+1)2=1nB(n+1,n), with appropriate real numbers n, where Γ(x) is the gamma function and 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 11−4x=(∑n=0∞(2nn)xn)(∑n=0∞(2nn)xn). Comparing the coefficients of xn gives ∑k=0n(2kk)(2n−2kn−k)=4n. For example, 64=1(20)+2(6)+6(2)+20(1) (sequence A000302 in the OEIS).

The number lattice paths of length 2n that consist of steps of unit length in one of the four cardinal directions and start and end at the origin is ∑k=0n(2kk)(2n−2kn−k)(2n2k)=(2nn)∑k=0n(nk)2=(2nn)2 (sequence A002894 in the OEIS).

Properties

edit edit source

Half the central binomial coefficient 12(2nn)=(2n−1n−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.

(2nn) is the sum of the squares of the n-th row of Pascal's Triangle:[3]

(2nn)=∑k=0n(nk)2

For example, (63)=20=12+32+32+12.

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)…(2n) is exactly n.

See also

edit edit source

References

edit edit source
  1. ^ Sloane, N. J. A. (ed.). "Sequence A000120". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. Wikipedia revision 1370488966, retrieved 2026-11-18
  2. ^ Stanley, Richard P. (2012), Enumerative Combinatorics, vol. 1 (2 ed.), Cambridge University Press, Example 1.1.15, ISBN 978-1-107-60262-5 Wikipedia revision 1370488966, retrieved 2026-11-18
  3. ^ a b Sloane, N. J. A. (ed.). "Sequence A000984 (Central binomial coefficients)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. Wikipedia revision 1370488966, retrieved 2026-11-18
  4. ^ Sloane, N. J. A. (ed.). "Sequence A002894". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. Wikipedia revision 1370488966, retrieved 2026-11-18
  5. ^ Luke, Yudell L. (1969). The Special Functions and their Approximations, Vol. 1. New York, NY, USA: Academic Press, Inc. p. 35. Wikipedia revision 1370488966, retrieved 2026-11-18
  • Koshy, Thomas (2008), Catalan Numbers with Applications, Oxford University Press, ISBN 978-0-19533-454-8.
edit edit source Factorial and binomial topicsCombinatorial principlesCoreAddition principle · Rule of product · Binomial coefficient · Pascal's triangle · Central binomial coefficient · Vandermonde's identity · Binomial theorem · Binomial series · Binomial transform · Binomial type ·Twelvefold way · Abel's binomial theorem · Trinomial expansion · Pigeonhole principle · Inclusion–exclusion principleCombinatorics basicsCombination · Permutation · Multiset · Combinatorial number system · List of permutation topics · Antichain · Stars and bars (combinatorics)Identities, numbers, sequencesHockey-stick identity · Stirling number · Stirling transform · Catalan number · Fuss–Catalan number · Narayana numbers · Lah number · Gould's sequence · Jordan–Pólya number · Kempner function · Gaussian binomial coefficientMultinomial generalizationsMultinomial coefficient · Multinomial formula/theorem · Multinomial distribution · Pascal's pyramid · Pascal's simplex · Trinomial triangleDistributionsBinomial distribution · Negative binomial distribution · Hypergeometric distribution · Poisson distribution · Gamma distributionSpecial functions (connections)Gamma function · Beta function · Incomplete beta function · Incomplete gamma function · Pochhammer symbol (rising/falling) · Digamma function · Polygamma function · Multivariate gamma function · Hypergeometric series · Hypergeometric function identitiesFactorials & approximationsFactorial · Bhargava factorial · Exponential factorial · Hyperfactorial · Alternating factorial · Factorial moment · Factorial number system · Subfactorial · Superfactorial · Primorial · Lanczos approximation · Stirling's approximationStructures & arraysLozanić's triangle · Sierpinski triangle · Pascal matrix · Multiplicities of entries in Pascal's triangleOperators & calculus linksDifference operator · Difference polynomials · Table of Newtonian series · Faà di Bruno's formula · Taylor seriesTheorems & resultsStar of David theorem · Erdős–Ko–Rado theorem · Carlson's theorem · Mahler's theorem · Proof of Bertrand's postulate · Wilson's theorem · Wilson prime · De Polignac's formulaMethods & integralsEgorychev method · Nörlund–Rice integral · q-binomial identities · Binomial QMF

Text derived from https://en.wikipedia.org/w/index.php?oldid=1370488966 under CC BY-SA 4.0; modifications have been made.