|
This is a list of combinatorics topics, by Wikipedia page. Combinatorics is a branch of mathematics that studies finite collections of objects that satisfy specified criteria. ...
A few decades ago it might have been said that combinatorics is to mathematics roughly what irritable bowel syndrome is to gastroenterology - a way to classify poorly-understood problems, and some standard remedies. Great progress has been made since 1960. Mathematics is the study of quantity, structure, space and change. ...
Gastroenterology or Gastrology might be better described as the field of digestive diseases, which are traditionally separated by anatomic or functional category. ...
This page is complementary to the list of graph theory topics: graph theory being the part of combinatorial mathematics that is most like a separate discipline. In general, combinatorics is as much about problem solving as theory building. This is a list of graph theory topics, by Wikipedia page. ...
A diagram of a graph with 6 vertices and 7 edges. ...
Since combinatorial mathematics is effectively the environment for the study of data structures in computer science, there are very many topics that arise there. The same could be said for other fields, such as error-correcting codes, bioinformatics. A binary tree, a simple type of branching linked data structure. ...
Wikibooks Wikiversity has more about this subject: School of Computer Science Open Directory Project: Computer Science Collection of Computer Science Bibliographies Belief that title science in computer science is inappropriate Categories: Computer science | Academic disciplines ...
In information theory and coding, an error-correcting code or ECC is a code in which each data signal conforms to specific rules of construction so that departures from this construction in the received signal can generally be automatically detected and corrected. ...
Bioinformatics or computational biology is the use of techniques from applied mathematics, informatics, statistics, and computer science to solve biological problems. ...
General combinatorial principles and methods
To begin with, some general principles: In proving results in combinatorics several useful combinatorial rules or combinatorial principles are used. ...
Trial and error is a method for obtaining knowledge, both propositional knowledge and know-how. ...
In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ...
According to the Jargon File, bogosort is the archetypal perversely awful algorithm, one example of which is attempting to sort a deck of cards by repeatedly throwing the deck in the air, picking the cards up at random, and then testing whether the cards are in sorted order. ...
The British Museum algorithm is a general approach to find a solution by checking all possibilities one by one, beginning with the smallest. ...
The pigeonhole principle states that if n pigeons are put into m pigeonholes, and if n > m, then at least one pigeonhole must contain more than one pigeon. ...
In enumerative combinatorial mathematics, identities are sometimes established by arguments that rely on singling out one distinguished element of a set. ...
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence. ...
Recurrent redirects here; for the meaning of recurrent in contemporary hit radio, see Recurrent rotation. ...
In mathematics, telescoping series is an informal expression referring to a series whose sum can be found by exploiting the circumstance that nearly every term cancels with a succeeding or preceding term. ...
In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...
In mathematics, formal power series are devices that make it possible to employ much of the analytical machinery of power series in settings that do not have natural notions of convergence. They are also useful to compactly describe sequences and to find closed formulas for recursively defined sequences; this is...
In combinatorial mathematics and probability theory, the Schrödinger method, named after the Austrian physicist Erwin Schrödinger, is used to solve some problems of distribution and occupancy. ...
In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...
In combinatorial mathematics, Stanleys reciprocity theorem, named after MIT mathematician Richard P. Stanley, states that a certain functional equation is satisfied by the generating function of any rational cone and the generating function of the cones interior. ...
In mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is defined to be the natural number and (Here, for a natural number m, m! denotes the factorial of m. ...
In combinatorics, double counting, also called two-way counting, is a proof technique that involves counting the size of a set in two ways in order to show that the two resulting expressions for the size of the set are equal. ...
A combinatorial proof is a method of proving a statement, usually a combinatorics identity, by counting some carefully chosen object in different ways to obtain different expressions in the statement (see also double counting). ...
In combinatorics, the inclusion-exclusion principle states that if A1, ..., An are finite sets, then where |A| denotes the cardinality of the set A. For example, taking n = 2, we get a special case of double counting: in words, we can count the size of the union of sets A...
The classic Möbius inversion formula was introduced into number theory during the 19th century by August Ferdinand Möbius. ...
Parity is a concept of equality of status or functional equivalence. ...
In mathematics, the permutations of a finite set (i. ...
In order theory, a field of mathematics, a locally finite partially ordered set is one for which every closed interval [a, b] = {x : a ≤ x ≤ b} within it is finite. ...
Greedy algorithm - Wikipedia /**/ @import /skins-1. ...
In computer science, divide and conquer (D&C) is an important algorithm design paradigm. ...
In computer science, the Akra-Bazzi method, or Akra-Bazzi theorem, is used to analyze the asymptotic behavior of the mathematical recurrences that appear in the analysis of divide and conquer algorithms where the sub-problems have substantially different sizes. ...
In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ...
Branch and bound is a general method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. ...
A birthday attack is a type of cryptographic attack which exploits the mathematics behind the birthday paradox, making use of a space_time tradeoff. ...
The birthday paradox states that if there are 23 people in a room then there is a chance of more than 50% that at least two of them will have the same birthday. ...
Floyds cycle-finding algorithm is an algorithm invented by Robert W. Floyd in 1967 which can detect cycles in arbitrary sequences, whether in data structures or generated on the fly, notably including those in graphs and pseudo-random sequences in O(1) space. ...
Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (or linear spaces), linear transformations, and systems of linear equations. ...
In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ...
A weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more of a weight than others. ...
Minimax is a method in decision theory for minimizing the expected maximum loss. ...
Alpha-beta pruning is a technique to reduce the number of nodes evaluated by the minimax algorithm for two-player games. ...
This article is not about probabilistic algorithms, which give the right answer with high probability but not with certainty, nor about Monte Carlo methods, which are simulations relying on pseudo-randomness. ...
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. ...
Analytic combinatorics is a sub-branch of combinatorics that describes combinatorial classes using generating functions, which are often analytic functions, but sometimes formal power series. ...
Symbolic combinatorics is a technique of analytic combinatorics (a sub-branch of combinatorics) that uses symbolic representations of combinatorial classes to derive their generating functions. ...
In combinatorics, a combinatorial class (or simply class) is an equivalence class of sets that have the same counting sequence. ...
In combinatorial mathematics, the exponential formula states that for any formal power series of the form we have where the index π running through the list of all partitions { B1, ..., Bk } of the set { 1, ..., n }. For example, we have because there is one partition of the set { 1, 2...
Problem solving forms part of thinking. ...
Heuristic is the art and science of discovery and invention. ...
This article is about induction in philosophy and logic. ...
George Polyas 1945 book How to Solve It (ISBN 0691080976) is a small volume describing methods of problem-solving. ...
Creative problem solving has been extensively discussed and studied both in popular culture and academically, for example, Michael Ray, one of the authors of The Creative Spirit holds the McJohn G. McCoy-Banc One Corporation Professor of Creativity and Innovation at Stanford University Graduate School of Business. ...
The Art of Problem Solving began as a set of two books coauthored by Richard Rusczyk and Sandor Lehoczky. ...
Some general theories In combinatorial mathematics, a matroid is a structure that captures the essence of a notion of independence that generalizes linear independence in vector spaces. ...
In combinatorics, a greedoid is a type of set system. ...
Ramsey theory, named for Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. ...
Van der Waerdens theorem is a theorem of the branch of mathematics called Ramsey theory. ...
In mathematics, the Hales-Jewett theorem [2] is a fundamental combinatorial result of Ramsey theory, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to be completely random. An informal geometric statement of the theorem is that for any...
In mathematics, before the 1970s, the term umbral calculus was understood to mean the surprising similarities between otherwise unrelated polynomial equations, and certain shadowy techniques that can be used to prove them. ...
Definition In mathematics, a polynomial sequence, i. ...
This article is about a concept in combinatorial mathematics. ...
For information on how large numbers are named in English, see names of large numbers. ...
The standard dictionary numbers Throughout this article, exponential or scientific notation is used. ...
Long scale is the English translation of the French term échelle longue, which designates a system of numeric names in which the word billion means a million millions. ...
In the Western world specific number names for larger numbers did not come into common use until quite recently. ...
Grahams number, named after Ronald Graham, is a very large number which is often described as the largest number that has ever been seriously used in a mathematical proof. ...
In mathematics, Mosers polygon notation is a means of expressing certain extremely large numbers. ...
In number theory, Skewes number is by definition the smallest natural number x for which the comparison π(x) < Li(x) fails; where π(x) is the prime counting function and Li(x) is the offset logarithmic integral. ...
Conway chained arrow notation, created by mathematician John Conway, is a means of expressing certain extremely large numbers. ...
The hyper operators forming the hypern family are as follows: hypern (a, b) = (See Knuths up-arrow notation and Conway chained arrow notation. ...
In mathematics, Knuths up-arrow notation is a notation for very large integers introduced by Donald Knuth in 1976. ...
In mathematics, Mosers polygon notation is a means of expressing certain extremely large numbers. ...
In mathematics, Mosers polygon notation is a means of expressing certain extremely large numbers. ...
In mathematics, a quantity that grows exponentially is one that grows at a rate proportional to its size. ...
In cryptanalysis, a brute force attack on a cipher is a brute-force search of the key space; that is, testing all possible keys, in an attempt to recover the plaintext used to produce a particular ciphertext. ...
In computing, tree data structures, and game theory, the branching factor is the number of children of each node. ...
Granularity is the extent to which a system contains discrete components of ever-smaller size. ...
Curse of dimensionality is a term coined by Richard Bellman applied to the problem caused by the rapid increase in volume associated with adding extra dimensions to a (mathematical) space. ...
In mathematics, concentration of measure is a principle that is applied in measure theory, probability and combinatorics, and has consequences for other fields such as Banach space theory. ...
Topics
0-9 (Redirected from (0,1) matrix) A binary matrix or (0,1)-matrix is a matrix whose entries are all either zero or one. ...
A In mathematics, given a universal set , and , a family of sets over , is an abstract simplicial complex if the following is true: for each , if then for each subset it follows that . ...
In mathematics, an addition chain is a sequence a0, a1, a2, a3, ... that satisfies a0 = 1, and for each k>0: ak = ai + aj for some i, j < k. ...
In mathematics, the Scholz conjecture (sometimes called the Scholz-Brauer conjecture or the Brauer-Scholz conjecture) is a conjecture from 1937 stating that l(2n−1) ≤ n − 1 + l(n) where l(n) is the shortest addition chain producing n. ...
In mathematics, an alternating sign matrix is an square matrix made up of 0s, 1s, and −1s in such a manner than every row and column sums to 1, the nonzero entries of each row, read from left to right, begin with 1 and alternate in sign, the nonzero entries...
In mathematics, two sets are almost disjoint if their intersection is small in some sense. ...
In the mathematical area of order theory, an antichain in a partially ordered set S is a subset A of S such that every pair of members of A is incomparable, i. ...
In geometry and combinatorics, an arrangement of hyperplanes is a finite set A of hyperplanes in a linear, affine, or projective space S. Questions about a hyperplane arrangement A generally concern geometrical, topological, or other properties of the complement, M(A), which is the set that remains when the hyperplanes...
The assignment problem is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. ...
In mathematics, the look and say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... To generate a member of the sequence from the previous member, read off the digits of the previous member, counting the number of digits in groups of...
B Wikipedia encoded in Code 128-B 2D barcode example A barcode (also bar code) is a machine-readable representation of information in a visual format on a surface. ...
A matrix code, also known as a 2D barcode, is a two-dimensional way of representing information. ...
A QR Code is a matrix code (or two-dimensional bar code) created by Japanese corporation Denso-Wave in 1994. ...
The UPC (Universal Product Code) was the original barcode widely used in the United States and Canada for items in stores. ...
In combinatorial mathematics, the Bell polynomials, named in honor of Eric Temple Bell, are given by the sum extending over all sequences j1, j2, j3, ..., jn−k+1 of positive integers such that Combinatorial meaning If the integer n is partitioned into a sum in which 1 appears j1 times...
In combinatorics, Bertrands ballot theorem is the solution to the question: In an election where one candidate receives p votes and the other q votes with p≥q, what is the probability that the first candidate will be strictly ahead of the second candidate throughout the count? The answer...
In mathematics, the binomial theorem is an important formula giving the expansion of powers of sums. ...
You may be looking for block design test In mathematics, a block design in combinatorics is a particular kind of set system, which has some long-standing applications to experimental design, as well as some pure combinatorial aspects. ...
The Boolean satisfiability problem (SAT) is a decision problem considered in complexity theory. ...
2-satisfiability (abbreviated as 2-SAT) is a special case of satisfiability if expressions are written in conjunctive normal form with 2 variables per clause (2-CNF). ...
The Boolean satisfiability problem (SAT) is a decision problem considered in complexity theory. ...
The Bruck-Chowla-Ryser theorem is a result on the combinatorics of block designs. ...
C The Catalan numbers, named after the Belgian mathematician Eugène Charles Catalan (1814—1894), form a sequence of natural numbers that occur in various counting problems in combinatorics. ...
A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, and theoretical biology. ...
Gosper Glider Gun creating gliders. The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. ...
The Collatz conjecture is an unresolved conjecture in mathematics. ...
A combinadic is similar to a factoradic, but used for combinations. ...
In combinatorial mathematics, a combination of members of a set is a subset. ...
Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ...
Combinatorial search is a branch of computer science that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering. ...
Constraint-satisfaction problems or CSPs are mathematical problems where one must find states or objects in a system that satisfy a number of constraints or criteria. ...
In mathematics, a cyclic order on a set X with n elements is an arrangement of X as on a clock face, for an n-hour clock. ...
In mathematics, the cyclotomic identity states that where M is Moreaus necklace-counting function and μ is the classic Möbius function of number theory. ...
D In telecommunication, the term data integrity has the following meanings: The condition that exists when data is unchanged from its source and has not been accidentally or maliciously modified, altered, or destroyed. ...
Alternating bit protocol (ABP) means a simple data link layer network protocol that retransmits lost or corrupted messages. ...
A checksum is a form of redundancy check, a very simple measure for protecting the integrity of data by detecting errors in data that is sent through space (telecommunications) or time (storage). ...
A cyclic redundancy check (CRC) is a type of hash function used to produce a checksum, which is a small number of bits, from a large block of data, such as a packet of network traffic or a block of a computer file, in order to detect errors in transmission...
The Luhn algorithm or Luhn formula, also known as the modulus 10 or mod 10 algorithm, was developed in the 1960s as a method of validating identification numbers. ...
In computer science and information theory, error correction consists of using methods to detect and/or correct errors in the transmission or storage of data by the use of some amount of redundant data and (in the case of transmission) the selective retransmission of incorrect segments of the data. ...
In information theory and coding, an error-detecting code is a code in which each data signal conforms to specific rules of construction so that departures from this construction in the received signal can generally be automatically detected. ...
In telecommunication, an error-detecting system is a system employing an error-detecting code and so arranged that any signal detected as being in error is either deleted from the data delivered to the data sink, in some cases with an indication that such deletion has taken place, or delivered...
In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ...
In telecommunication, a redundancy check is extra data added to a message for the purposes of error detection and error correction. ...
In telecommunication, the term summation check (sum check) has the following meanings: A checksum based on the formation of the sum of the digits of a numeral. ...
In mathematics, a de Bruijn sequence in combinatorics is a cyclic sequence from a given alphabet A of size m, of length N = mn for which every possible subsequence of length n in A is present exactly once. ...
A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, so neither ever does. ...
In computer science, the dining philosophers problem is an illustrative example of a common computing problem in concurrency. ...
Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the concurrent use of un-shareable resources by pieces of computer code called critical sections. ...
The rendezvous dilemma is related to the prisoners dilemma and can be formulated in this way: Two young people have a date in a park they have never been to before. ...
In combinatorics, a derangement is a permutation φ of a set S (i. ...
In mathematics, Dicksons lemma is a finiteness statement applying to n-tuples of natural numbers. ...
In combinatorics, the Dinitz conjecture was a problem on the extension of arrays to partial Latin squares, posed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin. ...
Discrete optimization is a branch of optimization in applied mathematics and computer science. ...
E One of the 12 unique solutions The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queens moves. ...
An entropy encoding is a coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. ...
Enumeration is the name given to the generic field of mathematics which deals with counting objects. ...
Algebraic enumeration is a subfield of enumeration that deals with counting algebraic objects. ...
Combinatorial enumeration is a subfield of enumeration that deals with the counting of objects that have symmetries which are combinatorial in nature. ...
Burnsides lemma, sometimes also called Burnsides counting theorem, Pólyas formula or Cauchy-Frobenius lemma, is a result in group theory which is often useful in taking account of symmetry when counting mathematical objects. ...
In combinatorial mathematics, the Erdős-Ko-Rado theorem of Paul Erdős, Chao Ko, and Richard Rado is the following. ...
The Euler numbers are a sequence En of integers defined by the following Taylor series expansion: (Note that e, the base of the natural logarithm, is also occasionally called Eulers number, as is the Euler characteristic. ...
F // The formula Faà di Brunos formula is an identity in mathematics generalizing the chain rule to higher derivatives, named in honor of Francesco Faà di Bruno (1825–1888), who was (in chronological order) a military officer, a mathematician, and a priest, and was beatified by the Pope a century...
The factorial based radix or factoradic is a factorial based mixed radix numeral scheme: radix: 5! 4! 3! 2! 1! decimal: 120 24 6 2 1 In this numbering system, the rightmost digit may be 0 or 1, the next 0, 1, or 2, and so on. ...
In mathematics, the concept of hypergraph generalizes the notion of a graph. ...
The n-puzzle is known in various versions, including the 8 puzzle, the 15 puzzle, and with various names. ...
A finite geometry is any geometric system that has only a finite number of points. ...
In topology, the finite intersection property is a property of a collection of subsets of a set X. A collection has this property if the intersection over any finite subcollection of the collection is nonempty. ...
G Game theory is a branch of applied mathematics that uses models to study interactions with formalised incentive structures (games). It has applications in a variety of fields, including economics, international relations, evolutionary biology, political science, and military strategy. ...
Combinatorial game theory (CGT) is a mathematical theory that studies a certain kind of game. ...
Combinatorial game theory arose first in relation to the game of nim, which can be solved completely. ...
The teaching of combinatorial game theory normally uses the following examples: Blue-Red Hackenbush -- At the finite level, this partisan combinatorial game allows constructions of games whose values are dyadic rational numbers. ...
Star, written as * or *1, is the value given to the combinatorial game {0 | 0}, where zero is the zero game. ...
In combinatorial game theory, the zero game is the game where neither player has any legal options. ...
This article may be too technical for most readers to understand. ...
Dots and Boxes (also known as Boxes, Squares or Dots) is a pencil and paper game for two players (or sometimes, more than two). ...
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. ...
There are three common mathematical meanings of the term digital sum. ...
Nim is a two-player game of strategy in which players take turns removing objects from heaps, one or more objects at a time but only from a single heap. ...
In mathematics, the proper class of nimbers is introduced in combinatorial game theory. ...
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game is equivalent to a nimber. ...
In combinatorial game theory, a game is partisan or partizan if it is not impartial. ...
A two-player game can be solved on several levels. ...
Col is a pencil and paper game, involving the shading of areas in a line drawing according to the rules of Graph coloring. ...
The word Sim can refer to the following topics: Sim (Pencil Game), a pencil game an abbreviation of the word simulation The Sims, a household simulation computer game by Maxis Dave Sim, author of the comic book Cerebus Sim Wong Hoo, founder of the world-leading entertainment manufacturing company, Creative...
Sprouts is a pencil-and-paper game with interesting mathematical properties. ...
In mathematics, the surreal numbers are a field containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number, and therefore the surreals are algebraically similiar to superreal numbers and hyperreal numbers. ...
In computer chess and other computer games, transposition tables are used to speed up the search of the game tree. ...
The Black Path Game (also known by various other names, such as Brick) is a two-player board game described and analysed in Winning Ways for your Mathematical Plays. ...
Sylver Coinage is a mathematical game for two players, invented by John H. Conway. ...
Golomb coding is a form of entropy coding invented by Solomon W. Golomb that is optimal for alphabets following geometric distributions, that is, when small values are vastly more common than large values. ...
Golomb ruler of order 4 and length 6. ...
An n×n Graeco-Latin square is a table, each cell of which contains a pair of symbols, composed of a symbol from each of two sets of n elements. ...
A Gray code is a binary numeral system where two successive values differ in only one digit, originally designed to prevent spurious output from electromechanical switches. ...
H A Hadamard matrix is a square matrix with entries +1, -1 whose rows are mutually orthogonal. ...
In information theory, the Hamming distance, named after Richard Hamming, is the number of positions in two strings of equal length for which the corresponding elements are different. ...
A hash function is a function that converts an input from a (typically) large domain into an output in a (typically) smaller range (the hash value, often a subset of the integers). ...
Hash collision is a term in computer programming for a situation that occurs when two distinct inputs into a hash function produce identical outputs. ...
Perfect hash functions are hash functions which guarantee O(1) operations complexity when used in a hash table. ...
The hat problem, attributed to Todd Ebert, in his 1998 Ph. ...
In mathematics, the Heilbronn triangle problem is a typical question in the area of irregularities of distribution, within elementary geometry. ...
In combinatorics, a Helly family of order k, named after Eduard Helly (1884 - 1943), is a set system (F, E), with F a collection of subsets of E, that satisfies the k-Helly property. ...
In mathematics, hypergeometric identies are equalities involving sums over hypergeometric terms. ...
In mathematics, a hypergeometric series could in principle be any formal power series in which the ratio of successive coefficients an/an-1 is a rational function of n. ...
In mathematics, the concept of hypergraph generalizes the notion of a graph. ...
I In mathematics, in particular in combinatorics, an incidence structure is a triple where is the set of points, is the set of lines and is the incidence relation. ...
In mathematics, a partition of a positive integer n is a way of writing n as a sum of positive integers. ...
In mathematics, a partition of a positive integer n is a way of writing n as a sum of positive integers. ...
K In mathematics, the Kakeya needle problem asks whether there is a minimum area of a region D in the plane, in which a needle can be turned through 360°. This question was first posed by Soichi Kakeya (1886-1947), a Japanese mathematician who worked mainly in mathematical analysis. ...
The knapsack problem is a problem in combinatorics, complexity theory, cryptography, and applied mathematics. ...
The Kruskal–Katona theorem is a combinatorial theorem about uniform hypergraphs. ...
L In mathematical analysis, the Lagrange inversion theorem, also known as the Lagrange-Bürmann formula, gives the Taylor series expansion of the inverse function of an analytic function. ...
This page is about Lagrange reversion. ...
In mathematics, Lah numbers, discovered by Ivo Lah in 1955 are coefficients expressing rising factorials in terms of falling factorials. ...
For information on how large numbers are named in English, see names of large numbers. ...
A Latin square is an n × n table filled with n different symbols in such a way that each symbol occurs exactly once in each row and exactly once in each column. ...
In information theory, the Levenshtein distance or edit distance between two strings is given by the minimum number of operations needed to transform one string into the other, where an operation is an insertion, deletion, or substitution. ...
In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. ...
In mathematics, the Littlewood-Offord problem is the combinatorial question in geometry of describing usefully the distribution of the subsums made out of vectors v1, v2, ..., vn, taken from a given Euclidean space of fixed dimension d ≥ 1. ...
In combinatorial mathematics, the Lubell-Yamamoto-Meshalkin inequality, more commonly known as the LYM inequality, can be stated as follows. ...
In mathematics, a Lucas chain is a restricted type of addition chain, named for the French mathematician Edouard Lucas. ...
M In mathematics, a magic square of order n is an arrangement of n² numbers in a square, such that the n numbers in all rows, all columns, and both diagonals sum to the same constant. ...
In mathematics, the marriage theorem, usually credited to mathematician Phillip Hall, is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of subsets. ...
In mathematics, a perfect matching for a graph is a matching (a subset of edges without common vertices) which touches all vertices exactly once. ...
In combinatorics, a matroid embedding is a set system (F, E), where F is a collection of feasible sets, that satisfies the following properties: (Accessibility Property) every nonempty feasible set X contains an element x such that X{x} is feasible; (Extensibility Property) for every feasible subset X of a...
In computer science, an m-by-n array of real numbers is a Monge array if for all i, j, k, l such that: and one obtains: So whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersection points, the...
In mathematics, a monomial order is a total order on the set of all monomials (considering monomials which only differ in their coefficient to be the same) satisfying two additional properties. ...
In combinatorial mathematics, Moreaus necklace-counting function where μ is the classic Möbius function, counts the number of necklaces asymmetric under rotation (also called Lyndon words) that can be made by arranging n beads the color of each of which is chosen from a list of α colors. ...
In mathematics, a multiset (sometimes also called a bag) differs from a set in that each member has a multiplicity, which is a natural number indicating (loosely speaking) how many times it is a member, or perhaps how many memberships it has in the multiset. ...
N Moreaus necklace-counting function treats a problem that is not only recreational. ...
In mathematics, a negligible set is a set that is small enough that it can be ignored for some purpose. ...
In mathematics, the phrase almost all has a number of specialised uses. ...
In measure theory (a branch of mathematical analysis), one says that a property holds almost everywhere if the set of elements for which the property does not hold is a null set, i. ...
In measure theory, a null set is a set that it is negligible for the purposes of the measure in question. ...
O In mathematics, an ordered partition O of a set S is a sequence A1, A2, A3, ..., An of subsets of S, with union is S, which are non-empty, and pairwise disjoint. ...
P Packing problems are one area where mathematics meets puzzles (recreational mathematics). ...
The bin packing problem is an NP-complete problem in mathematics. ...
A partition of U into 6 blocks: a Venn diagram representation. ...
In combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of (among other things) its application to the theory free probability. ...
For the hair treatment see Permanent wave. ...
In mathematics, especially in abstract algebra and related areas, a permutation is a bijection, from a finite set X onto itself. ...
In linear algebra, a permutation matrix is a binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere. ...
This article is an elementary introduction to permutations and combinations in combinatorial mathematics. ...
In computer science, the Josephus permutation is defined as follows. ...
The term shuffle can also refer to the act of dragging ones feet on the ground while walking, running, or dancing. ...
In mathematics, the Pochhammer symbol, introduced by Leo August Pochhammer, is used in the theory of special functions to represent the rising factorial or upperfactorial and, confusingly, is used in combinatorics to represent the falling factorial or lower factorial . In the following, the notation of Ronald L. Graham, Donald E...
In recreational mathematics, a polyform is a plane figure constructed by joining together identical basic polygons. ...
In recreational mathematics, a polycube is a polyform with a cube as the base form. ...
The pieces of a Soma cube (with extra coloring) The same puzzle, assembled into a cube The Soma cube is a solid dissection puzzle created by Piet Hein during a lecture on quantum mechanics by Werner Heisenberg. ...
A polyiamond is a counterpart to a polyomino where the polygon used as the building block is an equilateral triangle rather than a square. ...
A polyomino (also called polysquare) is a polyform with the square as its base form. ...
A hexomino is a polyomino of order 6, that is, a polygon in the plane made of 6 equal-sized squares connected edge-to-edge. ...
A pentomino is a geometric shape composed of five (Greek πέντε / pente) identical squares, connected orthogonally. ...
A tetromino, also spelled tetramino or tetrimino, is a geometric shape composed of four squares, connected orthogonally. ...
In mathematics, a projective plane consists of a set of lines and a set of points with the following properties: Given any two distinct points, there is exactly one line incident with both of them. ...
In mathematics, Property B is a certain set theoretic property. ...
In combinatorial mathematics, the Prüfer sequence (or Prüfer code) of a labeled tree is a unique sequence associated with the tree. ...
R Rubiks Cube about to be solved Rubiks Cube is a mechanical puzzle invented by the Hungarian sculptor and professor of architecture Ernő Rubik in 1974. ...
There are many algorithms to solve scrambled Rubiks Cubes. ...
Rubiks Revenge is the 4x4x4 version of Rubiks Cube. ...
S In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem. ...
In computer science, binary search is a search algorithm for searching a set of sorted data for a particular value. ...
Interpolation search parallels how humans search through a telephone book. ...
In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value. ...
Local search is a metaheuristic that is commonly used for solving computationally hard problem such as the traveling salesman problem (TSP). ...
String searching algorithms are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. ...
The Aho-Corasick algorithm is a string searching algorithm discovered by Alfred V. Aho and Margaret J. Corasick. ...
Fuzzy string searching is a technique for finding a string that approximately matches the search string. ...
grep is a command line utility originally written for use with the Unix operating system. ...
Agrep (Approximate grep) is a fuzzy string searching program, developed by Udi Manber and Sun Wu between 1988 and 1991, for use with the Unix operating system. ...
The term wildcard character has the following meanings: Telecommunication In telecommunications, a wildcard character is a character that may be substituted for any of a defined subset of all possible characters. ...
The Knuth-Morris-Pratt string searching algorithm searches for occurrences of a pattern string within a main string by employing the simple observation that when a mismatch occurs, we have enough knowledge simply by possessing the pattern to determine where the next match could begin, thus bypassing re-examination of...
In combinatorial mathematics, the series-parallel networks problem asks for the number of networks that can be formed using a given number of edges. ...
The set cover problem (also set covering) is a classical question in computer science and complexity theory. ...
In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ...
A sparse array in computing is an array where only very few indices are in practice used. ...
In combinatorics, a Sperner family (or Sperner system), named in honor of Emanuel Sperner, is a set system (F, E) in which no element is contained in another. ...
In combinatorial mathematics, Sperners lemma states that every Sperner coloring of a triangulation of an n-dimensional simplex contains a cell colored with a complete set of colors. ...
In mathematics, the Stable Marriage Problem (hereafter: SMP) is as follows: Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women off such that there are...
In mathematics, a Steiner system is a type of block design. ...
Stirling numbers of the first kind In combinatorics, unsigned Stirling numbers of the first kind (with a lower-case s) count the number of permutations of n elements with k disjoint cycles. ...
In combinatorial mathematics, the Stirling transform of a sequence { an : n = 1, 2, 3, ... } of numbers is the sequence { bn : n = 1, 2, 3, ... } given by where is the Stirling number of the second kind, also denoted S(n,k) (with a capital S), which is the number of partitions...
In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ...
In cryptography, a straddling checkerboard is a device for converting an alphabetic plaintext into digits whilst simultaneously achieving fractionation (a simple form of information diffusion) and homophony (a simple method for suppressing peaks of the frequency distribution). ...
In mathematics, a subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without disturbing the relative positions of the remaining elements. ...
The longest-common subsquence problem is the search for an efficient method of finding the longest common subsequence (LCS). ...
Figure 1. ...
The subset sum problem is an important problem in complexity theory and cryptography. ...
In mathematics, the theory of symmetric functions is part of the theory of polynomial equations, and also a substantial chapter of combinatorics. ...
In mathematics, Szemerédis theorem states that a set of natural numbers of density > 0 contains finite arithmetic progressions, of any length k we may ask for. ...
T In mathematics and its applications, the Thue-Morse sequence, or Prouhet-Thue-Morse sequence, is a certain binary sequence whose initial segments alternate (in a certain sense). ...
A model set of the Towers of Hanoi The Tower of Hanoi (also called Towers of Hanoi) is a mathematical game or puzzle. ...
A Turing tarpit is a programming language designed to be Turing-complete while minimizing the number of distinct instructions. ...
U An urn problem is an idealized thought experiment in which some objects of real interest (such as atoms, people, cars, etc. ...
V In combinatorial mathematics, Vandermondes identity, named after Alexandre-Théophile Vandermonde, states that This may be proved by simple algebra relying on the fact that (see factorial) but it also admits a more combinatorics-flavored bijective proof, as follows. ...
W Weighted round robin (WRR) is a best-effort connection scheduling discipline. ...
Deficit round robin (DRR) is a modified weighted round robin scheduling discipline. ...
The Wigner - dEspagnat inequality is a basic result of set theory. ...
Y In mathematics, a Young tableau is a combinatorial object useful in representation theory. ...
Data structure concepts A binary tree, a simple type of branching linked data structure. ...
On computer science, a datatype (often simply type) is a name or label for a set of values and some operations which can be performed on that set of values. ...
Abstract data types or ADTs are a mathematical specification of a set of data and the set of operations that can be performed on the data. ...
In functional programming, new types can be defined, each of which has one or more constructors. ...
In computer science, composite types are datatypes which can be constructed in a programming language out of that languages primitive types and type constructors and other composite types. ...
In computer programming, an array, also known as a vector or list, is one of the simplest data structures. ...
In computing, an associative array, also known as a map, lookup table, or dictionary, is an abstract data type very closely related to the mathematical concept of a function with a finite domain. ...
A deque, or double-ended queue is a data structure which unites the properties of a queue and a stack. ...
In computer science, a list is an abstract concept denoting an ordered collection of fixed-length entities. ...
In computer science, a linked list is one of the fundamental data structures used in computer programming. ...
For queueing people, see queue area. ...
A priority queue is an ADT (abstract data type) supporting the following two operations: add an element to the queue with an associated priority remove the element from the queue that has the highest priority, and return it The simplest way to implement a priority queue data type is to...
A skip list is a probabilistic data structure, based on parallel linked lists, with efficiency comparable to a binary search tree (order O(log n) average time for most operations). ...
A stack is a data structure that works on the principle of Last In First Out (LIFO). ...
In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ...
In computing, garbage collection (also known as GC) is a form of automatic memory management. ...
People Eric Temple Bell (1883 - 1960) was a mathematician born in Scotland who lived in the USA from 1903 until his death. ...
John Horton Conway (born December 26, 1937, Liverpool, England) is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. ...
On Numbers and Games is a mathematics book by John Conway, published by Academic Press Inc in 1976, ISBN 0121863506, and re-released by AK Peters in 2000 (ISBN 1568811276). ...
Winning Ways for your Mathematical Plays (ISBN 1568811306) by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy is a compendium of information on mathematical games. ...
Persi W. Diaconis (born January 31, 1945) is an American mathematician and former professional magician. ...
Paul Erdős Paul Erdős (also Pál Erdős, March 26, 1913 – September 20, 1996) was an immensely prolific and famously eccentric mathematician who, with hundreds of collaborators, worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory and probability theory. ...
The prolific mathematician Paul Erdős and his various collaborators made many famous mathematical conjectures, over a wide field of subjects. ...
This article is being considered for deletion in accordance with Wikipedias deletion policy. ...
Ben Green (born Ben George Christian Green in 1964) was bassist for the industrial/heavy metal band Godflesh. ...
William Timothy Gowers (born November 20, 1963, Wiltshire, United Kingdom) is a British mathematician. ...
Luke Pebody (born 1977) is a mathematician who solved the necklace problem. ...
George Pólya (December 13, 1887 - September 7, 1985, in Hungarian Pólya György) was a mathematician, who was born in Budapest, Hungary and died in Palo Alto, USA. He worked on a great variety of mathematical topics, including series, number theory, combinatorics, and probability. ...
Gian-Carlo Rota (April 27, 1932 – April 18, 1999, known as Juan Carlos Rota to Spanish speakers) was an Italian-born American mathematician and philosopher. ...
Emanuel Sperner (9 December 1905 - 31 January 1980) was a German mathematician, best known for two theorems. ...
Richard P. Stanley (born 1944) is Norman Levinson Professor of Applied Mathematics at the Massachusetts Institute of Technology, in Cambridge, Massachusetts. ...
Endre Szemerédi (born August 21, 1941) is a Hungarian mathematician, working in the field of combinatorics, currently professor at Rutgers University. ...
Terence Tao (陶哲轩, born July 17, 1975, Adelaide, Australia), is a mathematician working primarily on harmonic analysis, partial differential equations, combinatorics, analytic number theory and representation theory. ...
Paul (Pál) Turán (August 28, 1910–September 26, 1976) was a Hungarian mathematician who made contributions in number theory and group theory. ...
Publications Geombinatorics is a mathematical research journal (ISSN 1065-7371) published by the University of Colorado, USA, since 1991 under an international board of editors. ...
See also |
Feeds |
Contact