Home / Courses / Discrete Mathematics / Unit 4

Discrete Mathematics Unit 4: Counting

Counting answers "how many ways?" without listing them. Decide whether order matters and whether repetition is allowed.

Covers: Sum & product rules, permutations, combinations, pigeonhole principle, inclusion-exclusion

Study guide

Counting problems ask how many ways something can happen. The sum rule says that if a task can be done in one of m ways or one of n other ways (with no overlap), there are m + n options. The product rule says that if a procedure has a step with m ways followed by a step with n ways, there are m·n total. Most counting problems combine these.

A permutation is an ordered arrangement. The number of ways to arrange r of n distinct items is P(n, r) = n!/(n − r)!, and all n items can be arranged n! ways. Arrangements of letters with repeats divide by the factorials of the repeat counts.

A combination is an unordered selection: C(n, r) = n!/(r!(n − r)!). Ask whether order matters; if swapping two chosen items gives the same outcome, use combinations. With repetition allowed and order not mattering, stars and bars gives C(n + r − 1, r).

The pigeonhole principle says that if n + 1 objects go into n boxes, some box holds at least two. The generalized version says some box holds at least ⌈N/k⌉. It proves existence without finding the specific example.

Inclusion–exclusion counts unions with overlap: |A ∪ B| = |A| + |B| − |A ∩ B|, and for three sets add back the triple intersection. Complementary counting (total minus the unwanted cases) is often easier for "at least one" problems.

The number of functions from an m-element set to an n-element set is nᵐ. The number of injections is P(n, m) = n!/(n − m)! (zero if m > n), and the number of bijections between two n-element sets is n!. The division rule says that if each outcome is counted exactly k times, divide the total by k. For example, dealing 52 cards into 13-card hands for four players, where order within a hand doesn't matter, can be counted as 52! arrangements divided by (13!)⁴.

Key ideas

• Product rule: tasks in sequence multiply.
• Sum rule: disjoint choices add.
• Permutations count arrangements where order matters.
• Combinations count selections where order doesn't matter.
• Pigeonhole principle: n + 1 objects in n boxes means some box has two.
• Inclusion–exclusion corrects for double-counting.

Formulas and rules

Common mistakes

• Using permutations when order doesn't matter.
• Double-counting overlapping cases.

Words to know

Permutations P(n, r)

n!/(n − r)!

Combinations C(n, r)

n!/(r!(n − r)!)

Pigeonhole principle

Putting n + 1 objects into n boxes forces some box to hold at least 2.

Order matters vs. doesn't

Order matters: permutations. Order doesn't: combinations.

Stars and bars: choosing r items from n types with repetition

C(n + r − 1, r)

Sum rule

m or n ways (no overlap) gives m + n.

Product rule

m ways then n ways gives m·n.

Permutations with repeated letters

n!/(n₁!n₂!…)

Generalized pigeonhole principle

N objects in k boxes force a box with at least ⌈N/k⌉.

Inclusion–exclusion

|A ∪ B| = |A| + |B| − |A ∩ B|

Complementary counting

Total minus the unwanted cases.

Sample practice questions

29 more questions like these, from level 1 to 5, are in the practice set.