Binomial Coefficient

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

The binomial coefficient 👁 (n; k)
is the number of ways of picking 👁 k
unordered outcomes from 👁 n
possibilities, also known as a combination or combinatorial number. The symbols 👁 _nC_k
and 👁 (n; k)
are used to denote a binomial coefficient, and are sometimes read as "👁 n
choose 👁 k
."

👁 (n; k)
therefore gives the number of k-subsets possible out of a set of 👁 n
distinct items. For example, The 2-subsets of 👁 {1,2,3,4}
are the six pairs 👁 {1,2}
, 👁 {1,3}
, 👁 {1,4}
, 👁 {2,3}
, 👁 {2,4}
, and 👁 {3,4}
, so 👁 (4; 2)=6
. In addition, the number of lattice paths from the origin 👁 (0,0)
to a point 👁 (a,b
) is the binomial coefficient 👁 (a+b; a)
(Hilton and Pedersen 1991).

The value of the binomial coefficient for nonnegative integers 👁 n
and 👁 k
with 👁 0<=k<=n
is given by

(Graham et al. 1989, p.157), where 👁 z!
denotes a factorial. Filling in values by row for 👁 k=0
, 1, ..., 👁 n
for increasing 👁 n
gives Pascal's triangle.

Writing the factorial as a gamma function 👁 z!=Gamma(z+1)
allows the binomial coefficient to be generalized to noninteger arguments (including complex 👁 x
and 👁 y
) as

The Roman coefficient (Roman 1992, Loeb 1995) is a generalization of the binomial coefficient. Whenever the binomial coefficient is defined, the Roman coefficient agrees with it. However, the Roman coefficients are defined for values for which the binomial coefficients are not.

Binomial coefficients for nonnegative integer 👁 y
give a polynomial in 👁 x

where 👁 (x)_y
is a Pochhammer symbol. These rational coefficients are sometimes known as "generalized binomial coefficients."

Using the gamma function symmetry formula

for integer 👁 a
, 👁 b
and complex 👁 s
, this definition can be extended to negative integer arguments, making it continuous at all integer arguments as well as continuous for all complex arguments except for negative integer 👁 x
and noninteger 👁 y
, in which case it is infinite (Kronenburg 2011). This definition, given by

for negative integer 👁 n
and integer 👁 k
is in agreement with the binomial theorem, and with combinatorial identities with a few special exceptions (Kronenburg 2011).

The binomial coefficient is implemented in the Wolfram Language as [n, k], which follows the above convention starting in Version 8. A variation 👁 [n,m]
that preserves Pascal's identity

and which therefore differs in value for negative integer 👁 n
, is implemented in the Wolfram Language as [n, k].

Plotting the binomial coefficient in the 👁 xy
-plane (Fowler 1996) gives the beautiful plot shown above, which has a very complicated graph for negative 👁 x
and 👁 y
and is therefore difficult to render using standard plotting programs.

For a positive integer 👁 n
, the binomial theorem gives

The finite difference analog of this identity is known as the Chu-Vandermonde identity. A similar formula holds for negative integers,

There are a number of elegant binomial sums.

The binomial coefficients satisfy the identities

The product of binomial coefficients is given by

where 👁 H(n)
is a hyperfactorial and 👁 n!
is a factorial.

As shown by Kummer in 1852, if 👁 p^k
is the largest power of a prime 👁 p
that divides 👁 (m+n; m)
, where 👁 m
and 👁 n
are nonnegative integers, then 👁 k
is the number of carries that occur when 👁 m
is added to 👁 n
in base 👁 p
(Graham et al. 1989, Exercise 5.36, p. 245; Ribenboim 1989; Vardi 1991, p. 68). Kummer's result can also be stated in the form that the exponent of a prime 👁 p
dividing 👁 (n; m)
is given by the number of integers 👁 j>=0
for which

where 👁 frac(x)
denotes the fractional part of 👁 x
. This inequality may be reduced to the study of the exponential sums 👁 sum_(n)Lambda(n)e(x/n)
, where 👁 Lambda(n)
is the Mangoldt function. Estimates of these sums are given by Jutila (1973, 1974), but recent improvements have been made by Granville and Ramare (1996).

R. W. Gosper showed that

for all primes, and conjectured that it holds only for primes. This was disproved when Skiena (1990) found it also holds for the composite number 👁 n=3×11×179
. Vardi (1991, p. 63) subsequently showed that 👁 n=p^2
is a solution whenever 👁 p
is a Wieferich prime and that if 👁 n=p^k
with 👁 k>3
is a solution, then so is 👁 n=p^(k-1)
. This allowed him to show that the only solutions for composite 👁 n<1.3×10^7
are 5907, 👁 1093^2
, and 👁 3511^2
, where 1093 and 3511 are Wieferich primes.

Consider the binomial coefficients 👁 f(n)=(2n-1; n)
, the first few of which are 1, 3, 10, 35, 126, ... (OEIS A001700). The generating function is

