Binomial coefficient

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The binomial coefficients can be arranged to form Pascal's triangle.
Visualisation of binomial expansion up to the 4th power

In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk. It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n. Under suitable circumstances the value of the coefficient is given by the expression \tfrac{n!}{k!\,(n-k)!}. Arranging binomial coefficients into rows for successive values of n, and in which k ranges from 0 to n, gives a triangular array called Pascal's triangle.

This family of numbers also arises in many areas of mathematics other than algebra, especially in combinatorics. \tbinom nk is often read aloud as "n choose k", because there are \tbinom nk ways to choose k elements from a set of n elements. The properties of binomial coefficients have led to extending the meaning of the symbol \tbinom nk beyond the basic case where n and k are nonnegative integers with kn; such expressions are still called binomial coefficients.

The notation \tbinom nk was introduced by Andreas von Ettingshausen in 1826,[1] although the numbers were already known centuries before that (see Pascal's triangle). The earliest known detailed discussion of binomial coefficients is in a tenth-century commentary, by Halayudha, on an ancient Sanskrit text, Pingala's Chandaḥśāstra. In about 1150, the Indian mathematician Bhaskaracharya gave an exposition of binomial coefficients in his book Lilavati.[2]

Alternative notations include C(n, k), nCk, nCk, Ckn, Cnk,[3] Cn,k in all of which the C stands for combinations or choices. Many calculators use similar variants of the C notation as it can be represented on a single-line display.

Definition and interpretations[edit]

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








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 n factors of the power (1 + X)n 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 Xk, and the coefficient of that monomial in the result will be the number of such subsets. This shows in particular that \tbinom nk 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 \tbinom nk, while the number of ways to write k=a_1+a_2+\cdots+a_n where every ai is a nonnegative integer is given by \tbinom{n+k-1}{n-1}. Most of these interpretations are easily seen to be equivalent to counting k-combinations.

Computing the value of binomial coefficients[edit]

Several methods exist to compute the value of \tbinom nk without actually expanding a binomial power or counting k-combinations.

Recursive formula[edit]

One method uses the recursive, purely additive, formula

  \binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \text{for all integers }n,k : 1\le k\le n-1,

with initial/boundary values

\binom n0 = \binom nn = 1 \quad \text{for all integers } n\ge0,


Multiplicative formula[edit]


\binom nk = \frac{n^{\underline{k}}}{k!} = \frac{n(n-1)(n-2)\cdots(n-(k-1))}{k(k-1)(k-2)\cdots 1}=\prod_{i=1}^k \frac{n-(k-i)}{i}=\prod_{i=1}^k \frac{n+1-i}{i},

where the numerator of the first fraction n^{\underline{k}} is expressed as a falling factorial power. This formula is easiest to understand for the combinatorial interpretation of binomial coefficients. The numerator gives the number of ways to select a sequence of k distinct objects, retaining the order of selection, from a set of n objects. The denominator counts the number of distinct sequences that define the same k-combination when order is disregarded.

Factorial formula[edit]


 \binom nk = \frac{n!}{k!\,(n-k)!} \quad \text{for }\ 0\leq k\leq n,


 \binom nk = \binom n{n-k} \quad \text{for }\ 0\leq k\leq n,







 \binom nk =  
 n^{\underline{k}}/k! & \text{if }\ k \le \frac{n}{2} \\
 n^{\underline{n-k}}/(n-k)! & \text{if }\ k > \frac{n}{2}

Generalization and connection to the binomial series[edit]

The multiplicative formula allows the definition of binomial coefficients to be extended[4] by replacing n by an arbitrary number α (negative, real, complex) or even an element of any commutative ring in which all positive integers are invertible:

\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1}
  \quad\text{for } k\in\N \text{ and arbitrary } \alpha.

With this definition one has a generalization of the binomial formula (with one of the variables set to 1), which justifies still calling the \tbinom\alpha k binomial coefficients:

 (1+X)^\alpha = \sum_{k=0}^\infty {\alpha \choose k} X^k.







