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}$.
Definitions
Consider integers $n$ and $k$ such that $0 \leq k \leq n$. The number of permutations $P(n, k)$, read “$n$ permute $k$,” is the number of permutations of $k$ of $n$ objects, that is, the number of ordered lists of $k$ different objects chosen from $n$ objects:
\[P(n, k) = n (n - 1) \cdots (n - k + 1) = \frac{n!}{(n - k)!}.\]Examples
-
Choosing $2$ of the $3$ letters $A$, $B$, and $C$
: $P(3, 2) = 6$
Choosing $2$ of the letters $A$, $B$, $C$ in order gives $P(3, 2) = 3 \cdot 2 = 6$ permutations, because there are $3$ choices for the first letter and then $2$ for the second. The six permutations are $AB$, $BA$, $AC$, $CA$, $BC$, and $CB$.
-
Electing a president and a vice president from a club of $10$ members
: $P(10, 2) = 90$
Electing a president and a vice president from $10$ members has $P(10, 2) = 10 \cdot 9 = 90$ outcomes, because there are $10$ choices for president and then $9$ for vice president.
Properties
- The product $n (n - 1) \cdots (n - k + 1)$ counts the choices one position at a time: there are $n$ choices for the first object, $n - 1$ for the second, and so on, down to $n - k + 1$ for the $k$th.
- The number of permutations of all $n$ objects is $P(n, n) = n!$.
- Each combination of $k$ objects can be put in order in $k!$ ways, so $P(n, k)$ is $k!$ times the binomial coefficient: \[P(n, k) = k! \binom{n}{k}.\]
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
-
Choosing $2$ of the $3$ letters $A$, $B$, and $C$
: $\binom{3}{2} = 3$
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$
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$
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*}\]
Examples
Each cell is the number of ways to make the choice in that row, counted with order (the number of permutations) or without order (the binomial coefficient).
| Example | number of permutations | binomial coefficient | Why |
|---|---|---|---|
| Choosing $2$ of the $3$ letters $A$, $B$, and $C$ | $P(3, 2) = 6$ | $\binom{3}{2} = 3$ | Choosing $2$ of the letters $A$, $B$, $C$ gives twice as many permutations as combinations, because each combination of $2$ letters can be put in order in $2! = 2$ ways. |
| Electing a president and a vice president from a club of $10$ members | $P(10, 2) = 90$ | – | |
| Choosing a committee of $2$ members from a club of $10$ members | – | $\binom{10}{2} = 45$ | |
| Drawing $6$ different lottery numbers from $1, 2, \dots, 49$, where only the set of numbers drawn matters | – | $\binom{49}{6} = 13\,983\,816$ |
Notes
- The number $P(n, k)$ is also written ${}n P_k$ (read “$n$ P $k$,” as on a calculator) or $n^{\underline{k}}$, the _falling factorial $n (n - 1) \cdots (n - k + 1)$, read “$n$ to the $k$ falling.” The number $\binom{n}{k}$ is also written ${}_n C_k$ or $C(n, k)$.
- Both counts assume that each object is chosen at most once; choosing with repetition gives $n^k$ ordered choices and $\binom{n + k - 1}{k}$ unordered choices.