Hubbry Logo
search
logo
1997514

Central binomial coefficient

logo
Community Hub0 Subscribers
Read side by side
from Wikipedia

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

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 is the number of arrangements where there are an equal number of two types of objects. For example, when , the binomial coefficient 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 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 , 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 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 This can be proved using the binomial series and the relation where is a generalized binomial coefficient.[2]

The central binomial coefficients have exponential generating function 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]

Asymptotic growth

[edit]

The asymptotic behavior can be described quite accurately:[5]

[edit]

The closely related Catalan numbers Cn are given by:

A slight generalization of central binomial coefficients is to take them as , with appropriate real numbers n, where is the gamma function and 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 Comparing the coefficients of gives For example, (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 (sequence A002894 in the OEIS).

Properties

[edit]

Half the central binomial coefficient (for ) (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.

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

For example, .

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

Another noteworthy fact is that the power of 2 dividing is exactly n.

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia
from Grokipedia
The central binomial coefficient (2nn)\binom{2n}{n} is the binomial coefficient that selects the middle entry in the 2n2nth row of Pascal's triangle (for nonnegative integer nn), given explicitly by the formula (2n)!(n!)2\frac{(2n)!}{(n!)^2}.[1] It counts the number of ways to choose nn items from a set of 2n2n distinct items without regard to order, and equivalently, the number of monotonic lattice paths along the edges of a grid with n×nn \times n square cells.[1] This coefficient also equals the sum of the squares of the binomial coefficients in the nnth row of Pascal's triangle: k=0n(nk)2=(2nn)\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}.[1] Central binomial coefficients play a fundamental role in combinatorics and analysis, serving as a cornerstone for counting problems and generating functions due to their rich structure and frequent appearances in series expansions.[2] The ordinary generating function for the sequence is n=0(2nn)xn=114x\sum_{n=0}^\infty \binom{2n}{n} x^n = \frac{1}{\sqrt{1-4x}} for x<14|x| < \frac{1}{4}, which arises in contexts like the enumeration of binary trees and random walks.[1] They are intimately connected to the Catalan numbers Cn=1n+1(2nn)C_n = \frac{1}{n+1} \binom{2n}{n}, which quantify diverse structures such as correctly matched parentheses and non-crossing partitions.[1] Asymptotically, the central binomial coefficient grows like (2nn)4nπn\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}} as nn \to \infty, a result derived from Stirling's approximation to the factorials, with more refined expansions involving higher-order terms for precise estimates in large-nn applications.[3] These coefficients exhibit notable number-theoretic properties, such as never being prime for n>1n > 1 and having only finitely many squarefree values (specifically 2, 6, and 70 for n=1,2,4n=1,2,4), as established through advanced theorems in analytic number theory.[4] Their study extends to inequalities, divisibility criteria by primes, and integrals, underscoring their utility across pure and applied mathematics.[2]

Definition and Basics

Definition

The binomial coefficient (mk)\binom{m}{k} is defined as the number m!k!(mk)!\frac{m!}{k!(m-k)!}, where mm and kk are non-negative integers with kmk \leq m, representing the number of ways to choose kk elements from a set of mm elements without regard to order.[5] The nnth central binomial coefficient is the specific binomial coefficient (2nn)\binom{2n}{n}, also denoted C(2n,n)C(2n, n), given explicitly by the formula
(2nn)=(2n)!(n!)2. \binom{2n}{n} = \frac{(2n)!}{(n!)^2}.
[4] This quantity arises as the central entry in the (2n)(2n)th row of Pascal's triangle, where the entries are the binomial coefficients (2nk)\binom{2n}{k} for k=0,1,,2nk = 0, 1, \dots, 2n, and (2nn)\binom{2n}{n} is the largest among them due to the symmetry and unimodality of the row.
The term "central binomial coefficient" reflects its position at the center of the even-length row in Pascal's triangle. These coefficients appeared in early combinatorial studies during the 18th century, notably in Leonhard Euler's Introductio in analysin infinitorum (1748), where binomial expansions and their applications in series were explored.[6] They possess significant combinatorial interpretations, such as counting balanced parentheses or lattice paths, which are elaborated in subsequent sections.