(1+X)^\alpha(1+X)^\beta=(1+X)^{\alpha+\beta} \quad\text{and}\quad ((1+X)^\alpha)^\beta=(1+X)^{\alpha\beta}.

If α is a nonnegative integer n, then all terms with k > n are zero, and the infinite series becomes a finite sum, thereby recovering the binomial formula. However for other values of α, including negative integers and rational numbers, the series is really infinite.

Pascal's triangle[edit]

Main articles: Pascal's triangle and Pascal's rule

Pascal's rule is the important recurrence relation







which can be used to prove by mathematical induction that  \tbinom n k is a natural number for all n and k, (equivalent to the statement that k! divides the product of k consecutive integers), a fact that is not immediately obvious from formula (1).

Pascal's rule also gives rise to Pascal's triangle:

0: 1
1: 1 1
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1
5: 1 5 10 10 5 1
6: 1 6 15 20 15 6 1
7: 21 35 35 21
8: 28 56 70 56 28




Combinatorics and statistics[edit]


  • There are \tbinom n k ways to choose k elements from a set of n elements. See Combination.
  • There are \tbinom {n+k-1}k ways to choose k elements from a set of n elements if repetitions are allowed. See Multiset.
  • There are  \tbinom {n+k} k strings containing k ones and n zeros.
  • There are  \tbinom {n+1} k strings consisting of k ones and n zeros such that no two ones are adjacent.[5]
  • The Catalan numbers are \tfrac{1}{n+1}\tbinom{2n}{n}.
  • The binomial distribution in statistics is \tbinom n k p^k (1-p)^{n-k} \!.

Binomial coefficients as polynomials[edit]

For any nonnegative integer k, the expression \scriptstyle{\binom{t}{k}} can be simplified and defined as a polynomial divided by k!:

\binom{t}{k} =\frac{(t)_k}{k!}=\frac{(t)_k}{(k)_k}= \frac{t(t-1)(t-2)\cdots(t-k+1)}{k(k-1)(k-2)\cdots2 \cdot 1};\,\!

This presents a polynomial in t with rational coefficients.


For each k, the polynomial \tbinom{t}{k} can be characterized as the unique degree k polynomial p(t) satisfying p(0) = p(1) = ... = p(k − 1) = 0 and p(k) = 1.


\binom{t}{k} = \sum_{i=0}^k \left[{ k \atop i} \right]\frac{t^i}{k!}.

The derivative of \tbinom{t}{k} can be calculated by logarithmic differentiation:

\frac{\mathrm{d}}{\mathrm{d}t} \binom{t}{k} = \binom{t}{k} \sum_{i=0}^{k-1} \frac{1}{t-i}\,.


Over any field of characteristic 0 (that is, any field that contains the rational numbers), each polynomial p(t) of degree at most d is uniquely expressible as a linear combination \sum_{k=0}^d a_k \binom{t}{k} of binomial coefficients. The coefficient ak is the kth difference of the sequence p(0), p(1), …, p(k). Explicitly,[6]

a_k = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} p(i).






Integer-valued polynomials[edit]

Each polynomial \tbinom{t}{k} is integer-valued: it takes integer values at integer inputs. (One way to prove this is by induction on k, using Pascal's identity.) Therefore any integer linear combination of binomial coefficient polynomials is integer-valued too. Conversely, (4) shows that any integer-valued polynomial is an integer linear combination of these binomial coefficient polynomials. More generally, for any subring R of a characteristic 0 field K, a polynomial in K[t] takes values in R at all integers if and only if it is an R-linear combination of binomial coefficient polynomials.



9\tbinom{t}{2} + 6 \tbinom{t}{1} + 0\tbinom{t}{0}.\

Identities involving binomial coefficients[edit]


 \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}






and, with a little more work,

\binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}.

Moreover, the following may be useful:


For constant n, we have the following recurrence:

 \binom{n}{k} = \frac{n+1-k}{k} \binom{n}{k-1}.

Series involving binomial coefficients[edit]

The formula

 \sum_{k=0}^n \tbinom n k = 2^n







The formulas

\sum_{k=0}^n k \tbinom n k = n 2^{n-1}






