mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a combinatorial class is a

countable set In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbe ...

of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size.

Counting sequences and isomorphism

The ''counting sequence'' of a combinatorial class is the sequence of the numbers of elements of size ''i'' for ''i'' = 0, 1, 2, ...; it may also be described as a

generating function In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...

that has these numbers as its coefficients. The counting sequences of combinatorial classes are the main subject of study of

enumerative combinatorics Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an inf ...

. Two combinatorial classes are said to be isomorphic if they have the same numbers of objects of each size, or equivalently, if their counting sequences are the same.. Frequently, once two combinatorial classes are known to be isomorphic, a

bijective proof In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other ...

of this equivalence is sought; such a proof may be interpreted as showing that the objects in the two isomorphic classes are cryptomorphic to each other. For instance, the

triangulation In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points. Applications In surveying Specifically in surveying, triangulation involves only angle m ...

s of

regular polygon In Euclidean geometry, a regular polygon is a polygon that is Equiangular polygon, direct equiangular (all angles are equal in measure) and Equilateral polygon, equilateral (all sides have the same length). Regular polygons may be either ''convex ...

s (with size given by the number of sides of the polygon, and a fixed choice of polygon to triangulate for each size) and the set of unrooted binary plane trees (up to

graph isomorphism In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...

, with a fixed ordering of the leaves, and with size given by the number of leaves) are both counted by the

Catalan number The Catalan numbers are a sequence of natural numbers that occur in various Enumeration, counting problems, often involving recursion, recursively defined objects. They are named after Eugène Charles Catalan, Eugène Catalan, though they were p ...

s, so they form isomorphic combinatorial classes. A bijective isomorphism in this case is given by planar graph duality: a triangulation can be transformed bijectively into a tree with a leaf for each polygon edge, an internal node for each triangle, and an edge for each two (polygon edges?) or triangles that are adjacent to each other.

Analytic combinatorics

The theory of combinatorial species and its extension to

analytic combinatorics Analytic combinatorics uses techniques from complex analysis to solve problems in enumerative combinatorics, specifically to find asymptotic estimates for the coefficients of generating functions. History One of the earliest uses of analyti ...

provide a language for describing many important combinatorial classes, constructing new classes from combinations of previously defined ones, and automatically deriving their counting sequences. For example, two combinatorial classes may be combined by

disjoint union In mathematics, the disjoint union (or discriminated union) A \sqcup B of the sets and is the set formed from the elements of and labelled (indexed) with the name of the set from which they come. So, an element belonging to both and appe ...

, or by a

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...

construction in which the objects are ordered pairs of one object from each of two classes, and the size function is the sum of the sizes of each object in the pair. These operations respectively form the addition and multiplication operations of a

semiring In abstract algebra, a semiring is an algebraic structure. Semirings are a generalization of rings, dropping the requirement that each element must have an additive inverse. At the same time, semirings are a generalization of bounded distribu ...

on the family of (isomorphism equivalence classes of) combinatorial classes, in which the zero object is the empty combinatorial class, and the unit is the class whose only object is the

empty set In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...

Permutation patterns

In the study of

permutation pattern In combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of entries representing the result of a ...

s, a combinatorial class of permutation classes, enumerated by permutation length, is called a Wilf class. The study of enumerations of specific permutation classes has turned up unexpected equivalences in counting sequences of seemingly unrelated permutation classes.

References

{{DEFAULTSORT:Combinatorial Class Combinatorics