Examples and Computation

The central binomial coefficient (2nn)\binom{2n}{n} for small values of nn illustrates its rapid growth. The sequence begins with (00)=1\binom{0}{0} = 1, (21)=2\binom{2}{1} = 2, (42)=6\binom{4}{2} = 6, and continues as shown in the following table for n=0n = 0 to 1010:[1]
nn(2nn)\binom{2n}{n}
01
12
26
320
470
5252
6924
73432
812870
948620
10184756
These values are cataloged in the Online Encyclopedia of Integer Sequences as A000984.[1] For small nn, (2nn)\binom{2n}{n} can be computed directly using the definition (2nn)=(2n)!(n!)2\binom{2n}{n} = \frac{(2n)!}{(n!)^2}, where factorials are calculated via successive multiplication.[4] This approach is straightforward but becomes inefficient for larger nn due to the need to handle increasingly large intermediate factorials. An alternative is the multiplicative formula (2nn)=k=1nn+kk\binom{2n}{n} = \prod_{k=1}^n \frac{n + k}{k}, which computes the value as a running product, reducing the size of intermediates compared to full factorials. A useful recursive relation for iterative computation is (2nn)=4n2n(2n2n1)\binom{2n}{n} = \frac{4n - 2}{n} \binom{2n-2}{n-1}, with base case (00)=1\binom{0}{0} = 1. To derive this, start with the ratio:
(2nn)(2n2n1)=(2n)!(n!)2(2n2)!((n1)!)2=(2n)!(2n2)!((n1)!)2(n!)2=(2n)(2n1)1nn=2n(2n1)n2=2(2n1)n=4n2n. \frac{\binom{2n}{n}}{\binom{2n-2}{n-1}} = \frac{\frac{(2n)!}{(n!)^2}}{\frac{(2n-2)!}{((n-1)!)^2}} = \frac{(2n)!}{(2n-2)!} \cdot \frac{((n-1)!)^2}{(n!)^2} = (2n)(2n-1) \cdot \frac{1}{n \cdot n} = \frac{2n(2n-1)}{n^2} = \frac{2(2n-1)}{n} = \frac{4n-2}{n}.
Rearranging yields the recurrence. This relation enables computation by building up from smaller values, avoiding full factorial evaluations and useful for programming implementations. Computing (2nn)\binom{2n}{n} for large nn presents challenges, such as overflow in fixed-precision integer arithmetic, where values exceed standard data types like 64-bit integers beyond n30n \approx 30. In number theory applications, such as studying divisibility or congruences modulo a prime pp, modular arithmetic is employed to compute (2nn)modp\binom{2n}{n} \mod p without full expansion, often using Lucas' theorem or specialized recurrences to avoid overflow entirely. As of 2025, modern software supports efficient evaluation using arbitrary-precision arithmetic. In Python 3.8 and later, the math.comb(2*n, n) function implements the multiplicative formula with built-in big integers for exact results up to very large nn. Similarly, Mathematica's Binomial[2 n, n] leverages arbitrary-precision computation for exact values. For extremely large nn (e.g., n>106n > 10^6), where even arbitrary-precision multiplication becomes costly, fast Fourier transform (FFT)-based methods accelerate the computation of the product in the multiplicative formula by enabling rapid convolution for the numerator and denominator terms. For estimating values without exact computation, asymptotic approximations provide scale, such as (2nn)4nπn\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}} via Stirling's formula (detailed in later sections).[4]

Combinatorial Interpretations

Classical Interpretations

