Algebraic enumeration

Last updated

Algebraic enumeration is a subfield of enumeration that deals with finding exact formulas for the number of combinatorial objects of a given type, rather than estimating this number asymptotically. Methods of finding these formulas include generating functions and the solution of recurrence relations. [1]

An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration depend on the discipline of study and the context of a given problem.

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.

In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.

Related Research Articles

Algebraic geometry branch of mathematics

Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical problems about these sets of zeros.

Definable real number

Informally, a definable real number is a real number that can be uniquely specified by its description. The description may be expressed as a construction or as a formula of a formal language. For example, the positive square root of 2, , can be defined as the unique positive solution to the equation , and it can be constructed with a compass and straightedge.

Discrete mathematics study of discrete mathematical 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 or Euclidean geometry. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics." Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.

Power set (of any set S) set of all subsets of S, including the empty set and S itself

In mathematics, the power set of any set S is the set of all subsets of S, including the empty set and S itself, variously denoted as P(S), 𝒫(S), ℘(S), P(S), ℙ(S), or, identifying the powerset of S with the set of all functions from S to a given set of two elements, 2S. In axiomatic set theory, the existence of the power set of any set is postulated by the axiom of power set.

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

In mathematics, an algebraic equation or polynomial equation is an equation of the form

This article itemizes the various lists of mathematics topics. Some of these lists link to hundreds of articles; some link only to a few. The template to the right includes links to alphabetical lists of all mathematical articles. This article brings together the same content organized in a manner better suited for browsing.

In algebra, the theory of equations is the study of algebraic equations, which are equations defined by a polynomial. The main problem of the theory of equations was to know when an algebraic equation has an algebraic solution. This problem was completely solved in 1830 by Évariste Galois, by introducing what is now called Galois theory.

Richard P. Stanley American mathematician

Richard Peter Stanley is the Norman Levinson Professor of Applied Mathematics at the Massachusetts Institute of Technology, in Cambridge, Massachusetts. He received his Ph.D. at Harvard University in 1971 under the supervision of Gian-Carlo Rota. He is an expert in the field of combinatorics and its applications to other mathematical disciplines.

Jacques Philippe Marie Binet French mathematician

Jacques Philippe Marie Binet was a French mathematician, physicist and astronomer born in Rennes; he died in Paris, France, in 1856. He made significant contributions to number theory, and the mathematical foundations of matrix algebra which would later lead to important contributions by Cayley and others. In his memoir on the theory of the conjugate axis and of the moment of inertia of bodies he enumerated the principle now known as Binet's theorem. He is also recognized as the first to describe the rule for multiplying matrices in 1812, and Binet's Formula expressing Fibonacci numbers in closed form is named in his honour, although the same result was known to Abraham de Moivre a century earlier.

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.

Logic is the formal science of using reason and is considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and arguments, both through the study of formal systems of inference and the study of arguments in natural language. The scope of logic can therefore be very large, ranging from core topics such as the study of fallacies and paradoxes, to specialized analyses of reasoning such as probability, correct reasoning, and arguments involving causality. One of the aims of logic is to identify the correct and incorrect inferences. Logicians study the criteria for the evaluation of arguments.

In mathematics, a period is a number that can be expressed as an integral of an algebraic function over an algebraic domain. Sums and products of periods remain periods, so the periods form a ring.

Graph enumeration class of combinatorial enumeration problems

In combinatorics, an area of mathematics, graph enumeration describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the graph. These problems may be solved either exactly or asymptotically. The pioneers in this area of mathematics were George Pólya, Arthur Cayley and John Howard Redfield.

In logic, quantification specifies the quantity of specimens in the domain of discourse that satisfy an open formula. The two most common quantifiers mean "for all" and "there exists". For example, in arithmetic, quantifiers allow one to say that the natural numbers go on forever, by writing that for all n, there is another number which is one bigger than n.

Christian Krattenthaler Austrian mathematician

Christian Friedrich Krattenthaler is an Austrian mathematician. He is a professor of discrete mathematics and the Dean of the Faculty of Mathematics at the University of Vienna.

References

  1. Gessel, Ira M.; Stanley, Richard P. (1995), "Algebraic enumeration", Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, pp. 1021–1061, MR   1373677 .