Combinatorial class
Encyclopedia
In combinatorics
, a combinatorial class (or simply class) is an equivalence class of sets that have the same counting sequence. Although the elements of these equivalent sets may have very different definitions and semantics, combinatorics is concerned only with the number of elements of a given size. Therefore, knowledge about one set in the class can be applied directly to other sets in the class.
For example, the set of triangulation
s of polygon
s is combinatorially isomorphic to the set of general rooted plane trees. Although these sets certainly describe different things, they have the same counting sequence, namely the Catalan number
s.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, a combinatorial class (or simply class) is an equivalence class of sets that have the same counting sequence. Although the elements of these equivalent sets may have very different definitions and semantics, combinatorics is concerned only with the number of elements of a given size. Therefore, knowledge about one set in the class can be applied directly to other sets in the class.
For example, the set of triangulation
Triangulation
In trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly...
s of polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
s is combinatorially isomorphic to the set of general rooted plane trees. Although these sets certainly describe different things, they have the same counting sequence, namely the Catalan number
Catalan number
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involvingrecursively defined objects...
s.
See also
- double countingDouble counting (proof technique)In combinatorics, double counting, also called counting in two ways, is a combinatorial proof technique for showing that two expressions are equal by demonstrating that they are two ways of counting the size of one set...
- combinatorial speciesCombinatorial speciesIn 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 graphs, permutations, trees, and so on; each of these has an associated generating function...
.