Binomial Coefficient

From PlasmaWiki

Jump to: navigation, search


The Binomial Coefficient

{n \choose k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1} = \frac{n!}{k!(n-k)!} \quad \mbox{if } n\geq k\geq 0 \qquad \mbox{(1)}

Read n 'choose' k, describes the number of ways to choose k elements from an n element set.

This may be extended to a more general definition which allows the upper index to be any complex number, and the lower index is any integer:

{r \choose k} = \frac{r \cdot (r-1) \cdots (r-k+1)}{k \cdot (k-1) \cdots 1} = \frac{r^{\underline{k}}}{k!} \quad \mbox{if } k \geq 0 \qquad \mbox{(2)}

Where r^{\underline{k}} is the rising factorial power.

The following is a table of the most useful identities. Eventually, each will link to a proof thereof.

The 'top ten' binomial coefficent identities. (From Concrete Mathematics)
Identity Constraints Name
{n \choose k} = \frac{n!}{k! (n - k)!}, integers n \geq k \geq 0. Factorial Expansion
{n \choose k} = {n \choose n - k}, integer n \geq 0, integer k. Symmetry
{r \choose k} = \frac{r}{k}{r - 1 \choose k - 1}, integer k \neq 0. Absorption/Extraction
{r \choose k} = {r - 1 \choose k} + {r - 1 \choose k - 1}, integer k. Addition/Induction
{r \choose k} = (-1)^k {k - r - 1 \choose k}, integer k. Upper Negation
{r \choose m}{m \choose k} = {r \choose k} {r - k \choose m - k}, integers m,k. Trinomial Revision
\sum_k{r \choose k} x^k y^{r-k} = (x + y)^r, integer r \geq 0, or | x / y | < 1. Binomial Theorem
\sum_{k \leq n}{r + k \choose k} = {r + n + 1 \choose n}, integer n. Parallel Summation
\sum_{0 \leq k \leq n}{k \choose m} = {n + 1 \choose m + 1}, integers m,n \geq 0. Upper Summation
\sum_k{r \choose k}{s \choose n - k} ={r + s \choose n}, integer n. Vandermonde Convolution
Retrieved from "http://localhost/wiki/Binomial_Coefficient"