Sets and counting

Why this matters

"How many?" questions sit underneath probability, security and computing. How many passwords of a given length exist? How many ways can a five-person team be picked from twelve people? How many test cases cover every combination of settings? Counting techniques answer these without listing every case, which is often impossible.

Sets

A set is a collection of distinct items, written in braces: A = {1, 2, 3, 4}. Order does not matter and duplicates are ignored.

• Union A ∪ B: items in A or B (or both).
• Intersection A ∩ B: items in both.
• Difference A − B: items in A but not B.

With A = {1, 2, 3, 4} and B = {3, 4, 5}: A ∪ B = {1, 2, 3, 4, 5}, A ∩ B = {3, 4}, A − B = {1, 2}.

The inclusion-exclusion rule counts a union without double counting:

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

If 30 students take Python, 20 take SQL and 8 take both, then 30 + 20 − 8 = 42 take at least one.

Python has sets built in:

a = {1, 2, 3, 4}
b = {3, 4, 5}
print(a | b, a & b, a - b)   # {1, 2, 3, 4, 5} {3, 4} {1, 2}

The multiplication principle

If one choice has m options and a second, independent choice has n options, together there are m × n outcomes.

• A meal deal with 4 mains and 3 drinks: 4 × 3 = 12 combinations.
• A 4-digit PIN: 10 × 10 × 10 × 10 = 10⁴ = 10,000 PINs.
• An 8-character password from 62 letters and digits: 62⁸ ≈ 2.18 × 10¹⁴. Each extra character multiplies the count by 62, which is why length matters so much for security.

Factorials

The number of ways to arrange n different items in a line is

n! = n × (n − 1) × ... × 2 × 1

Five books on a shelf: 5! = 120 orders. By definition 0! = 1. Factorials grow very fast: 10! = 3,628,800.

Permutations: order matters

Choosing k items from n where order matters (first, second, third place):

P(n, k) = n! / (n − k)!

Gold, silver and bronze among 8 runners: P(8, 3) = 8 × 7 × 6 = 336.

Combinations: order does not matter

Choosing k items from n where order does not matter (a team, a hand of cards):

C(n, k) = n! / (k! × (n − k)!)

This is the permutation count divided by k!, because each group of k can be arranged in k! orders that we now treat as the same.

A 3-person committee from 8 people: C(8, 3) = 336 / 3! = 336 / 6 = 56.

C(n, k) is also written "n choose k".

Worked example: which formula?

Ask: does swapping two chosen items give a different outcome?

• Picking a president and a treasurer from 10 club members: Ada as president and Ben as treasurer is different from the reverse. Order matters: P(10, 2) = 90.
• Picking 2 members to attend a conference: {Ada, Ben} is the same as {Ben, Ada}. Order does not matter: C(10, 2) = 45.

Worked example: lottery odds

A lottery draws 6 numbers from 49, order irrelevant. C(49, 6) = 13,983,816, so one ticket has about a 1 in 14 million chance.

In code

import math

print(math.factorial(5))   # 120
print(math.perm(8, 3))     # 336
print(math.comb(8, 3))     # 56
print(math.comb(49, 6))    # 13983816

The itertools module can list the actual arrangements (itertools.permutations, itertools.combinations) when n is small enough to print.

Common mistakes

• Using permutations when order does not matter, overcounting by a factor of k!.
• Adding instead of multiplying for independent choices.
• Double counting in a union; subtract the overlap.
• Forgetting that 0! = 1, which makes C(n, 0) = C(n, n) = 1.

Quick recap

• Sets: union, intersection, difference; |A ∪ B| = |A| + |B| − |A ∩ B|.
• Independent choices multiply.
• Arrangements of n items: n!.
• Order matters: P(n, k) = n! / (n − k)!. Order does not: C(n, k) = n! / (k!(n − k)!).

Try it

In the Do tab, write the combinations formula using math.factorial. A permutations function is already written for comparison.