13. Combinations and the Pigeonhole Principle

Starting point: what you already know

The multiplication principle: "and" means multiply.
$n! = n (n - 1) \dots 1$ and $^{n} P_{r} = \frac{n !}{( n - r )!}$ counts arrangements where order matters (previous chapter).

From permutations to combinations

Count teams of 3 chosen from A, B, C, D.

Ordered: $^{4} P_{3} = 24$ . But each team, such as ${A, B, C}$ , appears $3! = 6$ times in different orders (ABC, ACB, BAC, ...). So the number of teams is $\frac{24}{6} = 4$ .

Useful facts

$(0 n) = (n n) = 1$ : there is one way to choose nothing, and one way to choose everything.
$(1 n) = n$ .
$(r n) = (n - r n)$ : choosing who is in is the same as choosing who is out.

Committees with restrictions

Combinations

Meaning

Order does not matter
nCr = n!/(r!(n - r)!)

Facts

nC0 = nCn = 1
nCr = nC(n - r)

Restrictions

Split into groups, multiply
At least one: total minus none
Must include: put them in first

Pigeonhole

n + 1 items in n boxes
Some box has two

Quick summary

Combinations count selections where order does not matter: $(r n) = \frac{n !}{r ! ( n - r )!}$ .
$(r n) = (n - r n)$ , and $(0 n) = (n n) = 1$ .
Split restricted choices into groups and multiply. For "at least one", use total minus none.
Pigeonhole: $n + 1$ items in $n$ boxes means some box holds two.

Quiz

13 questions with instant marking. It is free, and your scores are saved to your account so you can carry on from any device.

Turn on JavaScript to sign in and take the quiz.