and
(Here m! denotes the factorial of m). The binomial coefficient of n and k is also written as C(n, k) or ^{n}C_{k} (C for combination) and read as "n choose k".
For example,
The binomial coefficients are the coefficients in the expansion of the binomial (x + y)^{n} (hence the name):
This is generalized by the binomial theorem, which allows the exponent n to be negative or a noninteger.
The important recurrence relation
row 0 1 row 1 1 1 row 2 1 2 1 row 3 1 3 3 1 row 4 1 4 6 4 1 row 5 1 5 10 10 5 1 row 6 1 6 15 20 15 6 1 row 7 1 7 21 35 35 21 7 1 row 8 1 8 28 56 70 56 28 8 1Row number n contains the numbers C(n, k) for k = 0,...,n. It is constructed by starting with ones at the outside and then always adding two adjacent numbers and writing the sum directly underneath. This method allows the quick calculation of binomial coefficients without the need for fractions or multiplications. For instance, by looking at row number 5 of the triangle, one can quickly read off that
The triangle was described by Zhu Shijie in 1303 AD in his book Precious Mirror of the Four Elements. In his book, Zhu mentioned the triangle as an ancient method (over 200 years before his time) for solving binomial coefficients, which indicated that the method was known to Chinese mathematicians five centuries before Pascal.
If you color in all even numbers on this triangle and leave the odd numbers blank, you get the Sierpinski triangle. Try coloring in multiples of 3, 4, 5, and so on and see what patterns emerge!

Binomial coefficients are of importance in combinatorics, because they provide ready formulas for certain frequent counting problems:
The binomial coefficients also occur in the formula for the binomial distribution in statistics and in the formula for a Bézier curve.
The following formulas are occasionally useful:
C(n, k) = C(n, nk) (4)This follows from expansion (2) by using (x + y)^{n} = (y + x)^{n}.
From expansion (2) using x = y = 1.
From expansion (2), after differentiating and substituting x = y = 1.
By expanding (x + y)^{n} (x + y)^{m} = (x + y)^{m+n} with (2) (note that C(n, k) is defined to be zero if k > n). This equation generalizes (3).
From expansion (7) using m = k = n and (4).
Here, F(n+1) denotes the Fibonacci numbers. This formula about the diagonals of Pascal's triangle can be proven with induction using (3).
This can be proven by induction on n using (3).
The prime divisors of C(n, k) can be interpreted as follows: if p is a prime number and p^{r} is the highest power of p which divides C(n, k), then r is equal to the number of natural numbers j such that the fractional part of k/p^{j} is bigger than the fractional part of n/p^{j}. In particular, C(n, k) is always divisible by n/gcd(n,k).
The binomial coefficient C(z, k) can be defined for any complex number z and any natural number k as follows:
This generalization is used in the formulation of the binomial theorem and satisfies properties (3) and (7).
For fixed k, the expression C(z, k) is a polynomial in z of degree k with rational coefficients. Every polyomial p(z) of degree d can be written in the form
with suitable constants a_{k}. This is important in the theory of difference equations[?] and can be seen as a discrete analog of Taylor's theorem.
Search Encyclopedia

Featured Article
