The **binomial coefficient** of the natural number *n* and the integer *k* is defined to be the natural number
*n*, *k*) in the *n*-th row and 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.
### Combinatorics and statistics

### Divisors of binomial coefficients

### Formulas involving binomial coefficients

*x* + *y*)^{n} = (*y* + *x*)^{n}.
*x* = *y* = 1.
*x* = *y* = 1.
*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).
*m* = *k* = *n* and (4).
*F*(*n*+1) denotes the Fibonacci numbers. This formula about the diagonals of Pascal's triangle can be proven with induction using (3).
### Generalization to complex arguments

*a*_{k}. This is important in the theory of [difference equations]? and can be seen as a discrete analog of Taylor's theorem.

/ n \ n! | | = --------- ifn≥k≥ 0(1)\ k / k! (n-k)!

and

/ n \ | | = 0 ifk< 0 ork>n. \ k /

(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} and read as "*n* choose *k*" or "*n* over *k*".

The name "binomial coefficient" stems from the expansion of (*x* + *y*)^{n}, where the coefficient of the binomial *x*^{k} *y*^{n-k} is equal to C(*n*, *k*):

n (x + y)^{n}= ∑ C(n, k) x^{k}y^{n-k}(2)k=0

This is generalized by the binomial theorem.

An important recurrence relation is

- C(
*n*,*k*) + C(*n*,*k*+1) = C(*n*+1,*k*+1)**(3)**

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1which contains the numbers C(

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 binomial coefficients also occur in the formula for the binomial distribution in statistics and in the formula for a Bezier curve.

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 following formulas are occasionly useful:

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

From expansion (2) usingn∑ C(n,k) = 2^{n}(5)k=0

From expansion (2), after differentiating and substitutingn∑kC(n,k) =n2^{n-1}(6)k=1

By expanding (k∑ C(m,j) C(n,k-j) = C(m+n,k)(7)j=0

From expansion (7) usingn∑ C(n,k)^{2}= C(2n,n)(8)k=0

Here,n∑ C(n-k,k) = F(n+1)(9)k=0

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).z(z-1) (z-2) ... (z-k+1) C(z,k) = -------------------------(10)k!

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 constantsdp(z) = ∑a_{k}C(z,k)k=0