Combinatorics

← Back to Domain-Specific Abstractions by Domain

16 domain-specific abstractions whose origin domain is Combinatorics.

• 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.
• Antimatroid — A union-closed accessible set system modeling knowledge or construction states in which feasible elements can be added one at a time and, once available, remain available until chosen.
• Baxter Permutation — A finite permutation avoiding the adjacency-sensitive patterns 2-41-3 and 3-14-2, forming an enumerated family with recursive, planar, tree, rectangulation, and algebraic representations.
• Binomial transform — An invertible triangular sequence transform that combines source terms with signed or unsigned binomial coefficients under a declared convention.
• 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.
• Helly family — A set family in which global intersection follows whenever every sufficiently small subfamily has nonempty intersection.
• Inclusion–exclusion principle — A counting identity that obtains the size or measure of a union by alternating sums over intersections, correcting repeated counting at every overlap order.
• Independence system — A finite ground set paired with a downward-closed family of feasible subsets containing the empty set.
• 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.
• Narumi polynomials — A parameterized Sheffer polynomial sequence defined by the exponential generating function (t/log(1+t))^a(1+t)x.
• Perfect ruler — An integer-marked ruler for which every distance through a stated maximum occurs exactly once as a positive difference between two marks.
• Q-difference polynomial — A polynomial sequence lowered by the q-derivative according to D_q p_n=[n]q p(n−1), generalizing Appell polynomials and ordinary differentiation.
• Recursive tree — A rooted labeled non-plane tree whose labels increase strictly along every path away from the root, often generated by attaching each new label to an earlier vertex.
• 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.
• 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.