Binomial coefficient
High school
Consider integers $n$ and $k$ such that $0 \leq k \leq n$. The binomial coefficient $\binom{n}{k}$, read “$n$ choose $k$,” is the number of combinations of $k$ of $n$ objects, that is, the number of ways to choose $k$ different objects from $n$ objects when the order does not matter:
\[\binom{n}{k} = \frac{n!}{k! \, (n - k)!}.\]Examples
Worked examples
-
Choosing $2$ of the $3$ letters $A$, $B$, and $C$
: $\binom{3}{2} = 3$
High school
Choosing $2$ of the letters $A$, $B$, $C$ without order gives $\binom{3}{2} = 3$ combinations, because each combination, such as $\setdef{A, B}$, comes from $2! = 2$ permutations, such as $AB$ and $BA$. The three combinations are $\setdef{A, B}$, $\setdef{A, C}$, and $\setdef{B, C}$.
-
Choosing a committee of $2$ members from a club of $10$ members
: $\binom{10}{2} = 45$
High school
Choosing a committee of $2$ from $10$ members has $\binom{10}{2} = (10 \cdot 9) / 2 = 45$ outcomes, which is half the $90$ ordered choices, because each committee can be ordered in $2$ ways.
-
Drawing $6$ different lottery numbers from $1, 2, \dots, 49$, where only the set of numbers drawn matters
: $\binom{49}{6} = 13\,983\,816$
High school
Drawing $6$ lottery numbers from $49$ has \[\binom{49}{6} = \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6!} = 13\,983\,816\] outcomes, so a single ticket wins with probability about $1$ in $14$ million.
Properties
- Each combination of $k$ objects can be put in order in $k!$ ways, so the binomial coefficient is the number of permutations divided by $k!$: \[\binom{n}{k} = \frac{P(n, k)}{k!}.\]
- Choosing $k$ of $n$ objects is the same as choosing the $n - k$ objects to leave out, so $\binom{n}{k} = \binom{n}{n - k}$.
- The binomial coefficient $\binom{n}{k}$ is the coefficient of $x^k$ in $(1 + x)^n$ (the binomial theorem): \[(1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k.\] The reason is that $(1 + x)^n$ is a product of $n$ factors $(1 + x)$. Multiplying out the product means choosing either $1$ or $x$ from each factor, and a choice gives $x^k$ when $x$ is chosen from exactly $k$ of the $n$ factors. So the number of terms equal to $x^k$ is the number of combinations of $k$ of the $n$ factors. For example, \[\begin{align*} (1 + x)^3 &= \binom{3}{0} + \binom{3}{1} x + \binom{3}{2} x^2 + \binom{3}{3} x^3 \\ &= 1 + 3 x + 3 x^2 + x^3. \end{align*}\]
Notes
The binomial coefficient $\binom{n}{k}$ is also written ${}_n C_k$ (read “$n$ C $k$,” as on a calculator) or $C(n, k)$.
Distinctions involving this term
- Number of permutations vs. binomial coefficient: Many counting problems ask how many ways there are to choose $k$ different objects from a set of $n$ objects. If the order of the chosen objects matters, then the answer is the number of permutations $P(n, k)$, read “$n$ permute $k$”: \[P(n, k) = \frac{n!}{(n - k)!}.\] If the order does not matter, then the answer is the binomial coefficient $\binom{n}{k},$ read “$n$ choose $k$”: \[\binom{n}{k} = \frac{n!}{k! \, (n - k)!}.\] Each combination of $k$ objects can be put in order in $k!$ ways, so $P(n, k) = k! \binom{n}{k}$.