Binomial coefficient

For natural numbers (taken to include 0) n and k, the binomial coefficient  can be defined as the coefficient of the monomial X^k in the expansion of (1 + X)ⁿ. The same coefficient also occurs (if k ≤ n) in the binomial formula

(valid for any elements x,y of a commutative ring), which explains the name "binomial coefficient".

http://en.wikipedia.org/wiki/Binomial_coefficient

Another occurrence of this number is in combinatorics, where it gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set. This number can be seen as equal to the one of the first definition, independently of any of the formulas below to compute it: if in each of the nfactors of the power (1 + X)ⁿ one temporarily labels the term X with an index i (running from 1 to n), then each subset of k indices gives after expansion a contribution X^k, and the coefficient of that monomial in the result will be the number of such subsets. This shows in particular that  is a natural number for any natural numbers n and k. There are many other combinatorial interpretations of binomial coefficients (counting problems for which the answer is given by a binomial coefficient expression), for instance the number of words formed of n bits (digits 0 or 1) whose sum is k is given by , while the number of ways to write  where every a_i is a nonnegative integer is given by . Most of these interpretations are easily seen to be equivalent to counting k-combinations.

reference -