Combinations
Lesson · Beginner
Combinatorics
A combination is a selection of objects in which order does not matter.
For example, choosing
is the same selection as
Therefore, when selecting objects from distinct objects, we use
read as “n choose r”.
The number of ways to choose objects from distinct objects is
For example,
The key idea is:
First select and arrange objects from distinct objects.
There are
ways.
However, each group of selected objects has been counted
times, once for each possible ordering.
Therefore,
and hence
Choosing objects to include is equivalent to choosing the objects to exclude.
For example, choosing 3 students from 10 is equivalent to deciding which 7 students are not chosen.
Therefore,
Choose one particular object .
Every selection of objects belongs to exactly one of two cases.
If is not selected, choose all objects from the remaining :
If is selected, choose the remaining objects from the other :
Adding the two cases gives
A committee of 5 people is selected from 8 men and 7 women.
How many committees contain exactly 3 women?
Choose 3 of the 7 women:
Then choose 2 of the 8 men:
Therefore,
How many 5-element subsets of
contain both 1 and 2?
The elements 1 and 2 are already selected.
We need to choose the remaining 3 elements from the other 10.
Therefore,
A committee of 6 people is selected from 10 men and 8 women.
How many committees contain at least 2 women?
It is easier to use the complement.
There are
total committees.
The undesired committees contain either no women or exactly one woman.
No women:
Exactly one woman:
Therefore, the desired number is
Thus,
How many 6-element subsets of
contain exactly 3 elements less than 10?
The numbers less than 10 are
so there are 9 of them.
Choose exactly 3:
The remaining elements must come from
which contains 11 elements.
Choose 3 of them:
Therefore,
There is exactly one way to choose no objects:
There is exactly one way to choose all objects:
Choosing objects is equivalent to choosing the one object that is excluded.
Therefore,
When evaluating
first use
to make the lower number as small as possible.
Then multiply only the necessary consecutive factors.
For example,
and instead of calculating with full factorials,
Therefore,
In general, if is small,
This is usually much faster than calculating , , and separately.