Counting combinations and permutations.
Many computational problems involve calculating the number of combinations or permutations (arrangements) of values (e.g. elements of a set). Sometimes, this requires that we generate every such combination or permutation, and keep a count; such operations are beyond the scope of this reference.1 Fortunately, it’s more often the case that we can compute these values with less brute force. An introduction to these computations is presented here.
Let’s examine the task of counting the number of combinations of $k$ objects that can be selected from a set of $n$ objects. For example, we might be counting the number of 5-card hands that can be dealt from a deck of 52 standard playing cards. Note that typically, we’re assuming that each hand has no effect on subsequent hands—in other words, we’re counting the number of distinct hands that might be obtained when each is drawn from a full (and re-shuffled) deck. Also, we’re intentionally ignoring the order of the cards in the hand itself. So the hand $\lbrace \text{2}\spadesuit, \text{5}\heartsuit, \text{10}\heartsuit, \text{J}\diamondsuit, \text{A}\clubsuit \rbrace$ is not considered distinct from $\lbrace \text{5}\heartsuit, \text{2}\spadesuit, \text{J}\diamondsuit, \text{10}\heartsuit, \text{A}\clubsuit \rbrace$.
The number of distinct combinations (without regard to order) of $k$ objects that can be selected from a set of $n$ objects is denoted as $C\left(n, k\right)$, $C_{k}^{n}$, ${_n}C_k$, or $\dbinom{n}{k}$, and its value is
\[\begin{equation} \begin{aligned} C\left(n, k\right) &= \dfrac{n!}{k! \left( n - k \right)!} \end{aligned} \label{combinations} \end{equation}\]Another way to express $\eqref{combinations}$, useful for some computations, is
\[\begin{aligned} C\left(n, k\right) &= \dfrac{n \cdot \left( n - 1 \right) \cdot \ldots \cdot \left( n - k + 1 \right)}{1 \cdot 2 \cdot \ldots \cdot k} \\ &= \prod_{i=1}^{k}\dfrac{n - i + 1}{i} \end{aligned}\]Or, equivalently:
\[\begin{equation} \begin{aligned} C\left(n, k\right) &= \prod_{i=0}^{k-1}\dfrac{n - i}{i + 1} \end{aligned} \label{combinations-partial-factorial} \end{equation}\]For example, we can implement $\eqref{combinations-partial-factorial}$ to compute the number of distinct 5-card poker hands with the following Java code:
long hands = 1;
for (int i = 0; i < 5; i++) {
hands *= 52 - i;
hands /= i + 1;
}
System.out.println(hands); // 2598960
(See “Factorial” for more information on the $n!$ notation convention, and on computing the factorial in Java.)
If all combinations are equally likely—as is the case by definition after a fair shuffle of a deck of cards (for example)—then the probability of a given outcome is simply the total number of combinations that include that outcome, divided by the total number of combinations. For example, there are 4 “royal flush” poker hands, and a total of 2,598,960 possible 5-card hands; therefore the probability of being dealt a royal flush from a freshly (and fairly) shuffled deck is
\[\begin{aligned} \dfrac{4}{2598960} &\approx 0.00000153907 \end{aligned}\]The number of permutations (arrangements) of $k$ distinct items is denoted by $\alpha(k)$ or $P(k)$, and can be computed with the factorial function:
\[\begin{aligned} \alpha(k) &= k! \end{aligned}\]If the $k$ items are not all distinct, but consist of $m$ groups, where $M = (k_1, k_2, \dots, k_m)$ and $\sum_{i=1}^{m} k_i = k$, then the number of permutations is
\[\begin{aligned} P(k, M) &= \dfrac{k!}{ {k_1}!{k_2}!\ldots{k_m}! }. \end{aligned}\]If the order of $k$ objects selected from is significant, then the number of permutations (distinct orderings) of the $k$ selected objects is $k!$. Therefore, the number of permutations of $k$ objects selected from a set of $n$ objects (denoted as $P\left(n, k\right)$, $P_{k}^{n}$, or ${_n}P_k$) is
\[\begin{aligned} P\left(n, k\right) &= \dfrac{n!}{k! \left( n - k \right)!} \cdot k! \\ &= \dfrac{n!}{\left( n - k \right)!} \end{aligned}\]The definitive reference on combinatoric algorithms is Donald Knuth’s The Art of Computer Programming, Volume 4A. ↩