binomial coefficient (original) (raw)

Properties.

1. 1. (nr) is an integer (proof. (http://planetmath.org/NchooseRIsAnInteger)).
2. 1. (nr)=(nn-r).
3. 1. (nr-1)+(nr)=(n+1r) (Pascal’s rule).
4. 1. (n0)=1=(nn) for all n.
5. 1. (n0)+(n1)+(n2)+⋯+(nn)=2n.
6. 1. (n0)-(n1)+(n2)-⋯+(-1)n⁢(nn)=0 for n>0.
7. 1. ∑t=kn(tk)=(n+1k+1).

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

Motivation

Suppose n≥r are integers. The below list shows some examples where the binomial coefficients appear.

• •
  (nr) constitute the coefficients when expanding thebinomial (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.
• •

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 alsoC⁢(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.