Definition:Binomial Coefficient
Contents |
Definition
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 often read n choose k.
This arises from the fact that $\displaystyle \binom n k$ is the number of different ways $k$ objects can be chosen (irrespective of order) from a set of $n$ objects.
See Cardinality of Set of Subsets for a proof.
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 definition for integers when $r$ is an integer.
For most applications the integer form is sufficient.
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.
Also see
- Pascal's Rule for a recurrence relation for defining the binomial coefficients.
Sources
- Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 19$
- 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: \ (2)$
- Murray R. Spiegel: Mathematical Handbook of Formulas and Tables (1968): $3.5$
