Combinatorial class

Last updated September 25, 2019

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]

Mathematics Field of study concerning quantity, patterns and change

Mathematics includes the study of such topics as quantity, structure (algebra), space (geometry), and change. It has no generally accepted definition.

In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set. Whether finite or infinite, the elements of a countable set can always be counted one at a time and, although the counting may never finish, every element of the set is associated with a unique natural number.

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.

In mathematics, a generating function is a way of encoding an infinite sequence of numbers (a_n) by treating them as the coefficients of a power series. This formal power series is the generating function. Unlike an ordinary series, this formal series is allowed to diverge, meaning that the generating function is not always a true function and the "variable" is actually an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal series in more than one indeterminate, to encode information about arrays of numbers indexed by several natural numbers.

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 infinite collection of finite sets S_i indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in S_n for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.

In combinatorics, bijective proof is a proof technique that finds a bijective function $f : A \to B$ between two finite sets $A$ and $B$ , or a size-preserving bijective function between two combinatorial classes, thus proving that they have the same number of elements, $| A | = | B |$ . One place the technique is useful is where we wish to know the size of $A$ , but can find no direct way of counting its elements. By establishing a bijection from $A$ to some $B$ solves the problem if $B$ is more easily countable. Another useful feature of the technique is that the nature of the bijection itself often provides powerful insights into each or both of the sets.

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]

In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

In Euclidean geometry, a regular polygon is a polygon that is equiangular and equilateral. Regular polygons may be either convex or star. In the limit, a sequence of regular polygons with an increasing number of sides approximates a circle, if the perimeter or area is fixed, or a regular apeirogon, if the edge length is fixed.

In mathematics and computer science, an unrooted binary tree is an unrooted tree in which each vertex has either one or three neighbors.

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]

In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for analysing discrete structures in terms of generating functions. Examples of discrete structures are (finite) graphs, permutations, trees, and so on; each of these has an associated generating function which counts how many structures there are of a certain size. One goal of species theory is to be able to analyse complicated structures by describing them in terms of transformations and combinations of simpler structures. These operations correspond to equivalent manipulations of generating functions, so producing such functions for complicated structures is much easier than with other methods. The theory was introduced, carefully elaborated and applied by the Canadian group of people around André Joyal.

In mathematics, the disjoint union of a family $of sets is a set with an injective function of each into A, such that the union of the images of these injections form a partition of A .$

In set theory, a Cartesian product is a mathematical operation that returns a set from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. Products can be specified using set-builder notation, e.g.

Permutation patterns

In the study of permutation patterns, a combinatorial class of permutation classes, enumerated by permutation length, is called a Wilf class.^[6] The study of enumerations of specific permutation classes has turned up unexpected equivalences in counting sequences of seemingly unrelated permutation classes.

In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the permutation to the digit sequence 123...; for instance the digit sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way, then π is said to contain σ as a pattern if some subsequence of the digits of π has the same relative order as all of the digits of σ.

In the study of permutations and permutation patterns, a permutation class is a set $of permutations such that every pattern within a permutation in is also in . That is, it is a downset in the permutation pattern order. A permutation class may also be known as a pattern class, closed class, or simply class of permutations.$

In the study of permutation patterns, there has been considerable interest in enumerating specific permutation classes, especially those with relatively few basis elements. This area of study has turned up unexpected instances of Wilf equivalence, where two seemingly-unrelated permutation classes have the same numbers of permutations of each length.

Related Research Articles

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc.

Isomorphism In mathematics, invertible homomorphism

In mathematics, an isomorphism is a homomorphism or morphism that can be reversed by an inverse morphism. Two mathematical objects are isomorphic if an isomorphism exists between them. An automorphism is an isomorphism whose source and target coincide. The interest of isomorphisms lies in the fact that two isomorphic objects cannot be distinguished by using only the properties used to define morphisms; thus isomorphic objects may be considered the same as long as one considers only these properties and their consequences.

In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894).

In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus and analysis.

In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof:

In combinatorics, especially in analytic combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet and is detailed in Part A of his book with Robert Sedgewick, Analytic Combinatorics. Similar languages for specifying combinatorial classes and their generating functions are found in work by Bender and Goldman, Foata and Schützenberger, and Joyal. The presentation in this article borrows somewhat from Joyal's combinatorial species.

In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.

In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. The idea of the classification is credited to Gian-Carlo Rota, and the name was suggested by Joel Spencer.

Pseudotriangle subset of the plane that lies between any three mutually tangent convex sets

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

In computer science and discrete mathematics, a sequence has an inversion where two of its elements are out of their natural order.

In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that one of the orders can be obtained from the other just by renaming of elements. Two strictly weaker notions that relate to order isomorphisms are order embeddings and Galois connections.

In number theory, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the number of plane trees with a given set of leaves, the number of ways of inserting parentheses into a sequence, and the number of ways of dissecting a convex polygon into smaller polygons by inserting diagonals. These numbers begin

In mathematics, the telephone numbers or the involution numbers are a sequence of integers that count the ways $n$ telephone lines can be connected to each other, where each line can be connected to at most one other line. These numbers also describe the number of matchings of a complete graph on $n$ vertices, the number of permutations on $n$ elements that are involutions, the sum of absolute values of coefficients of the Hermite polynomials, the number of standard Young tableaux with $n$ cells, and the sum of the degrees of the irreducible representations of the symmetric group. Involution numbers were first studied in 1800 by Heinrich August Rothe, who gave a recurrence equation by which they may be calculated, giving the values

In mathematics, equivalent definitions are used in two somewhat different ways. First, within a particular mathematical theory, a notion may have more than one definition. These definitions are equivalent in the context of a given mathematical structure. Second, a mathematical structure may have more than one definition.

Mireille Bousquet-Mélou is a French mathematician who specializes in enumerative combinatorics and who works as a senior researcher for the Centre national de la recherche scientifique (CNRS) at the computer science department (LaBRI) of the University of Bordeaux.

References

↑ Martínez, Conrado; Molinero, Xavier (2001), "A generic approach for the unranking of labeled combinatorial classes" (PDF), 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 .
1 2 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, 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 .
↑ Steingrímsson, Einar (2013), "Some open problems on permutation patterns", Surveys in combinatorics 2013, London Math. Soc. Lecture Note Ser., 409, Cambridge Univ. Press, Cambridge, pp. 239–263, MR 3156932

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Martínez, Conrado; Molinero, Xavier (2001), "A generic approach for the unranking of labeled combinatorial classes" (PDF), Random Structures & Algorithms, 19 (3–4): 472–497, doi:10.1002/rsa.10025, MR 1871563 .

[2] 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 .

[ac-3] 1 2 Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, Definition I.3, p.19, ISBN 9781139477161 .

[4] De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010), Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, 25, Springer, Theorem 1.1.3, pp. 4–6, ISBN 9783642129711 .

[5] Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34, ISBN 9780387887579 .

[6] Steingrímsson, Einar (2013), "Some open problems on permutation patterns", Surveys in combinatorics 2013, London Math. Soc. Lecture Note Ser., 409, Cambridge Univ. Press, Cambridge, pp. 239–263, MR 3156932