62 articles
Inclusion–exclusion principle
The inclusion–exclusion principle, or sieve principle, is a combinatorial counting formula giving the size of a union of finite sets via an alternating sum of intersections.
Labelled enumeration theorem
The labeled enumeration theorem, also called the fundamental theorem of combinatorial enumeration, translates constructions on labeled combinatorial structures into equations on their exponential generating functions, the labeled counterpart of Pólya's theorem.
Lexicographic order
Lexicographic order, also called lexical or dictionary order, is a way of ordering sequences by comparing them position by position, deciding at the first position where they differ.
Ordinary generating function
An ordinary generating function (OGF) encodes a sequence as a power series whose coefficients are the sequence's terms, distinguishing it from weighted variants such as exponential generating functions.
Partial word
A partial word is a finite or infinite sequence over a finite alphabet in which some positions, called holes, are undefined; it extends ordinary words in combinatorics on words.
Pentomino
Pentomino: a polyomino of five edge-connected squares; 12 free, 18 one-sided, 63 fixed forms named F–Z by Solomon Golomb (1953). The 12 pieces tile 6×10 rectangles in 2,339 ways and inspired games like Blokus and Tetris.
Permutation
A permutation is a rearrangement of the elements of a set, or a one-to-one mapping of a set onto itself; there are n! of n elements.
Pigeonhole principle
The pigeonhole principle, also called the Dirichlet box principle, states that more than n objects placed in n boxes force one box to hold two or more.
Plactic monoid
The plactic monoid, or tableau algebra, is the monoid of semistandard Young tableaux with multiplication by insertion; two words are equal exactly when Schensted's algorithm gives the same tableau.
Pólya enumeration theorem
The Pólya enumeration theorem, or Pólya enumeration formula, is a combinatorics result counting distinct colorings and configurations up to a symmetry group, generalizing Burnside's lemma through weighted generating functions.
Prefix code
A prefix code, also called a prefix-free or instantaneous code, is a variable-length code in which no codeword is a prefix of another, allowing unambiguous decoding without separators.
Q-analog
A q-analog, also called a q-analog or q-deformation, is a mathematical expression or identity parameterized by q that reduces to a known classical object when q is set to 1.
Q-Pochhammer symbol
The q-Pochhammer symbol (a;q)n, also called the q-shifted factorial, is the q-analog of the Pochhammer symbol, a finite product that becomes an infinite product building block of q-series and partition generating functions.
Random permutation statistics
Random permutation statistics studies quantities computed from a uniformly random permutation, such as cycles, descents, and inversions, including their distributions and limiting behavior as n grows.
Recurrence relation
A recurrence relation, also called a recurrence equation, defines each term of a sequence as a function of earlier ones; with initial values, like the Fibonacci recurrence, it determines the sequence uniquely.
Rule of division (combinatorics)
The rule of division, also called the division principle, is a combinatorics counting rule: count an over-counted collection, then divide by the number of times each object was counted.
Sieve methods (combinatorics)
Sieve methods are combinatorial counting techniques, rooted in the inclusion–exclusion principle, that strike out unwanted objects to control the explosion of terms, from Eratosthenes to Brun.
Spelling bee
Spelling bee: oral spelling competition, mainly American, in which students spell words aloud until one remains. Best known via the Scripps National Spelling Bee (since 1925); 2026 champion Shrey Parikh set a spell-off record of 32 words in 90 seconds.
Squarefree word
A squarefree word is a string of symbols containing no immediately repeated block, such as cocoa; Thue showed in 1906 that arbitrarily long ones exist over three letters.
Stable matching problem
The stable matching problem, also called the stable marriage problem, asks how to pair two sets of participants so no two would both prefer each other over their assigned partners.
Stars and bars (combinatorics)
Stars and bars is a counting technique in combinatorics that determines the number of ways to place n indistinguishable objects into k distinguishable bins, yielding the binomial coefficient of n + k − 1 choose n.
Stirling numbers
Stirling numbers are two families of integer arrays, s(n, k) and S(n, k), counting permutations of a set by cycles and partitions into nonempty subsets, named for James Stirling.
Stirling numbers and exponential generating functions in symbolic combinatorics
Stirling numbers of the first and second kind have closed-form exponential generating functions, which in symbolic combinatorics turn classical recurrences into consequences of simple set constructions.
Stirling numbers of the first kind
Stirling numbers of the first kind, named for James Stirling, count the permutations of n objects that decompose into exactly k cycles and appear as coefficients when a falling factorial is expanded in powers.
Stirling numbers of the second kind
Stirling numbers of the second kind, also called Stirling partition numbers, count the ways to partition a set of n labeled elements into exactly k nonempty subsets.
Sturmian word
A Sturmian word, also known as a billiard sequence, is an infinite word over two letters with exactly n + 1 distinct subwords of each length n, the minimum for an aperiodic word.
Substring
A substring, also known as a subword or factor, is a contiguous sequence of characters taken from within a longer string; unlike a subsequence, it must occupy consecutive positions.
Superpermutation
A superpermutation is a string over n symbols that contains every one of the n! permutations as a contiguous substring; the minimum length remains open for n at least 6.
Thue–Morse sequence
The Thue–Morse sequence, also called the Prouhet–Thue–Morse sequence or parity sequence, is an infinite binary sequence whose nth term is the parity of the number of 1s in the binary expansion of n.
Trace monoid
A trace monoid, also called a free partially commutative monoid, is a monoid obtained from a free monoid by declaring certain pairs of generators to commute; its elements, called traces, model concurrent computation.