Counts the total outcomes when a procedure can be performed by one of k mutually exclusive methods. If method i has mi ways to occur and no two methods share any outcome, the total number of ways is m1+m2+⋯+mk.
Equivalently in set-theoretic form: for pairwise disjoint sets, the cardinality of the union is the sum of the cardinalities.
Counts the total outcomes when an outcome is built from a sequence of k independent steps. If step i has mi options, and the steps are independent, the combined sequence has m1⋅m2⋯mk possible outcomes.
In set-theoretic form: the cardinality of a Cartesian product of finite sets is the product of their cardinalities.
Computes the size of a target set by subtracting its complement from the universe. Most useful when the target condition has the form "at least one" — its negation "none" often partitions into a single tractable count, while the direct count requires case analysis over overlapping subcases.
A proof technique rather than a numerical count. The same set S is enumerated by two genuinely different arguments — typically by selecting members directly versus by partitioning the selection into stages or cases. Both expressions equal ∣S∣, so they equal each other. The output is an identity.
The basic form: if n items are distributed among k containers and n>k, at least one container holds at least two items. An existential statement — guarantees a collision must occur without identifying where.
Back to top
Pigeonhole Principle (Generalized)
n items into k containers⟹∃ container with ≥⌈n/k⌉ items.
n items into k containers⟹∃ container with ≥⌈n/k⌉ items.
A strengthening of the basic principle: if n items are distributed among k containers, at least one container must hold at least ⌈n/k⌉ items, where ⌈⋅⌉ is the ceiling function.
Extends the two-set formula with one additional correction. Singles add three times for an element in all three sets; pairwise intersections subtract three times; the triple intersection adds once. The net count of any element is exactly one.
The n-set form. Add singles, subtract pairwise intersections, add triple intersections, and continue with alternating signs through the n-fold intersection. Every non-empty subset of the n sets contributes exactly one term — 2n−1 terms total.
Counts elements that satisfy none of the conditions defined by A1,…,An. Natural for problems phrased as "how many elements avoid all of the following" — derangements, surjective functions, arrangements with forbidden positions, divisibility problems requiring relative primality.
Counts the surjective (onto) functions from a domain of size n to a codomain of size k. Direct enumeration is awkward — the count comes out cleanly by Inclusion-Exclusion on the complementary set "functions that miss at least one codomain element."
The product of all positive integers from 1 to n. Counts the number of distinct orderings of n items — the foundational quantity behind every permutation formula.
The number of distinct linear arrangements of n distinct items, with every item used exactly once. Each item is placed at a single position, and reordering produces a different arrangement.
The number of ordered arrangements of r positions, where each position is filled independently from a pool of n items and items may repeat. This is the only permutation scenario whose count is unbounded as r grows past n.
The number of distinct linear arrangements of n items split into k groups of indistinguishable items of sizes n1,n2,…,nk. The naive n! orderings overcount by a factor of n1!n2!⋯nk! since swapping identical items produces no new arrangement.
The number of distinct arrangements of n distinct items around a circle, where rotations of the same arrangement are considered identical. Fixing the position of one item removes the rotational redundancy.
A two-term linear recurrence for the Derangement count. More efficient than the closed-form for computing !n from prior values, especially for tabulating sequences.
The fraction of permutations of {1,…,n} that are derangements approaches a non-zero constant — namely 1/e — as n grows. For any sufficiently large n, roughly 36.8% of all permutations are derangements.
The number of unordered r-element subsets of an n-element set. Different orderings of the same items count as the same combination — what distinguishes combinations from permutations.
The number of ways to partition n distinct items into k groups of specified sizes n1,n2,…,nk. The formula is the Multinomial Coefficient when group labels are kept distinct.
The number of ways to distribute n identical items into r labeled containers, where any container may receive zero or more items. Equivalently, the number of non-negative integer solutions to x1+x2+⋯+xr=n.
The number of ways to distribute n identical items into r labeled containers, with every container receiving at least one item. Equivalently, the number of positive integer solutions to x1+x2+⋯+xr=n.
The number of ways to assign each of n distinct items to one of r labeled containers. Items are distinct, containers are distinguishable, and any container may receive any number of items (zero allowed).
Equivalently: the number of functions from an n-element domain to an r-element codomain.
The number of k-element subsets of an n-element set. The same expression organizes polynomial expansions, governs probability distributions, and satisfies a network of identities — treating (kn) as a standalone mathematical object reveals structure that the subset interpretation alone does not expose.
The binomial coefficient extended to real or complex upper index. The numerator is a polynomial of degree k in x, so (kx) is itself a polynomial in x. Standard combinatorial interpretation fails when x is not a non-negative integer — the value is purely algebraic.
Choosing which k elements to include in a subset is the same act as choosing which n−k elements to exclude. The two perspectives count the same subsets, so the binomial coefficients agree.
In Pascal's triangle, the identity manifests as left-right symmetry within each row.
A recursive identity expressing each binomial coefficient as the sum of the two directly above it in Pascal's triangle. The rule is what generates the triangle row by row from the boundary values (0n)=(nn)=1.
Also called the committee identity. Both sides count the number of ways to choose a k-element subset of an n-element set and then designate one of its members as distinguished.
The sum of the entries in row n of Pascal's triangle equals 2n — the size of the power set of an n-element set. Each subset is counted exactly once by the row sum, grouped by size.
The alternating sum of row n of Pascal's triangle is zero for n≥1. Equivalently, the number of even-sized subsets of an n-set equals the number of odd-sized subsets.
Expresses a single binomial coefficient as a convolution sum of smaller ones. The identity says choosing r items from m+n items partitions according to how many come from each of two disjoint groups of sizes m and n.
A sum along a diagonal of Pascal's triangle collapses to a single entry one row below. The visual pattern of the summed entries plus the result forms a "hockey-stick" shape — the diagonal handle plus the off-diagonal tip.
The sum of squared entries in row n of Pascal's triangle equals the central binomial coefficient (n2n). A special case of Vandermonde's Identity with m=n and r=n.
Counts the number of ways to partition n distinct items into r labeled groups of specified sizes k1,k2,…,kr. Equivalently, the number of distinct arrangements of n items where ki are of type i. Generalizes the Binomial Coefficient from r=2 groups to arbitrary r.
Expands the n-th power of a binomial. The coefficients are precisely the entries of row n of Pascal's triangle. The expansion has n+1 terms, indexed by k from 0 through n.
The (k+1)-th term of the binomial expansion of (a+b)n. The tool for problems asking about one specific term — a particular power of one variable, the term independent of a variable — without expanding the entire polynomial.
When n is even, the expansion of (a+b)n has a unique middle term — the (n/2+1)-th term. Its coefficient (n/2n) is the maximum value in row n of Pascal's triangle: binomial coefficients grow from the edges of each row toward the middle.
This maximum coefficient is called the central binomial coefficient.
A weighted analogue of the Binomial Row Sum. Combinatorially, k(kn) counts (k-subset,distinguished member) pairs of size k — summing over k counts all (subset, distinguished member) pairs of any size.
Extends the Binomial Theorem from non-negative integer exponents n to arbitrary real (or complex) exponents α. The expansion becomes an infinite series, converging for ∣x∣<1.
When α=n is a non-negative integer, the Generalized Binomial Coefficient(kn) equals 0 for k>n, so the series terminates and recovers the ordinary binomial theorem.