and \sum_{k=0}^n k^2 \tbinom n k = (n + n^2)2^{n-2} follow from (2) after differentiating with respect to x (twice in the latter) and then substituting x = 1.


 \sum_{j=0}^k \tbinom m j \tbinom{n-m}{k-j} = \tbinom n k






and can be found by examination of the coefficient of x^k in the expansion of (1 + x)m (1 + x)n − m = (1 + x)n using equation (2). When m = 1, equation (7) reduces to equation (3).


\sum_{m=0}^n \tbinom m j \tbinom {n-m}{k-j}= \tbinom {n+1}{k+1}\,,






and can be found by examination of the coefficient of x^{n+1} in the expansion of x\left(\tfrac{x^{j}}{(1-x)^{j+1}}\right) \left(\tfrac{x^{k-j}}{(1-x)^{k-j+1}}\right) = \tfrac{x^{k+1}}{(1-x)^{k+2}} using \tfrac{x^l}{(1-x)^{l+1}} = \sum_{p=0}^\infty \tbinom p l x^p\,. When j = k, equation (8) gives

\sum_{m=0}^n \tbinom m k = \tbinom {n+1}{k+1}\,.


 \sum_{j=0}^m \tbinom m j ^2 = \tbinom {2m} m.






Let F(n) denote the n-th Fibonacci number. We obtain a formula about the diagonals of Pascal's triangle  \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \tbinom {n-k} k = F(n+1).


Another identity that follows from (8) with j=k-1 is  \sum_{j=k}^n (n+1-j) \tbinom {j-1} {k-1} = \tbinom {n+1}{k+1}.

Although there is no closed formula for

 \sum_{j=0}^k \tbinom n j

(unless one resorts to Hypergeometric functions),[7] one can again use (3) and induction, to show that for k = 0, ..., n − 1  \sum_{j=0}^k (-1)^j\tbinom n j = (-1)^k\tbinom {n-1}k

as well as[8]  \sum_{j=0}^n (-1)^j\tbinom n j = 0

[except in the trivial case where n = 0, where the result is 1 instead] which is itself a special case of the result from the theory of finite differences that for any polynomial P(x) of degree less than n,[9]  \sum_{j=0}^n (-1)^j\tbinom n j P(j) = 0. Differentiating (2) k times and setting x = −1 yields this for P(x)=x(x-1)\cdots(x-k+1), when 0 ≤ k < n, and the general case follows by taking linear combinations of these.


 \sum_{j=0}^n (-1)^j\tbinom n j P(n-j) = n!a_n






where a_n is the coefficient of degree n in P(x).

More generally for (10),

 \sum_{j=0}^n (-1)^j\tbinom n j P(m+(n-j)d) = d^n n! a_n where m and d are complex numbers. This follows immediately applying (10) to the polynomial Q(x):=P(m + dx) instead of P(x), and observing that Q(x) has still degree less than or equal to n, and that its coefficient of degree n is dnan.

The series \frac{k-1}k\sum_{j=0}^\infty \frac 1 {\binom {j+x} k}=\frac 1{\binom{x-1}{k-1}} is convergent for k ≥ 2. This formula is used in the analysis of the German tank problem. It follows from \frac{k-1}k\sum_{j=0}^{M}\frac 1 {\binom{j+x} k}=\frac 1{\binom{x-1}{k-1}}-\frac 1{\binom{M+x}{k-1}} which is proved by induction on M.

Using (9) one can derive \sum_{i=0}^{n}{i\binom{n}{i}^2}=\frac{n}{2}\binom{2n}{n} and \sum_{i=0}^n{i^2\binom{n}{i}^2}=n^2 \binom{2n-2}{n-1}.

Series multisection gives the following identity for the sum of binomial coefficients taken with a step s and offset t (0\leqslant t<s) as a closed-form sum of s terms:

\binom{n}{t}+\binom{n}{t+s}+\binom{n}{t+2s}+\ldots=\frac{1}{s}\sum_{j=0}^{s-1}\left(2\cos\frac{\pi j}{s}\right)^n\cos\frac{\pi(n-2t)j}{s}.

Identities with combinatorial proofs[edit]

