Sets, Functions and Counting Functions

Sets

A set is an unordered collection of distinct elements. Key notation: x ∈ A (membership), A ⊆ B (subset), ∅ (empty set), |A| (cardinality).

The set identities mirror Boolean algebra (De Morgan: complement of A ∪ B = Ā ∩ B̄). For counting, the inclusion–exclusion principle gives |A ∪ B| = |A| + |B| − |A ∩ B| and |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Functions

A function f : A → B assigns to every element of the domain A exactly one element of the codomain B. The set of values actually taken is the range (image).

A function has an inverse f⁻¹ exactly when it is a bijection. The composition (g ∘ f)(x) = g(f(x)) is injective (or surjective, or bijective) when both f and g are.

Counting functions

With |A| = m and |B| = n:

The onto formula subtracts the functions that miss at least one element of B: start with nᵐ, subtract the C(n, 1)(n − 1)ᵐ functions missing a given element, add back those missing two, and so on. A brute-force check over all functions:

from itertools import product
from math import comb

def count_functions(m, n):
    functions = list(product(range(n), repeat=m))          # f = (f(a1), ..., f(am))
    injective = sum(len(set(f)) == m for f in functions)
    surjective = sum(len(set(f)) == n for f in functions)
    return len(functions), injective, surjective

def onto_formula(m, n):
    return sum((-1) ** k * comb(n, k) * (n - k) ** m for k in range(n + 1))

for m, n in [(4, 3), (3, 4), (5, 3)]:
    total, inj, sur = count_functions(m, n)
    print(f"|A| = {m}, |B| = {n}: all {total}, one-to-one {inj}, onto {sur} (formula {onto_formula(m, n)})")

|A| = 4, |B| = 3: all 81, one-to-one 0, onto 36 (formula 36)
|A| = 3, |B| = 4: all 64, one-to-one 24, onto 0 (formula 0)
|A| = 5, |B| = 3: all 243, one-to-one 0, onto 150 (formula 150)

The pigeonhole principle

If n + 1 objects are placed into n boxes, some box gets at least two. More generally, if N objects go into k boxes, some box gets at least ⌈N / k⌉ objects.

Examples:

• Among any 13 people, two share a birth month.
• To be sure of 3 cards of the same suit from a deck, draw 2 × 4 + 1 = 9 cards (with 8 cards you could have exactly 2 of each suit).
• Among any 5 integers from 1 to 8, two of them sum to 9: the 4 pairs {1, 8}, {2, 7}, {3, 6}, {4, 5} are the boxes.

Practice questions