Counting principles

Builds on

Required prerequisites, all the way down: 5

You will learn to

• Apply the addition and multiplication principles to count outcomes.
• Count arrangements of n objects (n!) and ordered selections of k objects from n.
• Use complementary counting, for example to count passwords containing at least one digit.

Definition

• n! = n × (n − 1) × ⋯ × 1 for n ≥ 1, and 0! = 1.
• A permutation is an ordered arrangement of objects.

Theorem

• Addition principle: if A and B are disjoint finite sets, |A ∪ B| = |A| + |B|.
• Multiplication principle: |A × B| = |A| · |B|.
• The number of ordered selections of k objects from n distinct objects is n!/(n − k)!.

Common misconceptions

• Adding where the multiplication principle applies, or multiplying where the addition principle applies.
• Counting overlapping cases twice.

Leads to

Optional discoveries

• Probability Counting equally likely outcomes gives probabilities.