Many identities involving binomial coefficients can be proved by combinatorial means. For example, the following identity for nonnegative integers {n} \geq {q} (which reduces to (6) when q = 1):

\sum_{k=q}^n \tbinom n k \tbinom k q = 2^{n-q}\tbinom n q

can be given a double counting proof as follows. The left side counts the number of ways of selecting a subset of [n] = {1, 2, …, n} with at least q elements, and marking q elements among those selected. The right side counts the same parameter, because there are \tbinom n q ways of choosing a set of q marks and they occur in all subsets that additionally contain some subset of the remaining elements, of which there are 2^{n-q}.

In the Pascal's rule

{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}



\sum_{k=0}^n \tbinom n k ^2 = \tbinom {2n} n.

Suppose you have 2n empty squares arranged in a row and you want to mark (select) n of them. There are \tbinom {2n}n ways to do this. On the other hand, you may select your n squares by selecting k squares from among the first n and n-k squares from the remaining n squares; any k from 0 to n will work. This gives

\sum_{k=0}^n\tbinom  n k\tbinom n{n-k} = \tbinom {2n} n.

Now apply (5) to get the result.

The identity (9),


has the following combinatorial proof. The number \tbinom{n-k}{k} denotes the number of paths in a two-dimensional lattice from (0,0) to (k,n-k) using steps (0,1) and (1,1). This is easy to see: there are (n-k) steps in total and one may choose the k (1,1) steps. Now, replace each (1,1) step by a (0,2) step; note that there are exactly k. Then one arrives at point (0,n) using steps (0,1) and (0,2). Doing this for all k between 0 and \lfloor\frac{n}{2}\rfloor gives all paths from (0,0) to (0,n) using steps (0,1) and (0,2). Clearly, there are exactly F(n+1) such paths.

Sum of coefficients row[edit]

The number of k-combinations for all k, \sum_{0\leq{k}\leq{n}}\binom nk = 2^n, is the sum of the nth row (counting from 0) of the binomial coefficients. These combinations are enumerated by the 1 digits of the set of base 2 numbers counting from 0 to 2^n - 1, where each digit position is an item from the set of n.

Dixon's identity[edit]

Dixon's identity is

\sum_{k=-a}^{a}(-1)^{k}{2a\choose k+a}^3 =\frac{(3a)!}{(a!)^3}

or, more generally,

\sum_{k=-a}^a(-1)^k{a+b\choose a+k} {b+c\choose b+k}{c+a\choose c+k}  = \frac{(a+b+c)!}{a!\,b!\,c!}\,,


Continuous identities[edit]

Certain trigonometric integrals have values expressible in terms of binomial coefficients:

For \textstyle m, n \in \mathbb{N}

\int_{-\pi}^{\pi} \cos((2m-n)x)\cos^n x\ dx = \frac{\pi}{2^{n-1}} \binom{n}{m}

