binomial coefficient
Properties.
-
1.
is an integer (proof. (http://planetmath.org/NchooseRIsAnInteger)).
-
2.
.
-
3.
(Pascal’s rule).
-
4.
for all .
-
5.
.
-
6.
for .
-
7.
.
Properties 5 and 6 are the binomial theorem applied to and , respectively, although they also have purely combinatorial meaning.
Motivation
Suppose are integers. The below list shows some examples where the binomial coefficients appear.
-
•
constitute the coefficients when expanding the binomial – hence the name binomial coefficients. See Binomial Theorem.
-
•
is the number of ways to choose objects from a set with elements.
-
•
On the context of computer science, it also helps to see as the number of strings consisting of ones and zeros with ones and zeros. This equivalency comes from the fact that if be a finite set with elements, is the number of distinct subsets of with elements. For each subset of , consider the function
where whenever and otherwise (so is the characteristic function for ). For each , can be used to produce a unique bit string of length with exactly ones.
Notes
The 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 , there are also several variants. Especially in high school environments one encounters also or for .
Remark. It is sometimes convenient to set when . For example, property 7 above can be restated: . It can be shown that 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 | combinations |
Synonym | choose |
Related topic | PascalsRule |
Related topic | BinomialTheorem |
Related topic | BernoulliDistribution2 |
Related topic | MultinomialTheorem |
Related topic | ProofOfLucassTheorem2 |
Related topic | Factorial |
Related topic | CentralBinomialCoefficient |
Related topic | PascalsTriangle |
Related topic | TaylorSeriesViaDivision |
Related topic | CombinationsWithRepeatedElements |
Related topic | NonIsomorphicGroupsOfGivenOrder |
Related topic | AppellSeque |