Mathematics from zero
Combinations
You invite 2 friends from a group of 4 to dinner. Inviting Ann and Ben is the very same dinner as inviting Ben and Ann — the order you named them in changes nothing. When order stops mattering, you are counting combinations.
After this lesson you can say what a combination is, see how it differs from a permutation, and count combinations by dividing permutations by the orderings you no longer want to count separately.
A combination is a selection where order does not matter. A permutation cared
about position — gold, silver, bronze were all different. A combination only cares
who is chosen, not in what order. The group A, B and the group B, A are the same
combination, because they hold the same people.
Combinations are fewer than permutations of the same choice. Picking 2 of 4 people
as an ordered list — a permutation — gives 4 × 3 = 12 results. But A then B and
B then A are the same dinner. The 12 ordered lists collapse into fewer unordered
groups. A combination count is always smaller than the matching permutation count.
Count a combination by dividing the permutations by the orderings of the chosen
group. Choosing 2 of 4: there are 4 × 3 = 12 ordered picks. Each unordered pair was
counted once for every way to order 2 people — and 2 people can be ordered in 2! = 2
ways. So divide: 12 ÷ 2 = 6 combinations.
The rule: permutations divided by the factorial of the group size. To choose r
items from n when order does not matter, first count the ordered picks (the first
r shrinking factors of n), then divide by r! — the number of orderings of the
r chosen items. Dividing removes exactly the orderings you decided not to
distinguish.
In how many ways can you choose 3 people from a group of 5, when order does not matter?
First count the ordered picks — a permutation of 3 from 5. Three positions, three
shrinking factors: 5 × 4 × 3 = 60.
But order should not matter. Each chosen group of 3 was counted once for every ordering
of those 3 people, and 3 people can be ordered in 3! = 6 ways.
Divide out those orderings: 60 ÷ 6 = 10. There are 10 combinations. Check the
shape: 10 is much smaller than the 60 ordered picks — exactly because each group was
counted 6 times.
Why this works
Why divide by r! and not some other number? Because r! is exactly how many times
each unordered group got counted. The permutation count lists every ordering of every
group; one fixed group of r people appears in all r! of its orderings. Dividing by
r! merges those duplicates back into the single group they always were.
Common mistake
A common mistake is using the permutation count when order does not matter — saying 2
of 4 people can be chosen “12 ways”. That counts A, B and B, A as different, but
for a dinner they are the same. Whenever the order of the chosen items is irrelevant,
divide the permutation count by r!.
Choose 2 people from 4, order not mattering. Type the number of combinations.
Choose 1 person from 7, order not mattering. Type the number of combinations.
Choose 3 people from 5, order not mattering. Type the number of combinations.
Choosing 2 of 5 gives 20 ordered picks. Divide by 2 to get the combinations. Type the result.
Choose 4 people from a group of 4, order not mattering. Type the number of combinations.
Why is the number of combinations smaller than the number of permutations for the same choice?
A combination is a selection where order does not matter — the group A, B is the same
as B, A. Combinations are fewer than the matching permutations, because permutations
count each group once per ordering. To count combinations, take the permutation count
and divide by r!, the factorial of the group size — that division merges the
duplicate orderings back into single groups.