Definition:Binomial Coefficient
Definition
Definition 1
Let $n \in \Z_{\ge 0}$ and $k \in \Z$.
Then the binomial coefficient $\dbinom n k$ is defined as:
- $\dbinom n k = \begin{cases} \dfrac {n!} {k! \paren {n - k}!} & : 0 \le k \le n \\ & \\ 0 & : \text { otherwise } \end{cases}$
where $n!$ denotes the factorial of $n$.
Definition 2
Let $n \in \Z_{\ge 0}$ and $k \in \Z$.
The number of different ways $k$ objects can be chosen (irrespective of order) from a set of $n$ objects is denoted:
- $\dbinom n k$
This number $\dbinom n k$ is known as a binomial coefficient.
Definition 3
Let $n \in \Z_{\ge 0}$ and $k \in \Z$.
Then the binomial coefficient $\dbinom n k$ is defined as the coefficient of the term $a^k b^{n - k}$ in the expansion of $\paren {a + b}^n$.
Definition for Real Numbers
Let $r \in \R, k \in \Z$.
Then $\dbinom r k$ is defined as:
- $\dbinom r k = \begin {cases} \dfrac {r^{\underline k} } {k!} & : k \ge 0 \\ & \\ 0 & : k < 0 \end {cases}$
where $r^{\underline k}$ denotes the falling factorial.
That is, when $k \ge 0$:
- $\ds \dbinom r k = \dfrac {r \paren {r - 1} \cdots \paren {r - k + 1} } {k \paren {k - 1} \cdots 1} = \prod_{j \mathop = 1}^k \dfrac {r + 1 - j} j$
It can be seen that this agrees with the definition for integers when $r$ is an integer.
For most applications the integer form is sufficient.
Definition for Complex Numbers
Let $z, w \in \C$.
Then $\dbinom z w$ is defined as:
- $\dbinom z w := \ds \lim_{\zeta \mathop \to z} \lim_{\omega \mathop \to w} \dfrac {\map \Gamma {\zeta + 1} } {\map \Gamma {\omega + 1} \map \Gamma {\zeta - \omega + 1} }$
where $\Gamma$ denotes the Gamma function.
When $z$ is a negative integer and $w$ is not an integer, $\dbinom z w$ is infinite.
Definition for Multiindices
Let $k = \sequence {k_j}_{j \mathop \in J}$ and $\ell = \sequence {\ell_j}_{j \mathop \in J}$ be multiindices.
Let $\ell \le k$.
Then $\dbinom k \ell$ is defined as:
- $\ds \binom k \ell = \prod_{j \mathop \in J} \binom {k_j} {\ell_j}$
Note that since by definition only finitely many of the $k_j$ are non-zero, the product in the definition of $\dbinom k \ell$ is convergent.
Notation
The notation $\dbinom n k$ for the binomial coefficient was introduced by Andreas Freiherr von Ettingshausen in his $1826$ work Die kombinatorische Analysis, als Vorbereitungslehre zum Studium der theoretischen höheren Mathematik.
It appears to have become the de facto standard in recent years.
As a result, $\dbinom n k$ is frequently voiced the binomial coefficient $n$ over $k$.
Other notations include:
- $C \left({n, k}\right)$
- ${}^n C_k$
- ${}_n C_k$
- $C^n_k$
- ${C_n}^k$
all of which can cause a certain degree of confusion.
Examples
$2$ from $5$
The number of ways of choosing $2$ objects from a set of $5$ is:
- $\dbinom 5 2 = 10$
$5$ from $2$
- $\dbinom 2 5 = 0$
$2$ from $-5$
- $\dbinom {-5} 2 = 15$
$5$ from $-2$
- $\dbinom {-2} 5 = -6$
$3$ from $7$
The number of ways of choosing $3$ objects from a set of $7$ is:
- $\dbinom 7 3 = \dfrac {7 \times 6 \times 5} {3 \times 2 \times 1} = \dfrac {7!} {3! \, 4!} = 35$
$3$ from $8$
The number of ways of choosing $3$ objects from a set of $8$ is:
- $\dbinom 8 3 = \dfrac {8 \times 7 \times 6} {3 \times 2 \times 1} = \dfrac {8!} {3! \, 5!} = 56$
$4$ from $52$
The number of ways of choosing $4$ objects from a set of $52$ (for example, cards from a deck) is:
- $\dbinom {52} 4 = \dfrac {52 \times 51 \times 50 \times 49} {4 \times 3 \times 2 \times 1} = \dfrac {52!} {48! \, 4!} = 270 \, 725$
Number of Bridge Hands
The total number $N$ of possible different hands for a game of bridge is:
- $N = \dfrac {52!} {13! \, 39!} = 635 \ 013 \ 559 \ 600$
Historical Note
The binomial coefficients have been known about since at least the ancient Greeks and Romans, who were familiar with them for small values of $k$.
See the historical note to Pascal's Triangle for further history.
Also see
- Binomial Theorem for the reason behind the name of this entity
- Pascal's Rule for a recurrence relation for defining the binomial coefficients.
- Results about binomial coefficients can be found here.
Technical Note
The $\LaTeX$ code to render the binomial coefficient $\dbinom n k$ can be written in the following ways:
\dbinom n k
or:
\ds {n \choose k}
The \dbinom form is preferred on $\mathsf{Pr} \infty \mathsf{fWiki}$ because it is simpler.
It is in fact an abbreviated form of \ds \binom n k, which is the preferred construction when \ds is required for another entity in the expression.
While the form \binom n k is valid $\LaTeX$ syntax, it renders the entity in the reduced size inline style: $\binom n k$ which $\mathsf{Pr} \infty \mathsf{fWiki}$ does not endorse.
To render compound arguments, braces are needed to delimit the parameter when using \dbinom, but (confusingly) not \choose.
For example, to render $\dbinom {a + b} {c d}$ the following can be used:
\dbinom {a + b} {c d}
or:
\ds {a + b \choose c d}$\ds {a + b \choose c d}$
Again, for consistency across $\mathsf{Pr} \infty \mathsf{fWiki}$, the \dbinom form is preferred.