Central binomial coefficient

Last updated November 24, 2024

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

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:^[4]

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

Asymptotic growth

The asymptotic behavior can be described quite accurately:^[5] ${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 ).

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}$ (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$ .

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial $(x + y) n$ into a sum involving terms of the form $ax b y c$ , where the exponents $b$ and $c$ are nonnegative integers with $b + c = n$ , and the coefficient $a$ of each term is a specific positive integer depending on $n$ and $b$ . For example, for $n = 4$ ,

In mathematics, the Bernoulli numbers $B n$ are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.

In mathematics, the gamma function is the most common extension of the factorial function to complex numbers. Derived by Daniel Bernoulli, the gamma function $is defined for all complex numbers except non-positive integers, and for every positive integer, The gamma function can be defined via a convergent improper integral for complex numbers with positive real part:$

<span class="mw-page-title-main">Negative binomial distribution</span> Probability distribution

In probability theory and statistics, the negative binomial distribution is a discrete probability distribution that models the number of failures in a sequence of independent and identically distributed Bernoulli trials before a specified (non-random) number of successes occurs. For example, we can define rolling a 6 on some dice as a success, and rolling any other number as a failure, and ask how many failure rolls will occur before we see the third success. In such a case, the probability distribution of the number of failures that appear will be a negative binomial distribution.

In mathematics, the Euler numbers are a sequence E_n of integers defined by the Taylor series expansion

In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in 1782.

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form, by some expression involving operations on the formal series.

In mathematics, the Hermite polynomials are a classical orthogonal polynomial sequence.

<span class="mw-page-title-main">Harmonic number</span> Sum of the first n whole number reciprocals; 1/1 + 1/2 + 1/3 + ... + 1/n

In mathematics, the $n$ -th harmonic number is the sum of the reciprocals of the first $n$ natural numbers:

The Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after Eugène Catalan, though they were previously discovered in the 1730s by Minggatu.

In mathematics, the falling factorial is defined as the polynomial

In mathematics, Bertrand's postulate states that, for each $, there is a prime such that . First conjectured in 1845 by Joseph Bertrand, it was first proven by Chebyshev, and a shorter but also advanced proof was given by Ramanujan.$

In mathematics, the double factorial of a number $n$ , denoted by $n ‼$ , is the product of all the positive integers up to $n$ that have the same parity as $n$ . That is,

In mathematics, the binomial series is a generalization of the polynomial that comes from a binomial formula expression like $for a nonnegative integer . Specifically, the binomial series is the MacLaurin series for the function, where and . Explicitly,$

In mathematics, the $n$ th Motzkin number is the number of different ways of drawing non-intersecting chords between $n$ points on a circle. The Motzkin numbers are named after Theodore Motzkin and have diverse applications in geometry, combinatorics and number theory.

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the unsigned Stirling numbers of the first kind count permutations according to their number of cycles.

In mathematics, the Riemann zeta function is a function in complex analysis, which is also important in number theory. It is often denoted $and is named after the mathematician Bernhard Riemann. When the argument is a real number greater than one, the zeta function satisfies the equation It can therefore provide the sum of various convergent infinite series, such as Explicit or numerically efficient formulae exist for at integer arguments, all of which have real values, including this example. This article lists these formulae, together with tables of values. It also includes derivatives and some series composed of the zeta function at integer arguments.$

In mathematics, a Ramanujan–Sato series generalizes Ramanujan’s pi formulas such as,

In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.

References

↑ Sloane, N. J. A. (ed.). "SequenceA000120". 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
1 2 Sloane, N. J. A. (ed.). "SequenceA000984(Central binomial coefficients)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.
↑ Sloane, N. J. A. (ed.). "SequenceA002894". 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 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Sloane, N. J. A. (ed.). "SequenceA000120". 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] 1 2 Sloane, N. J. A. (ed.). "SequenceA000984(Central binomial coefficients)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.

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

[5] 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]

[5]