The **binomial coefficient** of the natural number *n* and the integer *k* is defined to be the natural number

For example,

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

- (
*x*+*y*)^{5}=**1***x*^{5}+**5***x*^{4}*y*+**10***x*^{3}*y*^{2}+**10***x*^{2}*y*^{3}+**5***x**y*^{4}+**1***y*^{5}.

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!

Table of contents |

2 Formulas involving binomial coefficients 3 Divisors of binomial coefficients 4 Generalization to complex arguments |

Binomial coefficients are of importance in combinatorics, because they provide ready formulas for certain frequent counting problems:

- every set with
*n*elements has C(*n*,*k*) different subsets having*k*elements each (these are called*k*-combinations) - the number of strings of length
*n*containing*k*ones and*n-k*zeros is C(*n*,*k*) - there are C(
*n*+1,*k*) strings consisting of*k*ones and*n*zeros such that no two ones are adjacent - the number of sequences consisting of
*n*natural numbers whose sum equals*k*is C(*n*+*k*-1,*k*); this is also the number of ways to choose*k*elements from a set of*n*if repetitions are allowed. - the Catalan numbers have an easy formula involving binomial coefficients; they can be used to count various structures, such as treess and parenthesized expressions.

The following formulas are occasionally useful:

C(This follows from expansion (2) by using (n,k) = C(n,n-k)(4)

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:

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