Definition:Binomial Coefficient
Contents |
Definition for Integers
Let $n \in \Z: n \ge 0$, and $k \in \Z$.
Then the symbol $\displaystyle \binom n k$ is interpreted as:
- $\displaystyle \binom n k = \begin{cases} \displaystyle \frac {n!} {k! \left({n - k}\right)!} & : 0 \le k \le n \\ 0 & : \text { otherwise } \\ \end{cases}$
The number $\displaystyle \binom n k$ is known as a binomial coefficient.
See the Binomial Theorem for the reason why.
$\displaystyle \binom n k$ is read n choose k.
Recursive Definition
The binomial coefficients can be defined using the following recurrence relation:
- $\displaystyle \binom n k = \begin{cases} 1 & : k = 0 \\ 0 & : k > n \\ \binom{n-1}{k-1} + \binom{n-1}{k} & : \text{otherwise} \end{cases}$
This relation is known as Pascal's Rule.
Definition for Real Numbers
Let $r \in \R, k \in \Z$.
Then $\displaystyle \binom r k$ is defined as:
- $\displaystyle \binom r k = \begin{cases} \dfrac {r^{\underline k}} {k!} & : k \ge 0 \\ & \\ 0 & : k < 0 \end{cases}$
where $r^{\underline k}$ is defined as the falling factorial.
That is, when $k \ge 0$:
- $\displaystyle \binom r k = \frac {r \left({r - 1}\right) \cdots \left({r - k + 1}\right)} {k \left({k - 1}\right) \cdots 1} = \prod_{j=1}^k \frac {r + 1 - j} j$
It can be seen that this agrees with the above definition when $r$ is an integer.
For most applications the integer form is sufficient.
Also see
Notation
The notation $\displaystyle \binom n k$ was introduced by Andreas von Ettingshausen in his 1826 work Die combinatorische Analysis. It appears to have become the de facto standard.
Alternative notations include $C(n, k)$, ${}^n C_k$, ${}_n C_k$, $C^n_k$ and $C_n^k$, all of which can be confusing.
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.
Sources
- J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 2.6$: Example $42 \ (2)$
- Richard A. Dean: Elements of Abstract Algebra (1966): $\S 0.6$: Theorem $8: \ 4$
- Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.6$
- Murray R. Spiegel: Mathematical Handbook of Formulas and Tables (1968): $3.5$
