# Combinations

Combinations are a method of selecting subsets (in which order does not matter) from a larger set .

For example, you might be asked how many possible groups of three can be made from a set of five individuals. If you list out all possible groups, regardless of order, you will realize that groups are all the same group of three people.

The trick here is to do the permutation problem first, then divide out by the number of different orders for each group. In this case:

${}_{5}{P}_{3}=5\text{\hspace{0.17em}}×\text{\hspace{0.17em}}4\text{\hspace{0.17em}}×\text{\hspace{0.17em}}3=60$

But this includes all the “duplicates” of each group of $3$ . Each group of $3$ can be arranged in $3!$ ways, so we need to divide the $60$ permutations by $3$ ! (or $6$ ) in order to get the number of groups where order does not matter.

$\begin{array}{l}{}_{5}{C}_{3}=\frac{5\text{\hspace{0.17em}}×\text{\hspace{0.17em}}4\text{\hspace{0.17em}}×\text{\hspace{0.17em}}3}{3!}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}=\frac{60}{6}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}=10\end{array}$

In general, if you want to find the number of groups of $m$ individuals that can be selected from a set of $n$ , first find ${}_{n}{P}_{m}$ and then divide by $m!$ .

${}_{n}{C}_{m}=\frac{n!}{\left(n-m\right)!}÷m!$

Moving the $m!$ to the denominator, we get:

${}_{n}{C}_{m}=\frac{n!}{m!\left(n-m\right)!}$

Example:

A quality inspector samples $4$ cell phones out of a batch of $100$ .  How many different possible samples could she select?

$\begin{array}{l}{}_{100}{C}_{4}=\frac{100!}{4!\left(100-4\right)!}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}=\frac{100!}{4!\left(96!\right)}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}=3,921,225\end{array}$