Combinatorial class

In mathematics, a combinatorial class is a countable set 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. 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 that has these numbers as its coefficients. The counting sequences of combinatorial classes are the main subject of study of enumerative combinatorics. 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 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 triangulations of regular polygons (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, with a fixed ordering of the leaves, and with size given by the number of leaves) are both counted by the Catalan numbers, 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. The theory of combinatorial species and its extension to analytic combinatorics provide a language for describing many important combinatorial classes, constructing new classes from combinations of previously defined ones, and automatically deriving their counting sequences.