Combinatorics: Counting, Permutations and Combinations: every key term you need (+ practice quiz)
25 flashcard terms for Discrete Mathematics Topic 4, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
If a procedure splits into independent stages with fixed numbers of choices at each stage, the total number of outcomes is the product of those numbers. It underlies almost every other counting formula.
Sum rule of counting
If a task can be done in one of several mutually exclusive ways, the total count is the sum of the counts for each way. The exclusivity condition is what makes double counting impossible.
Complementary counting
Counting the outcomes that fail a condition and subtracting from the total. It is usually easier when a condition contains the phrase at least one.
Permutation
An arrangement of objects in which order matters. The number of ordered arrangements of r objects chosen from n distinct objects is n factorial divided by the factorial of n minus r.
Combination
A selection of objects in which order does not matter, counted by the binomial coefficient n choose r, which equals the permutation count divided by r factorial.
Factorial
The product of all positive integers up to a given integer, with zero factorial defined as one so that formulas for choosing all or none of a collection stay correct.
Binomial coefficient
The number of r element subsets of an n element set, written n choose r. It is symmetric under replacing r by n minus r, since choosing what to keep is choosing what to discard.
Pascal identity
The recurrence stating that a binomial coefficient equals the sum of the two coefficients directly above it, obtained by splitting on whether a fixed element is chosen.
Binomial theorem
The expansion of a sum raised to a power as a sum of terms whose coefficients are binomial coefficients, explained combinatorially by choosing one term from each factor.
Permutation with repetition
Arrangements of a multiset with repeated items, counted by the total factorial divided by the product of the factorials of the repetition counts, which cancels indistinguishable swaps.
Combination with repetition
Selections allowing repeats where order is irrelevant, counted by the stars and bars formula as the binomial coefficient of n plus r minus one choose r.
Stars and bars
A bijection between selections with repetition and arrangements of identical markers separated by dividers, converting the problem into a straightforward subset count.
Pigeonhole principle
If more objects than containers are distributed, some container holds at least two objects. It requires only that the object count strictly exceeds the container count.
Generalised pigeonhole principle
Distributing n objects among k containers forces some container to hold at least the ceiling of n divided by k objects, which sharpens the basic statement when n far exceeds k.
Inclusion exclusion principle
A formula for the size of a union that adds all individual sizes, subtracts all pairwise intersections, adds all triple intersections, and continues with alternating signs.
Derangement
A permutation leaving no element in its original position. The count follows from inclusion exclusion and approaches the total permutation count divided by the constant e.
Bijective proof
A combinatorial argument establishing that two counts are equal by constructing an explicit one to one correspondence between the objects they count, rather than by algebra.
Double counting argument
A technique that counts one collection in two different ways and equates the results, which proves identities such as the sum of degrees in a graph equalling twice the edge count.
Multiplication of independent choices
The observation that when later choices do not change the number of options available, stages multiply. When they do change it, the count must be built stage by stage instead.
Circular permutation
An arrangement around a circle where rotations are considered identical, counted by fixing one object and arranging the remainder, giving n minus one factorial.
Vandermonde identity
The identity expressing a binomial coefficient of a sum as a convolution of binomial coefficients, proved by splitting a committee choice across two disjoint pools.
Combinatorial proof
An argument that establishes an algebraic identity by showing both sides count the same finite collection, which explains why an identity is true rather than merely verifying it.
Ordered versus unordered selection
The first decision in any counting problem: whether two outcomes differing only in arrangement count separately. Permutations say yes and combinations say no.
Multinomial coefficient
The count of ways to split objects into labelled groups of specified sizes, generalising the binomial coefficient to more than two parts.
Counting with restrictions
Problems where some placements are forbidden, usually handled by complementary counting, by inclusion exclusion, or by placing the restricted items first and filling around them.