Combinatorial counting establishes formal rules for determining the cardinality of a set of objects, often by constructing a mapping (function) to a structurally different but more easily counted set: the mapping rule relates cardinalities of domain and range according to whether a function is surjective, injective, or bijective, with the bijection rule stating that a bijection implies equal cardinalities between two sets. The generalized pigeonhole principle states that if the cardinality of a domain set exceeds k times the cardinality of a range set, then every function between them must map at least k+1 distinct domain elements to some common range element, enabling non-constructive existence proofs. Related counting mechanisms — the division rule (for k-to-one mappings), the generalized product rule (for counting sequences via successive independent choices), and the sum rule (for counting unions of disjoint sets) — together form the foundational toolkit of combinatorics, a branch of discrete mathematics that underlies probability theory.
Combinatorial counting establishes formal rules for determining the cardinality of a set of objects, often by constructing a mapping (function) to a structurally different but more easily counted set…