Editing 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.<ref>{{citation
 | last1 = Martínez | first1 = Conrado
 | last2 = Molinero | first2 = Xavier
 | doi = 10.1002/rsa.10025
 | issue = 3–4
 | journal = Random Structures & Algorithms
 | mr = 1871563
 | pages = 472–497
 | title = A generic approach for the unranking of labeled combinatorial classes
 | volume = 19
 | year = 2001| url = http://www.lsi.upc.edu/~conrado/research/papers/rsa-mm01.pdf
 }}.</ref><ref>{{citation
 | last1 = Duchon | first1 = Philippe
 | last2 = Flajolet | first2 = Philippe | authorlink = Philippe Flajolet
 | last3 = Louchard | first3 = Guy
 | last4 = Schaeffer | first4 = Gilles
 | doi = 10.1017/S0963548304006315
 | issue = 4–5
 | journal = [[Combinatorics, Probability and Computing]]
 | mr = 2095975
 | pages = 577–625
 | title = Boltzmann samplers for the random generation of combinatorial structures
 | volume = 13
 | year = 2004}}.</ref>

==Counting sequences and isomorphism==
The ''counting sequence'' of a combinatorial class is the sequence of the numbers of elements of size ''i'' for ''i''&nbsp;=&nbsp;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.<ref name="ac">{{citation|title=Analytic Combinatorics|first1=Philippe|last1=Flajolet|author1-link=Philippe Flajolet|first2=Robert|last2=Sedgewick|author2-link=Robert Sedgewick (computer scientist)|publisher=Cambridge University Press|year=2009|isbn=9781139477161|at=Definition I.3, p.19|title-link= Analytic Combinatorics}}.</ref> 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 [[cryptomorphism|cryptomorphic]] to each other.

For instance, the [[Polygon triangulation|triangulation]]s of [[regular polygon]]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 tree|unrooted binary]] [[Tree_(graph_theory)#Plane_tree|plane tree]]s (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 number]]s, so they form isomorphic combinatorial classes. A bijective isomorphism in this case is given by [[Dual graph|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.<ref>{{citation|title=Triangulations: Structures for Algorithms and Applications|volume=25|series=Algorithms and Computation in Mathematics|first1=Jesús A.|last1=De Loera|author1-link=Jesús A. De Loera|first2=Jörg|last2=Rambau|first3=Francisco|last3=Santos|publisher=Springer|year=2010|isbn=9783642129711|url=https://books.google.com/books?id=SxY1Xrr12DwC&pg=PA4|at=Theorem 1.1.3, pp. 4–6}}.</ref>

==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.<ref name="ac"/> 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]].<ref>{{citation|title=Algebraic Cryptanalysis|first=Gregory V.|last=Bard|publisher=Springer|year=2009|isbn=9780387887579|at=Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34|url=https://books.google.com/books?id=kjbp0mgu3IAC&pg=PA30}}.</ref>

==Permutation patterns==
In the study of [[permutation pattern]]s, a combinatorial class of [[permutation class]]es, enumerated by permutation length, is called a [[Wilf class]].<ref>{{citation
 | last = Steingrímsson | first = Einar
 | contribution = Some open problems on permutation patterns
 | mr = 3156932
 | pages = 239–263
 | publisher = Cambridge Univ. Press, Cambridge
 | series = London Math. Soc. Lecture Note Ser.
 | title = Surveys in combinatorics 2013
 | volume = 409
 | year = 2013}}</ref> The study of [[enumerations of specific permutation classes]] has turned up unexpected equivalences in counting sequences of seemingly unrelated permutation classes.

==References==
{{reflist}}

{{DEFAULTSORT:Combinatorial Class}}
[[Category:Combinatorics]]