Functions and Counting
A function maps each element of a domain to exactly one element of a codomain. Counting (combinatorics) determines the number of ways events can occur. Both are fundamental to algorithm analysis and discrete mathematics.
Functions
A function f: A → B assigns to each a ∈ A a unique f(a) ∈ B. Injective (one-to-one): different inputs give different outputs. Surjective (onto): every element of B is mapped to. Bijective: both injective and surjective (invertible). The composition (g ∘ f)(x) = g(f(x)).
Special Functions
The floor function ⌊x⌋ gives the greatest integer ≤ x. The ceiling function ⌈x⌉ gives the smallest integer ≥ x. The modulo function gives the remainder. Logarithmic, exponential, and polynomial functions are important in algorithm complexity analysis.
Counting Principles
The sum rule: if tasks are mutually exclusive, total ways = sum of individual ways. The product rule: if tasks are sequential and independent, total ways = product of individual ways. These form the basis of all counting techniques.
Permutations
A permutation is an ordered arrangement. The number of permutations of n objects taken r at a time: P(n, r) = n!/(n−r)!. Permutations with repetition: n^r. Permutations of n objects with identical items: n!/(n₁! · n₂! · ... · nₖ!).
Combinations
A combination is an unordered selection. C(n, r) = n!/(r!(n−r)!). Combinations with repetition: C(n+r−1, r). The binomial theorem: (a+b)^n = Σ C(n,k) · a^(n−k) · b^k. Pascal's triangle gives binomial coefficients.
Pigeonhole Principle
If n items are placed into m containers where n > m, at least one container has more than one item. The generalised pigeonhole principle: at least one container has ⌈n/m⌉ items. Applications include proving existence results in combinatorics and computer science.
Inclusion-Exclusion
The inclusion-exclusion principle counts elements in a union: |A ∪ B| = |A| + |B| − |A ∩ B|. For three sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. It generalises to n sets and is used in probability and counting.
Summary
Functions and counting techniques are essential mathematical tools. Permutations, combinations, the pigeonhole principle, and inclusion-exclusion are used throughout algorithm analysis, probability, and cryptography.