The central binomial coefficient (2nn)\binom{2n}{n} counts the number of ways to choose nn elements from a set of 2n2n distinct elements. This interpretation follows directly from the general combinatorial definition of binomial coefficients as the number of combinations. Equivalently, it enumerates the number of binary strings of length 2n2n containing exactly nn zeros and nn ones, where each string corresponds to selecting positions for the ones (or zeros).[7] In lattice path enumeration, (2nn)\binom{2n}{n} gives the number of monotonic paths from (0,0)(0,0) to (n,n)(n,n) consisting of nn right steps (1,0)(1,0) and nn up steps (0,1)(0,1), with no restrictions on crossing the main diagonal y=xy = x. These paths represent all possible orders of taking the required steps to reach the endpoint. For comparison, the restricted case of paths that stay below or on the diagonal corresponds to the Catalan number 1n+1(2nn)\frac{1}{n+1} \binom{2n}{n}.[7] The ballot theorem provides another classical context, where (2nn)\binom{2n}{n} counts the total number of vote-counting sequences in an election between two candidates each receiving exactly nn votes. Each sequence is an arrangement of nn votes for one candidate and nn for the other. The theorem itself specifies the number of such sequences in which one candidate remains strictly ahead throughout the count, given by 1n+1(2nn)\frac{1}{n+1} \binom{2n}{n}.[8] A simple application arises in partitioning problems: (2nn)\binom{2n}{n} is the number of ways to divide 2n2n distinct objects into two labeled groups of nn each, such as assigning players to two distinguishable teams. For unlabeled groups, where the partitions are unordered, the count is 12(2nn)\frac{1}{2} \binom{2n}{n} when n>0n > 0, since each partition is counted twice in the labeled case.[7]

Extensions and Variations

