binomial coefficient


For integers nr0 we define

(nr)=n!(n-r)!r!

and call such numbers binomial coefficientsMathworldPlanetmath.

Properties.

  1. 1.

    (nr) is an integer (proof. (http://planetmath.org/NchooseRIsAnInteger)).

  2. 2.

    (nr)=(nn-r).

  3. 3.

    (nr-1)+(nr)=(n+1r) (Pascal’s rule).

  4. 4.

    (n0)=1=(nn) for all n.

  5. 5.

    (n0)+(n1)+(n2)++(nn)=2n.

  6. 6.

    (n0)-(n1)+(n2)-+(-1)n(nn)=0 for n>0.

  7. 7.

    t=kn(tk)=(n+1k+1).

Properties 5 and 6 are the binomial theoremMathworldPlanetmath applied to (1+1)n and (1-1)n, respectively, although they also have purely combinatorial meaning.

Motivation

Suppose nr are integers. The below list shows some examples where the binomial coefficients appear.

  • (nr) constitute the coefficients when expanding the binomial (x+y)n – hence the name binomial coefficients. See Binomial Theorem.

  • (nr) is the number of ways to choose r objects from a set with n elements.

  • On the context of computer science, it also helps to see (nr) as the number of strings consisting of ones and zeros with r ones and n-r zeros. This equivalency comes from the fact that if S be a finite setMathworldPlanetmath with n elements, (nr) is the number of distinct subsets of S with r elements. For each subset T of S, consider the function

    XT:S{0,1}

    where XT(x)=1 whenever xT and 0 otherwise (so XT is the characteristic functionMathworldPlanetmathPlanetmathPlanetmath for T). For each T𝒫(S), XT can be used to produce a unique bit string of length n with exactly r ones.

Notes

The (nr) notation was first introduced by von Ettinghausen [1] in 1826, altough these numbers have been used long before that. See this page (http://planetmath.org/PascalsTriangle) for some notes on their history. Although the standard mathematical notation for the binomial coefficients is (nr), there are also several variants. Especially in high school environments one encounters also C(n,r) or Crn for (nr).

Remark. It is sometimes convenient to set (nr):=0 when r>n. For example, property 7 above can be restated: t=1n(tk)=(n+1k+1). It can be shown that (nr) is elementary recursive.

References

  • 1 N. Higham, Handbook of writing for the mathematical sciences, Society for Industrial and Applied Mathematics, 1998.
Title binomial coefficient
Canonical name BinomialCoefficient
Date of creation 2013-03-22 11:47:25
Last modified on 2013-03-22 11:47:25
Owner matte (1858)
Last modified by matte (1858)
Numerical id 32
Author matte (1858)
Entry type Definition
Classification msc 11B65
Classification msc 05A10
Classification msc 19D55
Classification msc 19K33
Classification msc 19D10
Synonym combinationsMathworldPlanetmath
Synonym choose
Related topic PascalsRule
Related topic BinomialTheorem
Related topic BernoulliDistribution2
Related topic MultinomialTheorem
Related topic ProofOfLucassTheorem2
Related topic FactorialMathworldPlanetmath
Related topic CentralBinomialCoefficient
Related topic PascalsTriangle
Related topic TaylorSeriesViaDivision
Related topic CombinationsWithRepeatedElements
Related topic NonIsomorphicGroupsOfGivenOrder
Related topic AppellSeque