\int_{-\pi}^{\pi} \sin((2m-n)x)\sin^n x\ dx = \left \{
(-1)^{m+(n+1)/2} \frac{\pi}{2^{n-1}} \binom{n}{m} & n \text{ odd} \\
0 & \text{otherwise} \\
\end{array} \right.

0 & \text{otherwise} \\
\end{array} \right.


Generating functions[edit]

Ordinary generating functions[edit]

For a fixed n, the ordinary generating function of the sequence {n\choose 0},\;{n\choose 1},\;{n\choose 2},\;\ldots is:

\sum_k {n\choose k} x^k = (1+x)^n.

For a fixed k, the ordinary generating function of the sequence {0\choose k},\;{1\choose k},\;{2\choose k},\;\ldots is:

\sum_{n=k}^\infty {n\choose k} y^n = \frac{y^k}{(1-y)^{k+1}}.

The bivariate generating function of the binomial coefficients is:

\sum_{n,k} {n\choose k} x^k y^n = \frac{1}{1-y-xy}.


\sum_{n,k} {n+k\choose k} x^k y^n = \frac{1}{1-x-y}.

Exponential generating function[edit]

The exponential bivariate generating function of the binomial coefficients is:

\sum_{n,k} \frac{1}{(n+k)!}{n+k\choose k} x^k y^n = e^{x+y}.

Divisibility properties[edit]

Main articles: Kummer's theorem and Lucas' theorem

In 1852, Kummer proved that if m and n are nonnegative integers and p is a prime number, then the largest power of p dividing \tbinom{m+n}{m} equals pc, where c is the number of carries when m and n are added in base p. Equivalently, the exponent of a prime p in \tbinom n k equals the number of nonnegative integers j such that the fractional part of k/pj is greater than the fractional part of n/pj. It can be deduced from this that \tbinom n k is divisible by n/gcd(n,k). In particular therefore it follows that p divides \tbinom{p^r}{s} for all positive integers r and s such that s < pr. However this is not true of higher powers of p: for example 9 does not divide \tbinom{9}{6}.

A somewhat surprising result by David Singmaster (1974) is that any integer divides almost all binomial coefficients. More precisely, fix an integer d and let f(N) denote the number of binomial coefficients \tbinom n k with n < N such that d divides \tbinom n k. Then

 \lim_{N\to\infty} \frac{f(N)}{N(N+1)/2} = 1.

Since the number of binomial coefficients \tbinom n k with n < N is N(N + 1) / 2, this implies that the density of binomial coefficients divisible by d goes to 1.


 \binom n 1, \binom n 2, \ldots, \binom n{n-1}

are divisible by n.

Proof: When p is prime, p divides

 \binom p k = \frac{p \cdot (p-1) \cdots (p-k+1)}{k \cdot (k-1) \cdots 1} for all 0 < k < p

because it is a natural number and the numerator has a prime factor p but the denominator does not have a prime factor p.


 \binom n p = \frac{n(n-1)(n-2)\cdots(n-p+1)}{p!}=\frac{k(n-1)(n-2)\cdots(n-p+1)}{(p-1)!}\not\equiv 0 \pmod{n}


Bounds and asymptotic formulas[edit]

The following bounds for \tbinom n k hold:

\left(\frac{n}{k}\right)^k \le {n \choose k}  \le \frac{n^k}{k!} \le \left(\frac{n\cdot e}{k}\right)^k for 1 ≤ k ≤ n.

Stirling's approximation yields the bounds:

\sqrt{n}{2n \choose n} \ge 2^{2n-1} and, in general, \sqrt{n}{mn \choose n} \ge \frac{m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}} for m ≥ 2 and n ≥ 1,

and the approximation

 {2n \choose n} \sim \frac{4^n}{\sqrt{\pi n}} as n\rightarrow\infty\,.

For both n and k much larger than 1, Stirling's approximation also yields the following asymptotic approximation:

\log_2{n \choose k} \sim n H\left(\frac{k}{n}\right)

where H(\epsilon) = -\epsilon\log_2(\epsilon) -(1-\epsilon)\log_2(1-\epsilon) is the binary entropy of \epsilon. More precisely, for all integers n \geq k \geq 1 with \epsilon \doteq k/n \leq 1/2, we can estimate the sum of the first k+1 binomial coefficients as follows:[10]

\frac{1}{\sqrt{8n\epsilon(1-\epsilon)}} \cdot 2^{H(\epsilon) \cdot n} \leq \sum_{i=0}^{k} \binom{n}{i} \leq 2^{H(\epsilon) \cdot n}\,.

When n is large and k is much smaller than n, one can also write

{n \choose k} = \frac{n(n-1)\dots(n-k+1)}{k!} \approx \frac{(n-k/2)^k }{ k^k e^{-k} \sqrt{2\pi k}} = \frac{(n/k-0.5)^k e^k }{ \sqrt{2\pi k}}\,,

and therefore

\log{n \choose k} \approx k \ln(n/k-0.5) + k - 0.5 \ln(2 \pi k)\,.

If more precision is desired, one can approximate \ln{(n(n-1)\dots(n-k+1))} with an integral, obtaining

\log{n \choose k} \approx (n+0.5) \ln\frac{n+0.5}{n-k+0.5} + k \ln \frac{n-k+0.5}{k} - 0.5 \ln(2 \pi k)

