Here, we're referring to each person by their letter. One possible choice for the group is $ABC$ and another is $ABD$ . However, we must make sure we don't double count, that is, if we've already counted the group $ABC$ , then we should not count the group $BAC$ as another combination. This should make sense because groups $ABC$ and $BAC$ are identical - both groups have the same people in them. In fact, the word "combinations" in mathematics specifically means that the ordering of the elements within a group does not matter.

How should we go about counting all possible combinations without double counting? Our plan of attack is to count all possible permutations first and then remove the double counts.

Recall from our guide on permutations that the total number of ways to select a group of $3$ from $5$ people is:

\begin{matrix} (1) & \frac{5!}{2!} = 5 \times 4 \times 3 = 60 \end{matrix}

The problem is that this number includes double counts. Our goal now is to discard these double counts. The key is to think about how many times we are counting each group. For instance, consider the group $ABC$ - let's list all the permutations of $ABC$ below:



            filter_none
            Copy

        
        
        
            
                
                
                    ABC, ACB, BAC, BCA, CAB, CBA

We can use permutations once again to compute the number of arrangements, that is, $3! = 6$ . Because each group is counted $6$ times and we have $60$ groups (with duplicates), the total number of possible combinations (without duplicates) is:

\begin{matrix} (2) & \frac{5!}{2!} \times \frac{1}{3!} = 60 \times \frac{1}{3!} = 10 \end{matrix}

Let's generalize this technique of counting combinations. Let $n$ be the number of distinct elements (e.g. people) and $r$ be the number of slots to fill. In our example, $n = 5$ and $r = 3$ . The count of ordered elements is computed by permutation as:

\begin{matrix} (3) & \frac{n!}{(n - r)!} \end{matrix}

If we plug in $n = 5$ and $r = 3$ as in our example, we would get $(1)$ .

Next, we remove double counts by dividing $(3)$ by $r!$ , which represents the number of ways to arrange any group:

\begin{matrix} (4) & \frac{n!}{r! (n - r)!} \end{matrix}

Again, if we substitute $n = 5$ and $r = 3$ as in our example, we would get $(2)$ . What we have managed to derive here is the formula for combinations!

■

Definition.

Definition and formula for combinations

Combination refers to the number of ways of selecting $r$ elements from a total of $n$ elements without regard to order:

(\binom{n}{r}) = \frac{n!}{r! (n - r)!}

The left side is read as "n choose r".

Difference between permutations and combinations

The main difference between permutations and combinations is that permutations are concerned with the ordering of the chosen elements whereas combinations are not.

For instance, the number of permutations of selecting two distinct letters from $A$ , $B$ and $C$ is:

_{3} P_{2} = \frac{3!}{(3 - 2)!} = 6

On the other hand, the number of combinations for the same task is:

(\binom{3}{2}) = \frac{3!}{2! \times (3 - 2)!} = 3

The formulas for permutations and combinations look similar, and in fact, combinations can be computed from permutations:

(\binom{3}{2}) =_{3} P_{2} \times \frac{1}{2!} = 3

As we can see, computing combinations involves an additional step of removing double counts by dividing by the number of arrangements of any selection ( $2!$ in this case). This also means that permutations must always be equal to greater than combinations for the same task.

Let's now go through some examples of applying the formula for combinations!

Examples

Example.

Number of combinations drawing balls

Suppose we have $8$ balls in a bag, of which $3$ are red and $5$ are green. How many possible combinations are there for choosing $2$ red and $4$ green balls?

Solution. The number of combinations of choosing $2$ red balls from $3$ red balls is:

\begin{aligned} (\binom{3}{2}) & = \frac{3!}{2! \times (3 - 2)!} \\ = 3 \end{aligned}

Here, the ordering of the red balls does not matter. For instance, if we label the balls as $R_{1}$ , $R_{2}$ and $R_{3}$ , then $R_{1} R_{2}$ is the same as $R_{2} R_{1}$ . This is the reason why we use combinations instead of permutations here.

The number of combinations of choosing $4$ green balls from $5$ green balls is:

\begin{aligned} (\binom{5}{4}) & = \frac{5!}{4! \times (5 - 4)!} \\ = 5 \end{aligned}

The total possible number of combinations is their product, that is, $3 \times 5 = 15$ .

■

Example.

Number of diagonals of a hexagon (optional)

How many diagonals does a hexagon have?

Solution. Each vertex of a hexagon has $3$ diagonals:

Since a hexagon has $6$ vertices, the total number of diagonals is:

6 \times 3 = 18

However, this number is misleading because we are double counting the diagonals. For instance, the diagonals from vertex $E$ are:

Here, the diagonal $AE$ is counted once again. Therefore, even though there are $18$ ordered diagonals, half of them are duplicated. Therefore the total number of unique diagonals is:

\frac{18}{2} = 9

Even though this question does not use the combinations formula, the main idea is the same - we first compute the total number of permutations and then remove duplicates by division.

■

Published by Isshin Inada

Edited by 0 others

Did you find this page useful?

thumb_up

thumb_down

Comment

Citation

Ask a question or leave a feedback...

thumb_up

thumb_down

chat_bubble_outline

settings

Enjoy our search

Hit / to insta-search docs and recipes!