Combinatorial Enumeration & Sequences

← Back to Domain-Specific Families

Abstractions about counting and enumerating discrete structures, including integer sequences, permutation statistics, partitions, lattice paths and symmetric functions, together with the algebraic transforms and inequalities that relate them.

38 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• 0/1-polytope — A convex polytope whose vertices are selected binary vectors from a finite-dimensional hypercube.
• Addition principle — The counting rule that mutually exclusive alternatives have a total number of possibilities equal to the sum of their individual counts.
• Ahlswede–Daykin inequality — A four-functions inequality on a finite distributive lattice that lifts a pointwise join–meet product bound to corresponding sums over subsets.
• Binomial transform — An invertible triangular sequence transform that combines source terms with signed or unsigned binomial coefficients under a declared convention.
• Catalan number — The integer sequence C_n=(1/(n+1)) binomial(2n,n) that counts many recursively nested structures such as balanced parentheses, polygon triangulations and binary trees.
• Combinatorial explosion — The superpolynomial—often exponential or factorial—growth of candidate configurations as problem dimensions increase, making exhaustive representation or search rapidly infeasible.
• Combinatorial number system — A bijective representation of nonnegative integers as fixed-size combinations through sums of binomial coefficients, enabling direct ranking and unranking without listing earlier combinations.
• Costas array — A permutation array whose displacement vector between every pair of dots is unique.
• Derangement — A permutation with no fixed points, so every element moves away from its original position.
• Discrepancy theory — The study of how evenly discrete points, signs, or colors can approximate a desired continuous or balanced distribution over a family of test sets.
• Durfee square — The largest square contained in the Ferrers or Young diagram of an integer partition.
• Eulerian number — A permutation-counting number classified by an exact number of ascents or, under shifted conventions, descents.
• Flag algebra — Razborov's algebraic framework for asymptotic densities of partially labeled finite structures, turning extremal combinatorics inequalities into positive semidefinite and semidefinite-programming certificates.
• Hales–Jewett theorem — A Ramsey-theoretic theorem guaranteeing a monochromatic combinatorial line in every sufficiently high-dimensional finite word cube.
• Higher spin alternating sign matrix — A square integer matrix whose row and column sums equal a fixed positive spin r and whose running partial sums along every row and column remain between zero and r.
• Hyperharmonic number — A recursively iterated family of partial sums beginning with reciprocals and extending the ordinary harmonic numbers by an order parameter.
• Incidence algebra — An algebra of interval-indexed functions on a locally finite partially ordered set, with multiplication given by convolution over intermediate elements.
• Lah number — A signed or unsigned combinatorial coefficient converting rising factorials to falling factorials and counting partitions of n labeled elements into k nonempty linearly ordered lists.
• Lobb number — A two-parameter ballot number counting prefixes of balanced-parenthesis paths with a specified excess of open parentheses, generalizing Catalan numbers.
• Motzkin number — A sequence whose nth term counts noncrossing chord matchings on n labeled points in convex position, allowing unmatched points.
• Order polynomial — The polynomial whose value at n counts order-preserving maps from a finite poset to an n-element chain.
• Order polytope — The convex polytope of order-preserving maps from a finite poset into the unit interval.
• Perfect ruler — An integer-marked ruler for which every distance through a stated maximum occurs exactly once as a positive difference between two marks.
• Piecewise syndetic set — A subset of the natural numbers whose gaps are uniformly bounded on arbitrarily long intervals.
• Poly-Bernoulli number — A doubly indexed integer sequence defined by an exponential generating function involving the polylogarithm and generalizing Bernoulli numbers.
• Quasisymmetric function — A bounded-degree formal power series whose coefficient depends on an exponent composition but not on the particular increasing sequence of variable indices.
• Rank of a partition — Associate an integer partition with Dyson's rank—largest part minus number of parts—while distinguishing the separate Durfee-square rank convention used elsewhere in combinatorics.
• Representation theory of the symmetric group — The classification and analysis of symmetric-group actions on vector spaces through partitions, Young diagrams, tableaux, characters and Specht modules.
• Robinson–Schensted–Knuth correspondence — A weight-preserving bijection between nonnegative-integer matrices and pairs of semistandard Young tableaux of equal shape.
• Sauer–Shelah lemma — An extremal bound stating that a set family of VC dimension d on an n-element ground set has at most the sum of binomial(n,i) for i from zero through d members.
• Schröder number — A sequence counting diagonal-bounded lattice paths with horizontal, vertical and diagonal steps, equivalently several recursively decomposable combinatorial structures.
• Schuette–Nesbitt formula — A weighted generalization of inclusion–exclusion that expresses sums over outcomes with exactly or at least a given number of occurring events.
• Signed set — A set equipped with a positive-or-negative label on every element, equivalently an ordered pair of disjoint positive and negative subsets or a map to a two-element sign set.
• Stanley symmetric function — A symmetric function indexed by a permutation and generated from its reduced words, encoding reduced-decomposition and Schubert-polynomial combinatorics.
• Stirling numbers of the second kind — The numbers S(n,k) counting partitions of an n-element labeled set into exactly k nonempty unlabeled blocks.
• Stirling transform — The invertible sequence transform that weights source terms by Stirling numbers of the second kind, with inverse coefficients given by signed first-kind Stirling numbers.
• Turán number — The minimum number of r-element blocks on n vertices needed so every k-element vertex subset contains at least one block.
• Ulam number — Generate a seed-dependent increasing integer sequence by repeatedly choosing the least larger integer having exactly one representation as a sum of two distinct earlier terms.