Lesson 6: Basic Counting Principles

The Sum Rule

When a task can be done by one of two mutually exclusive methods (you do method A or method B, but not both), the total number of ways equals n₁ + n₂.

More generally: |A₁ ∪ A₂ ∪ ... ∪ Aₖ| when the sets are disjoint.

The Product Rule

When a procedure consists of sequential steps — first do task A, then do task B — the total number of ways is n₁ × n₂.

More generally: n₁ × n₂ × n₃ × ... × nₖ for k sequential, independent tasks.

Permutations

A permutation is an ordered arrangement of r items selected from n distinct items.

Formula: P(n, r) = n! / (n − r)!

Example: How many ways can 3 books be arranged on a shelf from a collection of 8? P(8, 3) = 8! / 5! = 8 × 7 × 6 = 336

Permutations with Repetition: If repetition is allowed, the count for r selections from n items = nʳ.

Combinations

A combination is a selection of r items from n distinct items where order does not matter.

Formula: C(n, r) = n! / (r! × (n − r)!)

Example: How many ways can 3 students be chosen from a group of 10 for a committee? C(10, 3) = 10! / (3! × 7!) = 120

Combinations with Repetition: When repetition is allowed: C(n + r − 1, r) = (n + r − 1)! / (r! × (n − 1)!)

Example: How many ways can you choose 4 items from 5 categories (repetition allowed)? C(5 + 4 − 1, 4) = C(8, 4) = 70