These numbers are squarefree only for 👁 n=2
, 3, 4, 6, 9, 10, 12, 36, ... (OEIS A046097), with no others known. It turns out that 👁 f(n)
is divisible by 4 unless 👁 n
belongs to a 2-automatic set 👁 S_2
, which happens to be the set of numbers whose binary representations contain at most two 1s: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, 18, ... (OEIS A048645). Similarly, 👁 f(n)
is divisible by 9 unless 👁 n
belongs to a 3-automatic set 👁 S_3
, consisting of numbers 👁 n
for which the representation of 👁 2n
in ternary consists entirely of 0s and 2s (except possibly for a pair of adjacent 1s). The initial elements of 👁 S_3
are 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 18, 19, 21, 22, 27, ... (OEIS A051382). If 👁 f(n)
is squarefree, then 👁 n
must belong to 👁 S=S_2 intersection S_3
. It is very probable that 👁 S
is finite, but no proof is known. Now, squares larger than 4 and 9 might also divide 👁 f(n)
, but by eliminating these two alone, the only possible 👁 n
for 👁 n<=2^(64)
are 1, 2, 3, 4, 6, 9, 10, 12, 18, 33, 34, 36, 40, 64, 66, 192, 256, 264, 272, 513, 514, 516, 576 768, 1026, 1056, 2304, 16392, 65664, 81920, 532480, and 545259520. All of these but the last have been checked, establishing that there are no other 👁 n
such that 👁 f(n)
is squarefree for 👁 n<=545259520
.

Erdős showed that the binomial coefficient 👁 (n; k)
with 👁 3<=k<=n/2
is a power of an integer for the single case 👁 (50; 3)=140^2
(Le Lionnais 1983, p. 48). Binomial coefficients 👁 T_(n-1)=(n; 2)
are squares 👁 a^2
when 👁 a^2
is a triangular number, which occur for 👁 a=1
, 6, 35, 204, 1189, 6930, ... (OEIS A001109). These values of 👁 a
have the corresponding values 👁 n=2
, 9, 50, 289, 1682, 9801, ... (OEIS A052436).

The binomial coefficients 👁 (n; |_n/2_|)
are called central binomial coefficients, where 👁 |_x_|
is the floor function, although the subset of coefficients 👁 (2n; n)
is sometimes also given this name. Erdős and Graham (1980, p. 71) conjectured that the central binomial coefficient 👁 (2n; n)
is never squarefree for 👁 n>4
, and this is sometimes known as the Erdős squarefree conjecture. Sárkőzy's theorem (Sárkőzy 1985) provides a partial solution which states that the binomial coefficient 👁 (2n; n)
is never squarefree for all sufficiently large 👁 n>=n_0
(Vardi 1991). Granville and Ramare (1996) proved that the only squarefree values are 👁 n=2
and 4. Sander (1992) subsequently showed that 👁 (2n+/-d; n)
are also never squarefree for sufficiently large 👁 n
as long as 👁 d
is not "too big."

For 👁 p
, 👁 q
, and 👁 r
distinct primes, then the function (◇) satisfies

(Vardi 1991, p. 66).

Most binomial coefficients 👁 (n; k)
with 👁 n>=2k
have a prime factor 👁 p<=n/k
, and Lacampagne et al. (1993) conjecture that this inequality is true for all 👁 n>17.125k
, or more strongly that any such binomial coefficient has least prime factor 👁 p<=n/k
or 👁 p<=17
with the exceptions 👁 (62; 6)
, 👁 (959; 56)
, 👁 (474; 66)
, 👁 (284; 28)
for which 👁 p=19
, 19, 23, 29 (Guy 1994, p. 84).

The binomial coefficient 👁 (m; n)
(mod 2) can be computed using the XOR operation 👁 n
XOR 👁 m
, making Pascal's triangle mod 2 very easy to construct.

Sondow (2005) and Sondow and Zudilin (2006) noted the inequality

for 👁 m
a positive integer and 👁 r>=1
a real number.

See also

Apéry Number, Balanced Binomial Coefficient, Ballot Problem, Bernoulli Triangle, Binomial, Binomial Distribution, Binomial Identity, Binomial Sums, Binomial Theorem, Central Binomial Coefficient, Choose, Christmas Stocking Theorem, Chu-Vandermonde Identity, Combination, Deficiency, Erdős Squarefree Conjecture, Exceptional Binomial Coefficient, Factorial, Fibonomial Coefficient, Gamma Function, Good Binomial Coefficient, k-Subset, Kings Problem, Klee's Identity, Lah Number, Multichoose, Multinomial Coefficient, Pascal's Formula, Permutation, q-Binomial Coefficient, Roman Coefficient, Sárkőzy's Theorem, Stanley's Identity, Star of David Theorem, Stolarsky-Harborth Constant, Strehl Identities, Székely Identity, Wolstenholme's Theorem Explore this topic in the MathWorld classroom

Related Wolfram sites

http://functions.wolfram.com/GammaBetaErf/Binomial/

Explore with Wolfram|Alpha

References