One prominent extension of the central binomial coefficient involves q-analogues, where the Gaussian binomial coefficient (2nn)q\dbinom{2n}{n}_q serves as a deformation parameterized by qq. This generalization counts the number of n-dimensional subspaces in a (2n)-dimensional vector space over the finite field Fq\mathbb{F}_q, offering insights into combinatorial structures in finite geometries. Additionally, it is the generating function for the number of integer partitions whose Young diagrams fit within an n by n square (weighted by qq to the power of the partition's size), connecting to q-series and partition theory.[9] In probability theory, the central binomial coefficient (2nn)\dbinom{2n}{n} arises as the numerator in the probability of observing exactly n heads in 2n independent flips of a fair coin, yielding (2nn)/4n\dbinom{2n}{n} / 4^n. For large n, this probability aligns with the central limit theorem, approximating the peak of the standardized normal distribution and highlighting the concentration of the binomial distribution around its mean.[10] Geometrically, the central binomial coefficient (2nn)\dbinom{2n}{n} counts the number of lattice points in the n-dimensional polytope defined by non-negative integer coordinates with the sum of coordinates at most n, equivalent to the n-dilate of the standard n-simplex. This interpretation ties into Ehrhart theory, where the number of lattice points in the tt-dilate of the simplex is given by the Ehrhart polynomial (t+nn)\dbinom{t + n}{n} evaluated at t=nt = n, bridging discrete geometry and volume computations. In algebraic geometry, it also emerges in enumerating integer points on certain hypersurfaces, such as those arising in toric varieties associated with scaled simplices.[11] Variations appear in graph theory, where the number of perfect matchings in the complete graph K2nK_{2n} is given by (2n1)!!=(2nn)n!/2n(2n-1)!! = \dbinom{2n}{n} \cdot n! / 2^n, linking the central binomial coefficient to enumerative combinatorics on matchings.

Algebraic Properties

Identities and Recurrences

The central binomial coefficient satisfies several fundamental identities and recurrence relations that highlight its algebraic structure. One key identity is the sum of squares of binomial coefficients, given by
k=0n(nk)2=(2nn). \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}.
This follows as a special case of Vandermonde's convolution identity,
k=0r(mk)(nrk)=(m+nr), \sum_{k=0}^r \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r},
by setting m=nm = n and r=nr = n, since (nnk)=(nk)\binom{n}{n-k} = \binom{n}{k}.[12] Vandermonde's identity itself admits a combinatorial proof: the right side counts the number of ways to choose rr elements from a set of m+nm+n elements by selecting kk from the first mm and rkr-k from the last nn, which equals the left side.[12] An algebraic proof uses the binomial theorem applied to (1+x)m+n=(1+x)m(1+x)n(1+x)^{m+n} = (1+x)^m (1+x)^n and equating coefficients of xrx^r.[12] Recurrence relations for the central binomial coefficient can be derived from Pascal's identity,
(nk)=(n1k)+(n1k1), \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1},
which has a combinatorial interpretation: the kk-subsets of an nn-set are partitioned based on whether they include a distinguished element.[12] Applying symmetry (2n1n)=(2n1n1)\binom{2n-1}{n} = \binom{2n-1}{n-1} and substituting into Pascal's identity for (2nn)\binom{2n}{n} yields (2nn)=2(2n1n)\binom{2n}{n} = 2 \binom{2n-1}{n}. Then, using Pascal's identity again on (2n1n)=2n1n(2n2n1)\binom{2n-1}{n} = \frac{2n-1}{n} \binom{2n-2}{n-1}, we obtain the ratio recurrence
(2nn)(2n2n1)=4n2n. \frac{\binom{2n}{n}}{\binom{2n-2}{n-1}} = \frac{4n-2}{n}.
This relation allows iterative computation of central binomial coefficients starting from (00)=1\binom{0}{0} = 1.[12] The central binomial coefficient also exhibits symmetry in the context of the binomial theorem. The expansion (1+x)2n=k=02n(2nk)xk(1+x)^{2n} = \sum_{k=0}^{2n} \binom{2n}{k} x^k is symmetric in the coefficients (2nk)=(2n2nk)\binom{2n}{k} = \binom{2n}{2n-k}, with the central term (2nn)\binom{2n}{n} appearing at k=nk=n. Setting x=1x=1 gives k=02n(2nk)=4n\sum_{k=0}^{2n} \binom{2n}{k} = 4^n, underscoring the central term's prominence.[12] A useful lower bound arises from this expansion: since the coefficients are unimodal and peak at the center, (2nn)\binom{2n}{n} is the largest term, and there are 2n+12n+1 terms summing to 4n4^n, it follows that
(2nn)4n2n+1, \binom{2n}{n} \geq \frac{4^n}{2n+1},
with equality only for n=0n=0. This bound provides scale for the growth of the central binomial coefficient.[13] Another important relation is the convolution of central binomial coefficients,
k=0n(2kk)(2(nk)nk)=4n, \sum_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n,
which follows from the Cauchy product of generating functions, as the square of (2kk)xk=114x\sum \binom{2k}{k} x^k = \frac{1}{\sqrt{1-4x}} yields 114x=4nxn\frac{1}{1-4x} = \sum 4^n x^n.[2]

Divisibility and Prime Factors

