6.2c Combinations

Combination

A combination is an unordered list of elements from a set where the elements in the set are not replaced. Formally, the total number of combinations of $k\le n$ elements that can be made from a set of $n$ elements is expressed as
$N=\frac{n!}{k!(n-k)!}=\left(\genfrac{}{}{0ex}{}{n}{k}\right),$
thereby not only “cutting off” the $n-k$ unused arrangements, but accounting for the $k!$ ways of permuting every sequence of selected elements, since order does not matter here. This is a direct consequence of the division principle.

Combination counting is used to count the number of ways to choose a subset of items without regard to order (and without repetition), for instance, selecting three students from a class of ten.

Intuition

We know from the previous note that given a “constrained” sequence size $k\le n$, and a set of $n$ elements, there are $\frac{n!}{(n-k)!}$ ways to construct the sequence without repeating elements, where order does matter.

However, in combinations, the order does not matter. This means that sequences like $(1,2,3)$ and $(3,2,1)$, though different as permutations, represent the same group when order is irrelevant.

As such, we must account for all permutations that represent the same combination. Since each group of $k$ distinct elements can be permuted (i.e., rearranged) in $k\cdot (k-1)\cdot \dots \cdot 2\cdot 1=k!$ different ways, we divide by $k!$ to eliminate overcounting directly from the division principle and obtain $\frac{n!}{k!(n-k)!}$.

Examples

Dice Throws

We are playing Threes Away, and throw the 3 dice one by one.

How many throws are in strictly increasing order? $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20.$

Since each dice has 6 faces, and we are choosing 3 distinct elements, the total number of throws in strictly increasing order is

How many throws are in strictly decreasing order? $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$.

By symmetry, the answer is also

How many throws are not in strict order? $6^3=216$. Since this is a complement of the subset of sequences which are in strict order, the answer is $216-(20+20)=176.$

First note that the total number of outcomes is

How many throws have two of the same value? $6\cdot 5\cdot \left(\genfrac{}{}{0ex}{}{3}{2}\right)=90.$ To think about why, consider 4 to be the repeating value, and 2 as the singleton value:

Since we are counting two of the same value, we have one free choice which can take on all 6 values, and one face which can take on the other 5 values. Since 2 of the 3 values are equal, our answer is

• If you choose positions 1 and 2 to be the 4’s, the outcome is $(4,4,2)$.
• If you choose positions 1 and 3, it’s $(4,2,4)$.
• If you choose positions 2 and 3, it’s $(2,4,4)$.

Since there are 3 different ways to pick a pair of positions out of 3, that’s $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$. In other words, “3 choose 2” just counts the number of ways to place the two identical dice among the three spots.

As a side note, you might be tempted to answer $6\cdot 1\cdot 5=30$. However, this only accounts for one of the 3 cases we outlined above.

Grids