Combinatorial principles

Combinatorial principles are rules for counting discrete possibilities without listing them individually. They include the sum rule, product rule, and pigeonhole principle.

Connect

Sum rule: A counting rule that adds the sizes of mutually exclusive alternatives. It counts choices divided into non-overlapping cases.
Permutations: Ordered arrangements of objects selected from a set. The product rule counts the successive positions in an arrangement.
Double counting: A proof method that counts the same finite set in two different ways. It equates two expressions for one count to establish identities.
Probability theory: The mathematical study of uncertainty and random events. Counting supplies probabilities in equally likely finite sample spaces, but is not itself probability.
Product rule: A counting rule that multiplies the numbers of choices made in successive stages. It counts arrangements built through a sequence of decisions.
Combinations: Selections of objects in which order does not matter. They count unordered choices by correcting for repeated orderings.
Mathematical induction: A proof method that establishes a base case and then proves each case implies the next. It proves counting formulas across all allowed sizes.
Set theory: The mathematical study of sets and their relations. Counting principles address finite collections, while set theory also studies infinite sizes.
Pigeonhole principle: A principle stating that placing more objects than containers forces at least one container to hold multiple objects. It guarantees collisions when objects are assigned to too few categories.
Binomial theorem: A formula expressing powers of a binomial as sums of terms with binomial coefficients. Its coefficients count how many ways each term arises in a product.