The pp-adic valuation vp((2nn))v_p\left(\binom{2n}{n}\right), which gives the highest power of a prime pp dividing the central binomial coefficient, can be determined using Kummer's theorem. This theorem states that vp((2nn))v_p\left(\binom{2n}{n}\right) equals the number of carries that occur when adding n+nn + n in base pp.[14] Equivalently, by de Polignac's (Legendre's) formula for the valuation of factorials,
vp((2nn))=2sp(n)sp(2n)p1, v_p\left(\binom{2n}{n}\right) = \frac{2s_p(n) - s_p(2n)}{p-1},
where sp(m)s_p(m) denotes the sum of the digits of mm in base pp. This expression counts the carries implicitly, as each carry reduces the total digit sum by a multiple of p1p-1.[15]
For the specific case p=2p=2, the formula simplifies to v2((2nn))=s2(n)v_2\left(\binom{2n}{n}\right) = s_2(n), where s2(n)s_2(n) is the number of 11s in the binary expansion of nn. This follows because 2n2n in binary is the bits of nn shifted left by one position (appending a 00), so s2(2n)=s2(n)s_2(2n) = s_2(n), yielding v2((2nn))=s2(n)v_2\left(\binom{2n}{n}\right) = s_2(n). To see this via Lucas' theorem generalized to higher powers, note that the 22-adic valuation arises from the iterative application of the mod-22 case combined with lifting; however, the digit-sum formula provides the exact exponent directly. For example, when n=7n=7 (binary 111111, so s2(7)=3s_2(7)=3), (147)=3432=23×429\binom{14}{7}=3432=2^3 \times 429, confirming v2=3v_2=3. When n=8n=8 (binary 10001000, s2(8)=1s_2(8)=1), (168)=12870=21×6435\binom{16}{8}=12870=2^1 \times 6435, confirming v2=1v_2=1.[15] For odd primes pp, the valuation vp((2nn))=2sp(n)sp(2n)p1v_p\left(\binom{2n}{n}\right) = \frac{2s_p(n) - s_p(2n)}{p-1} depends on carries when doubling nn in base pp. For instance, take p=3p=3 and n=5n=5 (base-33: 12312_3, s3(5)=3s_3(5)=3; 2n=10=10132n=10=101_3, s3(10)=2s_3(10)=2). Then v3((105))=2322=2v_3\left(\binom{10}{5}\right) = \frac{2 \cdot 3 - 2}{2} = 2, and indeed 252=32×28252 = 3^2 \times 28. Another example: p=5p=5, n=3n=3 (base-55: 353_5, s5(3)=3s_5(3)=3; 2n=6=1152n=6=11_5, s5(6)=2s_5(6)=2), so v5((63))=624=1v_5\left(\binom{6}{3}\right) = \frac{6-2}{4} = 1, and 20=51×420=5^1 \times 4.[15] Regarding square-freeness, Erdős and Graham conjectured that (2nn)\binom{2n}{n} is square-free (not divisible by p2p^2 for any prime pp) only for small nn, specifically n=1n=1 (22), n=2n=2 (66), and n=4n=4 (7070). This was proved in 1996 by Andrew Granville and Olivier Ramaré, who showed that for n>4n>4, (2nn)\binom{2n}{n} is always divisible by p2p^2 for some prime pp.[16] Their proof uses explicit bounds on exponential sums to demonstrate the scarcity of square-free binomial coefficients, with implications for the distribution of prime powers in binomial coefficients and related Diophantine problems in number theory. For n=3n=3, (63)=20=22×5\binom{6}{3}=20=2^2 \times 5 provides an early counterexample beyond the square-free cases, while for n=5n=5, 252=22×32×7252=2^2 \times 3^2 \times 7 is divisible by multiple squares.

Analytic Developments

Generating Functions

The ordinary generating function for the central binomial coefficients (2nn)\binom{2n}{n} is given by
n=0(2nn)xn=114x \sum_{n=0}^\infty \binom{2n}{n} x^n = \frac{1}{\sqrt{1-4x}}
for x<1/4|x| < 1/4.[17] This form arises from the generalized binomial theorem applied to the expansion of (1+y)α(1 + y)^\alpha, where α=1/2\alpha = -1/2 and y=4xy = -4x. Specifically, the generalized binomial coefficient is (1/2n)=(1/2)(3/2)(1/2n+1)n!=(1)n(2n1)!!2nn!\binom{-1/2}{n} = \frac{(-1/2)(-3/2)\cdots(-1/2 - n + 1)}{n!} = (-1)^n \frac{(2n-1)!!}{2^n n!}, and substituting y=4xy = -4x yields (1/2n)(4x)n=(2nn)xn\binom{-1/2}{n} (-4x)^n = \binom{2n}{n} x^n, confirming the series expansion.[18] The radius of convergence 1/41/4 follows from the nearest singularity of the right-hand side at x=1/4x = 1/4.[17] The exponential generating function is
n=0(2nn)xnn!=e2xI0(2x), \sum_{n=0}^\infty \binom{2n}{n} \frac{x^n}{n!} = e^{2x} I_0(2x),
where I0(z)I_0(z) denotes the modified Bessel function of the first kind, defined by the series I0(z)=m=01(m!)2(z2)2mI_0(z) = \sum_{m=0}^\infty \frac{1}{(m!)^2} \left( \frac{z}{2} \right)^{2m}.[19] This relation follows from the bivariate exponential generating function r,s0(r+sr)xrysr!s!=ex+yI0(2xy)\sum_{r,s \geq 0} \binom{r+s}{r} \frac{x^r y^s}{r! s!} = e^{x+y} I_0(2 \sqrt{xy}); setting x=yx = y extracts the central terms via the diagonal.[19] The modified Bessel function I0I_0 satisfies the differential equation z2w+zw(z2+02)w=0z^2 w'' + z w' - (z^2 + 0^2) w = 0 and appears in solutions to problems in heat conduction and wave propagation.[19] The generating function for the squares of the central binomial coefficients is
n=0(2nn)2xn=2πK(4x), \sum_{n=0}^\infty \binom{2n}{n}^2 x^n = \frac{2}{\pi} K(4 \sqrt{x}),
valid for x<1/16|x| < 1/16, where K(k)=0π/2(1k2sin2θ)1/2dθK(k) = \int_0^{\pi/2} (1 - k^2 \sin^2 \theta)^{-1/2} \, d\theta is the complete elliptic integral of the first kind.[20] This expression derives from the hypergeometric representation n=0(2nn)2xn=2F1(1/2,1/2;1;16x)\sum_{n=0}^\infty \binom{2n}{n}^2 x^n = {}_2F_1(1/2, 1/2; 1; 16x) and the known identity K(k)=π22F1(1/2,1/2;1;k2)K(k) = \frac{\pi}{2} {}_2F_1(1/2, 1/2; 1; k^2), with the argument k=4xk = 4 \sqrt{x} matching the parameter 16x=k216x = k^2.[20] The complete elliptic integral K(k)K(k) has a branch point at k=1k=1 and is real-valued for 0k<10 \leq k < 1, with applications in computing arc lengths of ellipses. These generating functions facilitate series expansions in analysis, such as Taylor series for algebraic and transcendental functions involving square roots and elliptic forms, and appear in integral representations for evaluating definite integrals over special functions.[21] For instance, the ordinary generating function enables closed-form sums in probabilistic models like random walks, while the elliptic form for squares aids in deriving identities for lattice path counts and modular forms.[20]

Asymptotic Approximations

The leading asymptotic approximation for the central binomial coefficient (2nn)\binom{2n}{n} is obtained by applying Stirling's formula, which states that n!2πn(n/e)nn! \sim \sqrt{2\pi n} (n/e)^n as nn \to \infty.[22] To derive this, substitute the approximation into the factorial expression for the binomial coefficient: (2nn)=(2n)!(n!)2\binom{2n}{n} = \frac{(2n)!}{(n!)^2}. Using Stirling's formula yields 4πn(2n/e)2n2πn(n/e)2n=4nπn\frac{\sqrt{4\pi n} (2n/e)^{2n}}{2\pi n (n/e)^{2n}} = \frac{4^n}{\sqrt{\pi n}}, so (2nn)4nπn\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}} as nn \to \infty.[23] A refined asymptotic expansion provides higher-order terms beyond the leading approximation. The full series is (2nn)=4nπn(118n+1128n2+O(1n3))\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \left(1 - \frac{1}{8n} + \frac{1}{128n^2} + O\left(\frac{1}{n^3}\right)\right), where the error term O(1/n3)O(1/n^3) ensures the remainder is bounded by a constant multiple of 1/n31/n^3 for sufficiently large nn.[3] This expansion arises from the asymptotic series for the logarithm of the gamma function, lnΓ(z+1)=(z+1/2)lnzz+12ln(2π)+k=1mB2k2k(2k1)z2k1+O(1/z2m+1)\ln \Gamma(z+1) = (z + 1/2)\ln z - z + \frac{1}{2}\ln(2\pi) + \sum_{k=1}^m \frac{B_{2k}}{2k(2k-1)z^{2k-1}} + O(1/z^{2m+1}), applied to the ratio of gamma functions expressing the binomial coefficient, with Bernoulli numbers B2kB_{2k} generating the coefficients.[3] Strict bounds sharpen the approximation with explicit inequalities. For all positive integers nn, 4nπ(n+1/2)<(2nn)<4nπn\frac{4^n}{\sqrt{\pi(n + 1/2)}} < \binom{2n}{n} < \frac{4^n}{\sqrt{\pi n}}.[23] These are proved using the integral representation (2nn)=24nπ0π/2cos2nθdθ\binom{2n}{n} = \frac{2 \cdot 4^n}{\pi} \int_0^{\pi/2} \cos^{2n} \theta \, d\theta and properties of convex functions or continued fraction expansions for the error in Stirling's formula.[23] The asymptotic behavior also connects to the local central limit theorem via the de Moivre-Laplace theorem, which approximates the binomial distribution Bin(2n,1/2)\mathrm{Bin}(2n, 1/2) near its mean nn. Specifically, P(X=n)=(2nn)/4n1/πnP(X = n) = \binom{2n}{n}/4^n \sim 1/\sqrt{\pi n} as nn \to \infty, implying the same leading approximation for the central binomial coefficient through normalization by the variance σ2=n/2\sigma^2 = n/2.