For n=20 and k=10, \log{\tbinom n k} \approx 12.127, and these approximations yield 12.312 and 12.133 respectively.


(-1)^k {z \choose k}= {-z+k-1 \choose k} = \frac{1}{\Gamma(-z)} \frac{1}{(k+1)^{z+1}} \prod_{j=k+1} \frac{(1+\frac{1}{j})^{-z-1}}{1-\frac{z+1}{j}}

yields the asymptotic formulas

{z \choose k} \approx \frac{(-1)^k}{\Gamma(-z) k^{z+1}} \qquad  \mathrm{and}  \qquad {z+k \choose k} = \frac{k^z}{\Gamma(z+1)}\left( 1+\frac{z(z+1)}{2k}+\mathcal{O}\left(k^{-2}\right)\right)

as k \to \infty.

This asymptotic behaviour is contained in the approximation

{z+k \choose k}\approx \frac{e^{z(H_k-\gamma)}}{\Gamma(z+1)}

as well. (Here H_k is the k-th harmonic number and \gamma is the Euler–Mascheroni constant.)

Further, the asymptotic formula

\frac{{z+k\choose j}}{{k\choose j}}\to \left(1-\frac{j}{k}\right)^{-z}\quad\text{and}\quad \frac{{j\choose j-k}}{{j-z\choose j-k}}\to \left(\frac{j}{k}\right)^z

hold true, whenever k\to\infty and j/k\to x for some complex number x.


\sum_{i=0}^k {n \choose i} \leq \sum_{i=0}^k n^i\cdot 1^{k-i} = (1+n)^k


For large values of n, the following gives an approximation of the binomial coefficient based on its relation to the normal distribution

 \binom{n}{k} = \frac{2^n}{\sqrt{\frac{1}{2}n \pi }} e^{-\frac{(k-(n/2))^2}{n/2}}\left[1+O\left(\frac{1}{\sqrt{n}}\right)\right].

This follows from the bounds on the Central Limit Theorem, taking a normal distribution with the same expectation and variance as the binomial distribution (np, np(1-p)), centering the probabilities, by setting p = 1 - p = 1/2, and multiplying both by 2n.


Generalization to multinomials[edit]

Main article: Multinomial theorem


{n\choose k_1,k_2,\ldots,k_r} =\frac{n!}{k_1!k_2!\cdots k_r!}




(x_1 + x_2 + \cdots + x_r)^n.\

The case r = 2 gives binomial coefficients:

{n\choose k_1,k_2}={n\choose k_1, n-k_1}={n\choose k_1}= {n\choose k_2}.



{n\choose k_1,k_2,\ldots,k_r} ={n-1\choose k_1-1,k_2,\ldots,k_r}+{n-1\choose k_1,k_2-1,\ldots,k_r}+\ldots+{n-1\choose k_1,k_2,\ldots,k_r-1}

and symmetry:

{n\choose k_1,k_2,\ldots,k_r} ={n\choose k_{\sigma_1},k_{\sigma_2},\ldots,k_{\sigma_r}}

where (\sigma_i) is a permutation of (1,2,...,r).

Taylor series[edit]

Using Stirling numbers of the first kind the series expansion around any arbitrarily chosen point z_0 is

\begin{align} {z \choose k} = \frac{1}{k!}\sum_{i=0}^k z^i s_{k,i}&=\sum_{i=0}^k (z- z_0)^i \sum_{j=i}^k {z_0 \choose j-i} \frac{s_{k+i-j,i}}{(k+i-j)!} \\ &=\sum_{i=0}^k (z-z_0)^i \sum_{j=i}^k z_0^{j-i} {j \choose i} \frac{s_{k,j}}{k!}.\end{align}

Binomial coefficient with n = ½[edit]

The definition of the binomial coefficients can be extended to the case where n is real and k is integer.

In particular, the following identity holds for any non-negative integer k :


This shows up when expanding \sqrt{1+x} into a power series using the Newton binomial series :


Identity for the product of binomial coefficients[edit]


 {z \choose m} {z\choose n} = \sum_{k=0}^m {m+n-k\choose k,m-k,n-k} {z\choose m+n-k}


