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.[1][2]
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 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.[3] 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.[4]
Analytic combinatorics
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.[3] For example, two combinatorial classes may be combined by disjoint union, or by a Cartesian product 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 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.[5]
References
- ^ Martínez, Conrado; Molinero, Xavier (2001), "A generic approach for the unranking of labeled combinatorial classes", Random Structures & Algorithms, 19 (3–4): 472–497, doi:10.1002/rsa.10025, MR 1871563.
- ^ Duchon, Philippe; Flajolet, Philippe; Louchard, Guy; Schaeffer, Gilles (2004), "Boltzmann samplers for the random generation of combinatorial structures", Combinatorics, Probability and Computing, 13 (4–5): 577–625, doi:10.1017/S0963548304006315, MR 2095975.
- ^ a b Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, Definition I.3, p.19, ISBN 9781139477161.
- ^ De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010), Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, vol. 25, Springer, Theorem 1.1.3, pp. 4–6, ISBN 9783642129711.
- ^ Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34, ISBN 9780387887579.