Connections and Applications

Relation to Catalan Numbers

The Catalan numbers CnC_n are defined for nonnegative integers nn by the explicit formula
Cn=1n+1(2nn), C_n = \frac{1}{n+1} \binom{2n}{n},
which expresses them as a normalized version of the central binomial coefficient (2nn)\binom{2n}{n}.[24] This relation highlights how Catalan numbers refine the unrestricted counting provided by the central binomial coefficient. A combinatorial justification for the formula arises from the reflection principle applied to Dyck paths, which are lattice paths from (0,0)(0,0) to (2n,0)(2n,0) using up steps (1,1)(1,1) and down steps (1,1)(1,-1) that never descend below the x-axis; the total number of unrestricted paths of this form is (2nn)\binom{2n}{n}, and the reflection principle subtracts the invalid paths that do go below to yield exactly CnC_n valid Dyck paths.[25] Equivalently, CnC_n counts Dyck words of length 2n2n, which correspond to properly balanced parentheses strings with nn pairs.[24] The ordinary generating function for the Catalan numbers,
C(x)=n=0Cnxn=114x2x C(x) = \sum_{n=0}^\infty C_n x^n = \frac{1 - \sqrt{1 - 4x}}{2x}
(with the understanding that C(0)=1C(0) = 1 and the constant term is handled appropriately), can be derived algebraically from the generating function for the central binomial coefficients,
n=0(2nn)xn=114x. \sum_{n=0}^\infty \binom{2n}{n} x^n = \frac{1}{\sqrt{1 - 4x}}.
Using the integral representation or direct manipulation of the coefficient formula Cn=1n+1(2nn)C_n = \frac{1}{n+1} \binom{2n}{n}, the generating function C(x)C(x) emerges as the solution to the quadratic equation C(x)=1+xC(x)2C(x) = 1 + x C(x)^2 arising from the Catalan recurrence, with the square root form linking back to the binomial expansion.[26] This connection underscores unique combinatorial properties of the Catalan numbers, which count restricted structures in contrast to the unrestricted paths tallied by (2nn)\binom{2n}{n}. For instance, CnC_n enumerates the number of full binary trees with n+1n+1 leaves (or nn internal nodes), the number of non-crossing partitions of a set of nn elements, and the number of triangulations of a convex (n+2)(n+2)-gon using non-intersecting diagonals.[24] These interpretations emphasize "non-crossing" or "balanced" configurations, refining the total (2nn)\binom{2n}{n} lattice paths from (0,0)(0,0) to (n,n)(n,n) by excluding those that cross above the main diagonal.[26] Asymptotically, the Catalan numbers satisfy
Cn4nn3/2π, C_n \sim \frac{4^n}{n^{3/2} \sqrt{\pi}},
which follows from applying Stirling's approximation to the central binomial coefficient (2nn)4nπn\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}} and incorporating the 1n+1\frac{1}{n+1} factor, yielding the extra n1/2n^{-1/2} decay.[27] This adjustment reflects the stricter constraints in Catalan structures compared to the binomial case. The sequence was first expressed in its modern form by the Belgian mathematician Eugène Charles Catalan in 1838, who derived CnC_n while solving the problem of dissecting convex polygons into triangles, building on earlier work with central binomial coefficients dating back to Euler in the 18th century.[28] The name "Catalan numbers" was later formalized in the mid-20th century.[24] In number theory, central binomial coefficients play a pivotal role in Paul Erdős's 1932 elementary proof of Bertrand's postulate, which states that there is always at least one prime number between nn and 2n2n for any integer n>1n > 1. The argument proceeds by assuming, for contradiction, that no such prime exists for some n1n \geq 1, and then bounding the central binomial coefficient (2nn)\binom{2n}{n} from above using the prime factorization theorem and properties of binomial coefficients. Specifically, (2nn)\binom{2n}{n} can be expressed as a product involving primes up to 2n2n, but under the assumption, all prime factors are at most nn, leading to an upper bound of pnplogp(2n)+O(1)\prod_{p \leq n} p^{\log_ p (2n) + O(1)}, which grows slower than the known lower bound for (2nn)\binom{2n}{n} derived from its position as the largest term in (1+1)2n=22n(1+1)^{2n} = 2^{2n}. This contradiction implies the existence of a prime in (n,2n)(n, 2n).[29] In analytic number theory, central binomial coefficients appear in generating functions that connect to the Riemann zeta function, particularly through Apéry-like identities expressing values of ζ(2n+2)\zeta(2n+2) as accelerated series involving these coefficients and hypergeometric terms. For instance, experimental and theoretical work has identified generating functions where (2nn)2xn(n+1)2k+1\sum \frac{\binom{2n}{n}^2 x^n}{ (n+1)^{2k+1} } or similar forms yield closed evaluations for even zeta values, aiding in series acceleration and modular form connections. These relations stem from the ordinary generating function n=0(2nn)xn=114x\sum_{n=0}^\infty \binom{2n}{n} x^n = \frac{1}{\sqrt{1-4x}}, which integrates into broader hypergeometric structures evaluated at zeta points. Central binomial coefficients find significant applications in probability and statistics, notably in modeling simple symmetric random walks on the integers, where (2nn)\binom{2n}{n} counts the number of paths of length 2n2n that return to the origin, yielding the return probability (2nn)/4n\binom{2n}{n} / 4^n. This discrete structure underlies the convergence of rescaled random walks to Brownian motion, with the central term providing the dominant contribution to the local limit theorem for the position distribution. In the continuous limit, hitting times for Brownian motion—such as the first passage time to a level—inherit approximations from binomial tail sums, linking discrete combinatorics to diffusion processes.[30] Beyond direct applications, central binomial coefficients relate to broader combinatorial sequences such as Motzkin numbers and Schröder numbers, which generalize the path-counting interpretations underlying Catalan numbers (themselves 1[n+1](/page/N+1)(2nn)\frac{1}{[n+1](/page/N+1)} \binom{2n}{n}). Motzkin numbers count lattice paths from (0,0)(0,0) to (n,0)(n,0) with steps (1,1)(1,1), (1,1)(1,-1), and (1,0)(1,0) not going below the x-axis, incorporating the central binomial as a base case when level steps are forbidden; Schröder numbers extend this to allow additional diagonal steps, yielding generating functions that refine the 114x\frac{1}{\sqrt{1-4x}} form. Identities involving squares of central binomial coefficients further link to enumerative problems in these sequences.[31][32]

References

User Avatar
No comments yet.