Partial fraction decomposition[edit]

The partial fraction decomposition of the reciprocal is given by

\frac{1}{{z \choose n}}= \sum_{i=0}^{n-1} (-1)^{n-1-i} {n \choose i} \frac{n-i}{z-i}, and \frac{1}{{z+n \choose n}}= \sum_{i=1}^n (-1)^{i-1} {n \choose i} \frac{i}{z+i}.

Newton's binomial series[edit]

Main article: binomial series


 (1+z)^{\alpha} = \sum_{n=0}^{\infty}{\alpha\choose n}z^n = 1+{\alpha\choose1}z+{\alpha\choose 2}z^2+\cdots.



\frac{1}{(1-z)^{\alpha+1}} = \sum_{n=0}^{\infty}{n+\alpha \choose n}z^n

where the identity

{n \choose k} = (-1)^k {k-n-1 \choose k}

is applied.

Multiset (rising) binomial coefficient[edit]


let f = n = r + (k - 1) and r = f - (k - 1).




(f)_{k}=f^{\underline k}=(f-k+1)\cdots(f-3)\cdot(f-2)\cdot(f-1)\cdot f,

and the corresponding rising factorial as

{\color{white}{ \big|}}r^{(k)}=\,r^{\overline k}=\,r\cdot(r+1)\cdot(r+2)\cdot(r+3)\cdots(r+k-1);

so, for example,

17\cdot18\cdot19\cdot20\cdot21=(21)_{5}=21^{\underline 5}=17^{\overline 5}=17^{(5)}.

Then the binomial coefficients may be written as

\binom{f}{k} = \frac{(f)_{k}}{k!} =\frac{(f-k+1)\cdots(f-2)\cdot(f-1)\cdot f}{1\cdot2\cdot3\cdot4\cdot5\cdots k},


\left(\!\!\binom{r}{k}\!\!\right)=\frac{r^{(k)}}{k!}=\frac{r\cdot(r+1)\cdot(r+2)\cdots(r+k-1)}{1\cdot2\cdot3\cdot4\cdot5\cdots k}.

Generalization to negative integers[edit]

For any n,

\begin{align}\binom{-n}{k} &= \frac{-n\cdot-(n+1)\dots-(n+k-2)\cdot-(n+k-1)}{k!}\\
&=(-1)^k\;\frac{n\cdot(n+1)\cdot(n+2)\cdots (n + k - 1)}{k!}\\

In particular, binomial coefficients evaluated at negative integers are given by signed multiset coefficients. In the special case n = -1, this reduces to (-1)^k=\binom{-1}{k}=\left(\!\!\binom{-k}{k}\!\!\right) \,.


\begin{align}\binom{-4}{7} &= \frac

Two real or complex valued arguments[edit]


{x \choose y}= \frac{\Gamma(x+1)}{\Gamma(y+1) \Gamma(x-y+1)}= \frac{1}{(x+1) \Beta(x-y+1,y+1)}.

This definition inherits these following additional properties from \Gamma:

{x \choose y}= \frac{\sin (y \pi)}{\sin(x \pi)} {-y-1 \choose -x-1}= \frac{\sin((x-y) \pi)}{\sin (x \pi)} {y-x-1 \choose y};


{x \choose y} \cdot {y \choose x}= \frac{\sin((x-y) \pi)}{(x-y) \pi}.

The resulting function has been little-studied, apparently first being graphed in (Fowler 1996). Notably, many binomial identities fail: \textstyle{{n \choose m} = {n \choose n-m}} but \textstyle{{-n \choose m} = {-n \choose -n-m}} for n positive (so -n negative). The behavior is quite complex, and markedly different in various octants (that is, with respect to the x and y axes and the line y=x), with the behavior for negative x having singularities at negative integer values and a checkerboard of positive and negative regions:

  • in the octant 0 \leq y \leq x it is a smoothly interpolated form of the usual binomial, with a ridge ("Pascal's ridge").
  • in the octant 0 \leq x \leq y and in the quadrant x \geq 0, y \leq 0 the function is close to zero.
  • in the quadrant x \leq 0, y \geq 0 the function is alternatingly very large positive and negative on the parallelograms with vertices (-n,m+1), (-n,m), (-n-1,m-1), (-n-1,m)
  • in the octant 0 > x > y the behavior is again alternatingly very large positive and negative, but on a square grid.
  • in the octant -1 > y > x + 1 it is close to zero, except for near the singularities.

