anitsh
commented
3 years ago Mathematics Foundations
Dihedral Group
In mathematics, a dihedral group is the group of symmetries of a regular polygon,[1][2] which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.
Objects And Representations
We have to clearly distinguish between the number of objects and the number of representations.
Different representations can correspond to the same objects, but of course any representation corresponds to exactly one object. Consequently, the set of all representations is divided into equivalence classes. Our task is to compute the number of objects, or equivalently, the number of equivalence classes. The following example will make the difference between object and representation clearer.
The number of rotationally distinct colourings of the faces of a cube using three colours can be determined from this formula as follows:
Let X be the set of 36 possible face colour combinations that can be applied to a cube in one particular orientation, and let the rotation group G of the cube act on X in the natural manner. Then two elements of X belong to the same orbit precisely when one is simply a rotation of the other. The number of rotationally distinct colourings is thus the same as the number of orbits and can be found by counting the sizes of the fixed sets for the 24 elements of G.
- one identity element which leaves all 3^6 elements of X unchanged
- six 90-degree face rotations, each of which leaves 3^3 of the elements of X unchanged
- three 180-degree face rotations, each of which leaves 3^4 of the elements of X unchanged
- eight 120-degree vertex rotations, each of which leaves 3^2 of the elements of X unchanged
- six 180-degree edge rotations, each of which leaves 3^3 of the elements of X unchanged
Formula:
The Pólya enumeration theorem is a generalization of Burnside's lemma, and it also provides a more convenient tool for finding the number of equivalence classes.
Group Theory
It is the study of groups. Groups are sets equipped with an operation (like multiplication, addition, or composition) that satisfies certain basic properties. As the building blocks of abstract algebra, groups are so general and fundamental that they arise in nearly every branch of mathematics and the sciences. For example: Symmetry groups appear in the study of combinatorics overview and algebraic number theory, as well as physics and chemistry.
Group
A group is a set equipped with an operation that combines any two elements to form a third element while being associative as well as having an identity element and inverse elements.
Group Action
A group action on a space is a group homomorphism of a given group into the group of transformations of the space. The group of symmetries of a polyhedron acts on the vertices, the edges, and the faces of the polyhedron.
The symmetric group Sn acts on any set with n elements by permuting the elements of the set.
Symmetry
An object that is invariant under some transformations; including translation, reflection, rotation or scaling.
Symmetry Group
Two figures in the plane are congruent if one can be changed into the other using a combination of rotations, reflections, and translations.
Symmetry groups appear in the study of combinatorics overview and algebraic number theory, as well as physics and chemistry. For example, Burnside's lemma can be used to count combinatorial objects associated with symmetry groups.
Any figure is congruent to itself. However, some figures are congruent to themselves in more than one way, and these extra congruences are called symmetries. A square has eight symmetries. These are:
Commutative Property
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of the property that says "3 + 4 = 4 + 3" or "2 × 5 = 5 × 2", the property can also be used in more advanced settings. The name is needed because there are operations, such as division and subtraction, that do not have it (for example, "3 − 5 ≠ 5 − 3"); such operations are not commutative, and so are referred to as noncommutative operations. The idea that simple operations, such as the multiplication and addition of numbers, are commutative was for many years implicitly assumed. Thus, this property was not named until the 19th century, when mathematics started to become formalized.[1][2] A corresponding property exists for binary relations; a binary relation is said to be symmetric if the relation applies regardless of the order of its operands; for example, equality is symmetric as two equal mathematical objects are equal regardless of their order.
The commutative property (or commutative law) is a property generally associated with binary operations and functions. If the commutative property holds for a pair of elements under a certain binary operation then the two elements are said to commute under that operation.
Abelian Ggroup
An abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commutative. With addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples.
A corresponding property exists for binary relations; a binary relation is said to be symmetric if the relation applies regardless of the order of its operands; for example, equality is symmetric as two equal mathematical objects are equal regardless of their order.
Binary Operation
a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of the property that says "3 + 4 = 4 + 3" or "2 × 5 = 5 × 2", the property can also be used in more advanced settings. The name is needed because there are operations, such as division and subtraction, that do not have it (for example, "3 − 5 ≠ 5 − 3"); such operations are not commutative, and so are referred to as non-commutative operations.
More specifically, a binary operation on a set is an operation whose two domains and the codomain are the same set. Examples include the familiar arithmetic operations of addition, subtraction, multiplication. Other examples are readily found in different areas of mathematics, such as vector addition, matrix multiplication and conjugation in groups.
An operation of arity two that involves several sets is sometimes also called a binary operation. For example, scalar multiplication of vector spaces takes a scalar and a vector to produce a vector, and scalar product takes two vectors to produce a scalar. Such binary operations may be called simply binary functions.
Binary operations are the keystone of most algebraic structures, that are studied in algebra, in particular in semigroups, monoids, groups, rings, fields, and vector spaces.
More precisely, a binary operation on a set S is a mapping of the elements of the Cartesian product S × S to S:[1][2][3]
f : S × S → S . {\displaystyle \,f\colon S\times S\rightarrow S.} \,f \colon S \times S \rightarrow S.Because the result of performing the operation on a pair of elements of S is again an element of S, the operation is called a closed (or internal) binary operation on S (or sometimes expressed as having the property of closure).[4]
If f is not a function, but a partial function, then f is called a partial binary operation. For instance, division of real numbers is a partial binary operation, because one can't divide by zero: a/0 is undefined for every real number a. In both universal algebra and model theory, binary operations are required to be defined on all of S × S.
Sometimes, especially in computer science, the term binary operation is used for any binary function.
Binary Relation
A binary relation over sets X and Y is a subset of the Cartesian product X × Y; that is, it is a set of ordered pairs (x, y) consisting of elements x in X and y in Y.[1] It encodes the common concept of relation: an element x is related to an element y, if and only if the pair (x, y) belongs to the set of ordered pairs that defines the binary relation.
Since relations are sets, they can be manipulated using set operations, including union, intersection, and complementation, and satisfying the laws of an algebra of sets. Beyond that, operations like the converse of a relation and the composition of relations are available, satisfying the laws of a calculus of relations. A deeper analysis of relations involves decomposing them into subsets called concepts, and placing them in a complete lattice.
In some systems of axiomatic set theory, relations are extended to classes, which are generalizations of sets. This extension is needed for, among other things, modeling the concepts of "is an element of" or "is a subset of" in set theory, without running into logical inconsistencies such as Russell's paradox.
Operations on binary relations are union, intersection, composition, converse, complement, restriction and matrix representation.
Cardinality
The cardinality of a set is a measure of the "number of elements" of the set. For example, the set A = { 2 , 4 , 6 } contains 3 elements, and therefore A {A} A has a cardinality of 3.
The cardinality of a set is also called its size, when no confusion with other notions of size is possible.
Two sets A and B have the same cardinality if there exists a bijection (a.k.a., one-to-one correspondence) from A to B which is represented as |A| = |B|.
Cartesian Product
In mathematics, specifically set theory, the Cartesian product of two sets A and B, denoted A × B,[1] is the set of all ordered pairs (a, b) where a is in A and b is in B.[2] In terms of set-builder notation, that is A × B = { ( a , b ) ∣ a ∈ A and b ∈ B }
Axiom
An axiom (or postulate or assumption) is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments.
Binary Function
A binary function (also called bivariate function, or function of two variables) is a function that takes two inputs.
Precisely stated, a function f is binary if there exists sets X,Y,Z such that f : X × Y → Z where X × Y is the Cartesian product of X and Y.
Venn Diagram
A Venn diagram is a widely-used diagram style that shows the logical relation between sets, popularized by John Venn in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple set relationships in probability, logic, statistics, linguistics and computer science. A Venn diagram uses simple closed curves drawn on a plane to represent sets. Very often, these curves are circles or ellipses.
Arity
Arity is the number of arguments or operands taken by a function or operation in logic, mathematics, and computer science. In mathematics, arity may also be named rank, but this word can have many other meanings in mathematics. In logic and philosophy, it is also called adicity and degree. In linguistics, it is usually named valency.
Set
A set is a collection of distinct elements. The elements that make up a set can be any kind of things: people, letters of the alphabet, numbers, points in space, lines, other geometrical shapes, variables, or even other sets. Two sets are equal if and only if they have precisely the same elements.
Figure: A set of polygons in an Euler diagram
Set Theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concerned with those that are relevant to mathematics as a whole.
Class
In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share. The precise definition of "class" depends on foundational context. In work on Zermelo–Fraenkel set theory, the notion of class is informal, whereas other set theories, such as von Neumann–Bernays–Gödel set theory, axiomatize the notion of "proper class", e.g., as entities that are not members of another entity.
A class that is not a set (informally in Zermelo–Fraenkel) is called a proper class, and a class that is a set is sometimes called a small class. For instance, the class of all ordinal numbers, and the class of all sets, are proper classes in many formal systems.
In Quine's set-theoretical writing, the phrase "ultimate class" is often used instead of the phrase "proper class" emphasising that in the systems he considers, certain classes cannot be members, and are thus the final term in any membership chain to which they belong.
Outside set theory, the word "class" is sometimes used synonymously with "set". This usage dates from a historical period where classes and sets were not distinguished as they are in modern set-theoretic terminology. Many discussions of "classes" in the 19th century and earlier are really referring to sets, or perhaps rather take place without considering that certain classes can fail to be sets.
Cosets
A subgroup H of a group G may be used to decompose the underlying set of G into disjoint equal-size subsets called cosets. There are left cosets and right cosets. Cosets (both left and right) have the same number of elements (cardinality) as does H. Furthermore, H itself is both a left coset and a right coset. The number of left cosets of H in G is equal to the number of right cosets of H in G. This common value is called the index of H in G and is usually denoted by [G : H].
Cosets are a basic tool in the study of groups; for example, they play a central role in Lagrange's theorem that states that for any finite group G, the number of elements of every subgroup H of G divides the number of elements of G. Cosets of a particular type of subgroup (a normal subgroup) can be used as the elements of another group called a quotient group or factor group. Cosets also appear in other areas of mathematics such as vector spaces and error-correcting codes.
Orbit-Stabilizer Theorem
Orbits and stabilizers are closely related.
Think about the symmetric group of a cube. Call this group G and it acts on the cube. If you want to know how many elements there are in G, then you can think about it in two steps. Step I: If you fix one face, there are 4 ways to move the cube because you can only rotate the cube now. (These are the stabilizers ) Step II: There are six possible choice where this face can go. (Orbit of the face). So you figure out |G|=4⋅6
Combinatorics
- The enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems.
- The existence of such structures that satisfy certain given criteria.
- The construction of these structures, perhaps in many ways.
- Optimization, finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimality criterion.
Isomorphism
An isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word isomorphism is derived from the Ancient Greek: ἴσος isos "equal", and μορφή morphe "form" or "shape".
The interest in isomorphisms lies in the fact that two isomorphic objects have the same properties (excluding further information such as additional structure or names of objects). Thus isomorphic structures cannot be distinguished from the point of view of structure only, and may be identified. In mathematical jargon, one says that two objects are the same up to an isomorphism
The term isomorphism is mainly used for algebraic structures. In this case, mappings are called homomorphisms, and a homomorphism is an isomorphism if and only if it is bijective (1 to 1 mapping).
Mathematical Object
A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an object is anything that has been (or could be) formally defined, and with which one may do deductive reasoning and mathematical proofs. Typically, a mathematical object can be a value that can be assigned to a variable, and therefore can be involved in formulas. Commonly encountered mathematical objects include numbers, sets, functions, expressions, geometric shapes, transformations of other mathematical objects, and spaces. Mathematical objects can be very complex; for example, theorems, proofs, and even theories are considered as mathematical objects in proof theory.
List of mathematical objects by branch
- Combinatorics
- permutations, derangements, combinations
- Set theory
- sets, set partitions
- functions, and relations
- Geometry
- points, lines, line segments,
- polygons (triangles, squares, pentagons, hexagons, ...), circles, ellipses, parabolas, hyperbolas,
- polyhedra (tetrahedrons, cubes, octahedrons, dodecahedrons, icosahedrons, ), spheres, ellipsoids, paraboloids, hyperboloids, cylinders, cones.
- Graph theory
- graphs, trees, nodes, edges
- Topology
- topological spaces and manifolds.
- Linear algebra
- scalars, vectors, matrices, tensors.
- Abstract algebra
- groups,
- rings, modules,
- fields, vector spaces,
- group-theoretic lattices, and order-theoretic lattices.
Polynomial
A polynomial is an expression consisting of variables (also called indeterminates) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponentiation of variables. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example in three variables is x3 + 2xyz2 − yz + 1.
Cycle Index
A cycle index is a polynomial in several variables which is structured in such a way that information about how a group of permutations acts on a set can be simply read off from the coefficients and exponents. This compact way of storing information in an algebraic form is frequently used in combinatorial enumeration.
Each permutation π of a finite set of objects partitions that set into cycles; the cycle index monomial of π is a monomial in variables a1, a2, … that describes the type of this partition (the cycle type of π): the exponent of ai is the number of cycles of π of size i. The cycle index polynomial of a permutation group is the average of the cycle index monomials of its elements. The phrase cycle indicator is also sometimes used in place of cycle index.
Knowing the cycle index polynomial of a permutation group, one can enumerate equivalence classes due to the group's action. This is the main ingredient in the Pólya enumeration theorem. Performing formal algebraic and differential operations on these polynomials and then interpreting the results combinatorially lies at the core of species theory.
Enumerative Combinatorics
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 Si indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn 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.
The simplest such functions are closed formulas, which can be expressed as a composition of elementary functions such as factorials, powers, and so on. For instance, as shown below, the number of different possible orderings of a deck of n cards is f(n) = n!. The problem of finding a closed formula is known as algebraic enumeration, and frequently involves deriving a recurrence relation or generating function and using this to arrive at the desired closed form.
Twelvefold Way
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.
Equivalence Relation
An equivalence relation is a binary relation that is reflexive, symmetric and transitive. The relation "is equal to" is the canonical example of an equivalence relation. Each equivalence relation provides a partition of the underlying set into disjoint equivalence classes. Two elements of the given set are equivalent to each other, if and only if they belong to the same equivalence class.
Group Homomorphism
The purpose of defining a group homomorphism is to create functions that preserve the algebraic structure. An equivalent definition of group homomorphism is: The function h : G → H is a group homomorphism if whenever a ∗ b = c we have h(a) ⋅ h(b) = h(c). In other words, the group H in some sense has a similar algebraic structure as G and the homomorphism h preserves that.
Homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces).
Homomorphisms of vector spaces are also called linear maps, and their study is the object of linear algebra.
A homomorphism may also be an isomorphism, an endomorphism, an automorphism, etc.. Each of those can be defined in a way that may be generalized to any class of morphisms.
Morphism
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms are functions; in linear algebra, linear transformations; in group theory, group homomorphisms; in topology, continuous functions, and so on.
In category theory, morphism is a broadly similar idea: the mathematical objects involved need not be sets, and the relationships between them may be something other than maps, although the morphisms between the objects of a given category have to behave similarly to maps in that they have to admit an associative operation similar to function composition. A morphism in category theory is an abstraction of a homomorphism.
The study of morphisms and of the structures (called "objects") over which they are defined is central to category theory. Much of the terminology of morphisms, as well as the intuition underlying them, comes from concrete categories, where the objects are simply sets with some additional structure, and morphisms are structure-preserving functions. In category theory, morphisms are sometimes also called arrows.
Isometry and Symmetry
An isometry is a distance preserving map from some space it itself: a rigid motion. For example, f(x)=x+5 is a isometry of the real line; the whole line is shifted by 5 and distances between points remain unchanged. A symmetry of a figure in some space is an isometry of that space which maps the figure to itself.
Euclidean plane isometry
In geometry, a Euclidean plane isometry is an isometry of the Euclidean plane, or more informally, a way of transforming the plane that preserves geometrical properties such as length. There are four types: translations, rotations, reflections, and glide reflections.
Combinatorics
- https://en.wikipedia.org/wiki/Combinatorics
- https://artofproblemsolving.com/wiki/index.php/Combinatorics
Combinatorics is involved with:
- The enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,
- The existence of such structures that satisfy certain given criteria,
- The construction of these structures, perhaps in many ways,
- optimization, finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimality criterion.
Combinatorics is the study of discrete structures broadly speaking. Most notably, combinatorics involves studying the enumeration (counting) of said structures. For example, the number of three-cycles in a given graph is a combinatorial problem, as is the derivation of a non-recursive formula for the Fibonacci numbers, and so too methods of solving the Rubiks cube. Mathematicians who spend their careers studying combinatorics are known as combinatorialists.
Combinatorial problems often make up a good portion of problems found in mathematics competitions and can be approached by a variety of techniques, such as generating functions or the principle of inclusion-exclusion. Combinatorics also has many applications outside of pure mathematics, notably in theoretical computer science, statistics, and various fields of science.
People who encounter the term combinatorics for the first time often discredit it as "easy" because they "already know how to count." While this is true in the sense that people know how to count lists of numbers, enumeration problems are (typically) not nearly as simple as counting a list of numbers. One must first determine what and how something must be counted, both of which are often difficult to do.
Below are the approaches and subfields:
Enumerative Combinatorics
Five binary trees on three vertices, an example of Catalan numbers. Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. 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. Fibonacci numbers is the basic example of a problem in enumerative combinatorics. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.
Analytic Combinatorics
Analytic combinatorics concerns the enumeration of combinatorial structures using tools from complex analysis and probability theory. In contrast with enumerative combinatorics, which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining asymptotic formulae.
Partition Theory
A plane partition.
Partition theory studies various enumeration and asymptotic problems related to integer partitions, and is closely related to q-series, special functions and orthogonal polynomials. Originally a part of number theory and analysis, it is now considered a part of combinatorics or an independent field. It incorporates the bijective approach and various tools in analysis and analytic number theory and has connections with statistical mechanics.
Graph theory
Petersen graph. Graphs are fundamental objects in combinatorics. Considerations of graph theory range from enumeration (e.g., the number of graphs on n vertices with k edges) to existing structures (e.g., Hamiltonian cycles) to algebraic representations (e.g., given a graph G and two numbers x and y, does the Tutte polynomial TG(x,y) have a combinatorial interpretation?). Although there are very strong connections between graph theory and combinatorics, they are sometimes thought of as separate subjects.[20] While combinatorial methods apply to many graph theory problems, the two disciplines are generally used to seek solutions to different types of problems.
Design Theory
Design theory is a study of combinatorial designs, which are collections of subsets with certain intersection properties. Block designs are combinatorial designs of a special type. This area is one of the oldest parts of combinatorics, such as in Kirkman's schoolgirl problem proposed in 1850. The solution of the problem is a special case of a Steiner system, which systems play an important role in the classification of finite simple groups. The area has further connections to coding theory and geometric combinatorics.
Finite Geometry
Finite geometry is the study of geometric systems having only a finite number of points. Structures analogous to those found in continuous geometries (Euclidean plane, real projective space, etc.) but defined combinatorially are the main items studied. This area provides a rich source of examples for design theory. It should not be confused with discrete geometry (combinatorial geometry).
Order Theory
Hasse diagram of the powerset of {x,y,z} ordered by inclusion. Order theory is the study of partially ordered sets, both finite and infinite. Various examples of partial orders appear in algebra, geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders include lattices and Boolean algebras.
Matroid Theory
Matroid theory abstracts part of geometry. It studies the properties of sets (usually, finite sets) of vectors in a vector space that do not depend on the particular coefficients in a linear dependence relation. Not only the structure but also enumerative properties belong to matroid theory. Matroid theory was introduced by Hassler Whitney and studied as a part of order theory. It is now an independent field of study with a number of connections with other parts of combinatorics.
Extremal Combinatorics
Extremal combinatorics studies extremal questions on set systems. The types of questions addressed in this case are about the largest possible graph which satisfies certain properties. For example, the largest triangle-free graph on 2n vertices is a complete bipartite graph Kn,n. Often it is too hard even to find the extremal answer f(n) exactly and one can only give an asymptotic estimate.
Ramsey theory is another part of extremal combinatorics. It states that any sufficiently large configuration will contain some sort of order. It is an advanced generalization of the pigeonhole principle.
Probabilistic Combinatorics
Self-avoiding walk in a square grid graph. In probabilistic combinatorics, the questions are of the following type: what is the probability of a certain property for a random discrete object, such as a random graph? For instance, what is the average number of triangles in a random graph? Probabilistic methods are also used to determine the existence of combinatorial objects with certain prescribed properties (for which explicit examples might be difficult to find), simply by observing that the probability of randomly selecting an object with those properties is greater than 0. This approach (often referred to as the probabilistic method) proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finite Markov chains, especially on combinatorial objects. Here again probabilistic tools are used to estimate the mixing time.
Often associated with Paul Erdős, who did the pioneering work on the subject, probabilistic combinatorics was traditionally viewed as a set of tools to study problems in other parts of combinatorics. However, with the growth of applications to analyze algorithms in computer science, as well as classical probability, additive number theory, and probabilistic number theory, the area recently grew to become an independent field of combinatorics.
Algebraic Combinatorics
Young diagram of a partition (5,4,1).
Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra. Algebraic combinatorics is continuously expanding its scope, in both topics and techniques, and can be seen as the area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant.
Combinatorics On Words
Construction of a Thue–Morse infinite word.
Combinatorics on words deals with formal languages. It arose independently within several branches of mathematics, including number theory, group theory and probability. It has applications to enumerative combinatorics, fractal analysis, theoretical computer science, automata theory, and linguistics. While many applications are new, the classical Chomsky–Schützenberger hierarchy of classes of formal grammars is perhaps the best-known result in the field.
Geometric Combinatorics
An icosahedron.
Geometric combinatorics is related to convex and discrete geometry, in particular polyhedral combinatorics. It asks, for example, how many faces of each dimension a convex polytope can have. Metric properties of polytopes play an important role as well, e.g. the Cauchy theorem on the rigidity of convex polytopes. Special polytopes are also considered, such as permutohedra, associahedra and Birkhoff polytopes. Combinatorial geometry is an old fashioned name for discrete geometry.
Topological Combinatorics
Splitting a necklace with two cuts.
Combinatorial analogs of concepts and methods in topology are used to study graph coloring, fair division, partitions, partially ordered sets, decision trees, necklace problems and discrete Morse theory. It should not be confused with combinatorial topology which is an older name for algebraic topology.
Arithmetic combinatorics
Arithmetic combinatorics arose out of the interplay between number theory, combinatorics, ergodic theory, and harmonic analysis. It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). Additive number theory (sometimes also called additive combinatorics) refers to the special case when only the operations of addition and subtraction are involved. One important technique in arithmetic combinatorics is the ergodic theory of dynamical systems.
Infinitary Combinatorics
Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. It is a part of set theory, an area of mathematical logic, but uses tools and ideas from both set theory and extremal combinatorics.
Gian-Carlo Rota used the name continuous combinatorics to describe geometric probability, since there are many analogies between counting and measure.
Partition
A partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. (If order matters, the sum becomes a composition.) For example, 4 can be partitioned in five distinct ways: 4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1
What is Permutation?
In mathematics, permutation relates to the act of arranging all the members of a set into some sequence or order. In other words, if the set is already ordered, then the rearranging of its elements is called the process of permuting. Permutations occur, in more or less prominent ways, in almost every area of mathematics. They often arise when different orderings on certain finite sets are considered.
A permutation is the choice of r things from a set of n things without replacement and where the order matters. nPr = (n!) / (n-r)!
What is a Combination?
The combination is a way of selecting items from a collection, such that (unlike permutations) the order of selection does not matter. In smaller cases, it is possible to count the number of combinations. Combination refers to the combination of n things taken k at a time without repetition. To refer to combinations in which repetition is allowed, the terms k-selection or k-combination with repetition are often used. Permutation and Combination Class 11 is one of the important topics which helps in scoring well in Board Exams.
A combination is the choice of r things from a set of n things without replacement and where order does not matter. nCr = n!/(r!(n-r)!)
Burnside's Lemma and Pólya Enumeration Theorem
It is used to count/find combinatorial objects (i.e. equivalence classes or orbits) associated with symmetry groups.
It is a result in group theory that can help when counting objects with symmetry taken into account.
It gives a formula to count objects where two objects that are related by a symmetry (rotation or reflection, for example) are not to be counted as distinct.
Burnside’s Lemma simply states an equation within which if you can find any of the two variables then you can plug them in and solve for the other one.
Burnside's lemma asserts the following: The number of orbits (a natural number or +∞) is equal to the average number of points fixed by an element of G (which is also a natural number or infinity). Let G be a finite group that acts on a set X.
Burnside's lemma allows us to count the number of equivalence classes in sets, based on internal symmetry.
The Pólya enumeration theorem is a generalization of Burnside's lemma which provides a more convenient tool for finding the number of equivalence classes.
Orbit : The coloring's you get when you rotate and reflect the object.
Stabilizer: The rotations and reflections that preserve a given state.
Resource