Functions and Combinatorics

Functions in mathematics are a generalisation of functions in code. Combinatorics — the mathematics of counting — underpins probability, algorithm analysis, and cryptography.

Mathematical Functions

A function f: A → B assigns each element of A (the domain) exactly one element of B (the codomain). The set of actual output values is the range (or image).

f: ℤ → ℤ
f(x) = x²

f(3) = 9
f(-3) = 9   — same output, different inputs

In code, every function is a mathematical function from its input types to its output type. Pure functions (no side effects) are exactly the mathematical definition.

Injection, Surjection, Bijection

These three properties describe how a function maps inputs to outputs.

Injection (One-to-One)

Every element of the domain maps to a distinct element of the codomain. No two inputs share an output.

f(x) = 2x   is injective: different x → different 2x
f(x) = x²   is NOT injective: f(3) = f(-3) = 9

In software: an injective hash function would mean no collisions. Perfect hash functions are injective.

Surjection (Onto)

Every element of the codomain is hit by at least one input. The range equals the codomain.

f: {1,2,3} → {a,b}
f(1) = a, f(2) = b, f(3) = a   — surjective (both a and b are hit)

In software: a random number generator is surjective if it can produce every value in its range.

Bijection (One-to-One and Onto)

Both injective and surjective. Every input maps to a unique output, and every output is hit.

A bijection has an inverse function f⁻¹ that undoes f.

f: ℤ → ℤ, f(x) = x + 1
f⁻¹(x) = x - 1

Bijections appear in: encryption (a cipher must be bijective to be reversible), base conversion, and any lossless encoding.

Cardinality insight: if there exists a bijection between sets A and B, then |A| = |B|. This extends to infinite sets — the integers and rational numbers have the same cardinality (both countably infinite), but the reals are uncountably infinite. Cantor's diagonal argument proved this.

Counting: The Basics

Multiplication Principle

If you can do task A in m ways and task B in n ways independently, you can do both in m × n ways.

How many 3-character passwords using letters a-z? 26 × 26 × 26 = 26³ = 17,576

How many license plates with 3 letters then 3 digits? 26³ × 10³ = 17,576,000

Addition Principle

If task A can be done in m ways and task B in n ways, and they are mutually exclusive, the total is m + n ways.

How many strings of length 1 or 2 from {a, b, c}? 3 (length 1) + 9 (length 2) = 12

Permutations

A permutation is an ordered arrangement of items. Order matters.

P(n, k) = number of ways to arrange k items chosen from n distinct items:

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

How many ways to arrange 3 books chosen from 5? P(5, 3) = 5! / 2! = 120 / 2 = 60

All arrangements of n items: P(n, n) = n!

import math
math.perm(5, 3)   # 60
math.factorial(5)  # 120

Permutations appear in: generating all orderings, password strength analysis, ranking problems.

Combinations

A combination is an unordered selection of items. Order does not matter.

C(n, k) = "n choose k" = number of ways to choose k items from n:

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

How many ways to choose 3 books from 5 (order doesn't matter)? C(5, 3) = 5! / (3! × 2!) = 120 / 12 = 10

math.comb(5, 3)   # 10

Pascal's Triangle: C(n, k) = C(n-1, k-1) + C(n-1, k) — each entry is the sum of the two above it. This is the recurrence that makes combinations computable with DP.

Binomial theorem: (a + b)ⁿ = Σ C(n,k) aᵏ bⁿ⁻ᵏ — the coefficients are binomial coefficients C(n,k).

The Pigeonhole Principle

If n+1 items are placed into n containers, at least one container holds ≥ 2 items.

Simple but powerful. Applications:

Hash collisions are inevitable: a hash function mapping m values into n buckets where m > n must produce collisions. This is why hash collision resistance matters in cryptography.

Birthday problem: how many people do you need in a room before two share a birthday? With 367 people (> 366 days), it is guaranteed. In practice, 23 people give >50% probability — counterintuitive but mathematically certain.

Duplicate in a stream: if you see more than n distinct values in a stream of size n+1 drawn from a set of size n, at least one value is repeated. This gives the basis for streaming duplicate detection algorithms.

# Finding a duplicate in [1..n] using pigeonhole insight
def find_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return n
        seen.add(n)

Combinations in Algorithm Analysis

Combinations appear directly in:

• Subset generation: there are C(n,k) subsets of size k from n elements.
• Graph edges: a complete graph on n vertices has C(n,2) = n(n-1)/2 edges.
• Binomial heap / Pascal's triangle DP: many DP problems count paths or selections using combinations.

# Number of paths from top-left to bottom-right of an m×n grid
# (only moving right or down)
# = C(m+n-2, m-1)
import math
def grid_paths(m, n):
    return math.comb(m + n - 2, m - 1)

grid_paths(3, 3)   # 6

Key Takeaways

• Injective functions have no two inputs sharing an output — no collisions. Surjective functions cover the entire codomain. Bijections are invertible.
• Multiplication principle: m × n ways for independent sequential choices.
• Permutations P(n,k) = n!/(n-k)!: ordered arrangements. Combinations C(n,k) = n!/(k!(n-k)!): unordered selections.
• C(n,k) = C(n-1,k-1) + C(n-1,k) — computable with dynamic programming.
• Pigeonhole principle: n+1 items in n bins means at least one bin has ≥ 2 — proves hash collisions are inevitable and birthday attacks are possible.