Generalization to q-series[edit]


Generalization to infinite cardinals[edit]


{\alpha \choose \beta} = | \{ B \subseteq A : |B| = \beta \} |

where A is some set with cardinality \alpha. One can show that the generalized binomial coefficient is well-defined, in the sense that no matter what set we choose to represent the cardinal number \alpha, {\alpha \choose \beta} will remain the same. For finite cardinals, this definition coincides with the standard definition of the binomial coefficient.

Assuming the Axiom of Choice, one can show that {\alpha \choose \alpha} = 2^{\alpha} for any infinite cardinal \alpha.

Binomial coefficient in programming languages[edit]



from math import factorial
def binomialCoefficient(n, k):


def binomialCoefficient(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    c = 1
    for i in range(k):
    return c

(In Python, range(k) produces a list from 0 to k-1.)


def binomialCoefficient(n, k):
    if k < 0 or k > n:
        return 0
    if k > n - k: # take advantage of symmetry
        k = n - k
    if k == 0 or n <= 1:
    	return 1


{n \choose k+1} = \frac{n-k}{k+1} {n \choose k}

Rational arithmetic can be easily avoided using integer division

{n \choose k+1} = \left[(n-k) {n \choose k}\right] \div (k+1)

The following implementation uses all these ideas

(define (binomial n k)
  (define (binomial-iter n k i prev)
    (if (>= i k)
  (if (< k (-  n k))
    (binomial-iter n k 0 1)


  {n \choose k} = \frac{n!}{k!\,(n-k)!} = \frac{\Gamma(n+1)}{\Gamma(k+1)\,\Gamma(n-k+1)} = \exp(\ln\Gamma(n+1)-\ln\Gamma(k+1)-\ln\Gamma(n-k+1)),

where \ln\Gamma(n) denotes the natural logarithm of the gamma function at n. It is a special function that is easily computed and is standard in some programming languages such as using log_gamma in Maxima, LogGamma in Mathematica, gammaln in MATLAB, or lgamma in R. Roundoff error may cause the returned value to not be an integer.

See also[edit]


  1. ^ Higham (1998)
  3. ^ Shilov (1977)
  4. ^ See (Graham, Knuth & Patashnik 1994), which also defines \tbinom n k = 0 for k<0. Alternative generalizations, such as to two real or complex valued arguments using the Gamma function assign nonzero values to \tbinom n k for k<0, but this causes most binomial coefficient identities to fail, and thus is not widely used majority of definitions. One such choice of nonzero values leads to the aesthetically pleasing "Pascal windmill" in Hilton, Holton and Pedersen, Mathematical reflections: in a room with many mirrors, Springer, 1997, but causes even Pascal's identity to fail (at the origin).
  7. ^ Boardman, Michael (2004), "The Egg-Drop Numbers", Mathematics Magazine 77 (5): 368–372, JSTOR 3219201, MR 1573776, it is well known that there is no closed form (that is, direct formula) for the partial sum of binomial coefficients .
  8. ^ see induction developed in eq (7) p. 1389 in Aupetit, Michael (2009), "Nearly homogeneous multi-partitioning with a deterministic generator", Neurocomputing 72 (7-9): 1379–1389, doi:10.1016/j.neucom.2008.12.024, ISSN 0925-2312 .
  9. ^ Ruiz, Sebastian (1996). "An Algebraic Identity Leading to Wilson's Theorem". The Mathematical Gazette 80 (489): 579–582. doi:10.2307/3618534. 
  11. ^ Munarini, Emanuele (2011), "Riordan matrices and sums of harmonic numbers", Applicable Analysis and Discrete Mathematics 5 (2): 176–200, doi:10.2298/AADM110609014M, MR 2867317 .


External links[edit]