Abramowitz, M. and Stegun, I. A. (Eds.). "Binomial Coefficients." §24.1.1 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, pp. 10, 256, and 822-823, 1972.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, 1974.Conway, J. H. and Guy, R. K. In The Book of Numbers. New York: Springer-Verlag, pp. 66-74, 1996.Erdős, P.; Graham, R. L.; Nathanson, M. B.; and Jia, X. Old and New Problems and Results in Combinatorial Number Theory. New York: Springer-Verlag, 1998.Erdős, P.; Lacampagne, C. B.; and Selfridge, J. L. "Estimates of the Least Prime Factor of a Binomial Coefficient." Math. Comput. 61, 215-224, 1993.Feller, W. "Binomial Coefficients" and "Problems and Identities Involving Binomial Coefficients." §2.8 and 2.12 in An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. New York: Wiley, pp. 48-50 and 61-64, 1968.Fowler, D. "The Binomial Coefficient Function." Amer. Math. Monthly 103, 1-17, 1996.Graham, R. L.; Knuth, D. E.; and Patashnik, O. "Binomial Coefficients." Ch. 5 in Concrete Mathematics: A Foundation for Computer Science. Reading, MA: Addison-Wesley, pp. 153-242, 1989.Granville, A. "Arithmetic Properties of Binomial Coefficients. I. Binomial Coefficients Modulo Prime Powers." In Organic Mathematics. Proceedings of the Workshop Held in Burnaby, BC, December 12-14, 1995 (Ed. J. Borwein, P. Borwein, L. Jörgenson and R. Corless). Providence, RI: Amer. Math. Soc., pp. 253-276, 1997.Granville, A. "Arithmetic Properties of Binomial Coefficients." http://www.dms.umontreal.ca/~andrew/Binomial/.Granville, A. and Ramaré, O. "Explicit Bounds on Exponential Sums and the Scarcity of Squarefree Binomial Coefficients." Mathematika 43, 73-107, 1996.Guy, R. K. "Binomial Coefficients," "Largest Divisor of a Binomial Coefficient," and "Series Associated with the 👁 zeta
-Function." §B31, B33, and F17 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 84-85, 87-89, and 257-258, 1994.Harborth, H. "Number of Odd Binomial Coefficients." Not. Amer. Math. Soc. 23, 4, 1976.Hilton, P. and Pedersen, J. "Catalan Numbers, Their Generalization, and Their Uses." Math. Intel. 13, 64-75, 1991.Jutila, M. "On Numbers with a Large Prime Factor." J. Indian Math. Soc. 37, 43-53, 1973.Jutila, M. "On Numbers with a Large Prime Factor. II." J. Indian Math. Soc. 38, 125-130, 1974.Kronenburg, M. "The Binomial Coefficient for Negative Arguments." 18 May 2011. http://arxiv.org/abs/1105.3689/.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, 1983.Loeb, D. E. "A Generalization of the Binomial Coefficients." 9 Feb 1995. http://arxiv.org/abs/math/9502218.Ogilvy, C. S. "The Binomial Coefficients." Amer. Math. Monthly 57, 551-552, 1950.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Gamma Function, Beta Function, Factorials, Binomial Coefficients." §6.1 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 206-209, 1992.Prudnikov, A. P.; Marichev, O. I.; and Brychkow, Yu. A. Formula 41 in Integrals and Series, Vol. 1: Elementary Functions. Newark, NJ: Gordon & Breach, p. 611, 1986.Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, pp. 23-24, 1989.Riordan, J. "Inverse Relations and Combinatorial Identities." Amer. Math. Monthly 71, 485-498, 1964.Roman, S. "The Logarithmic Binomial Formula." Amer. Math. Monthly 99, 641-648, 1992.Sander, J. W. "On Prime Divisors of Binomial Coefficients." Bull. London Math. Soc. 24, 140-142, 1992.Sárkőzy, A. "On the Divisors of Binomial Coefficients, I." J. Number Th. 20, 70-80, 1985.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 262, 1990.Sloane, N. J. A. Sequences A001109/M4217, A001700/M2848, A046097, A048645, A051382, and A052436, in "The On-Line Encyclopedia of Integer Sequences."Sondow, J. "Problem 11132." Amer. Math. Monthly 112, 180, 2005.Sondow, J. and Zudilin, W. "Euler's Constant, 👁 q
-Logarithms, and Formulas of Ramanujan and Gosper." Ramanujan J. 12, 225-244, 2006.Spanier, J. and Oldham, K. B. "The Binomial Coefficients 👁 (nu; m)
." Ch. 6 in An Atlas of Functions. Washington, DC: Hemisphere, pp. 43-52, 1987.Sved, M. "Counting and Recounting." Math. Intel. 5, 21-26, 1983.Vardi, I. "Application to Binomial Coefficients," "Binomial Coefficients," "A Class of Solutions," "Computing Binomial Coefficients," and "Binomials Modulo an Integer." §2.2, 4.1, 4.2, 4.3, and 4.4 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 25-28 and 63-71, 1991.Wolfram, S. "Geometry of Binomial Coefficients." Amer. Math. Monthly 91, 566-571, 1984.

Referenced on Wolfram|Alpha

Binomial Coefficient

Cite this as:

Weisstein, Eric W. "Binomial Coefficient." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BinomialCoefficient.html

Subject classifications