|
Langford Pairing
In combinatorial mathematics, a Langford pairing, also called a Langford sequence, is a permutation of the sequence of 2''n'' numbers 1, 1, 2, 2, ..., ''n'', ''n'' in which the two 1s are one unit apart, the two 2s are two units apart, and more generally the two copies of each number ''k'' are ''k'' units apart. Langford pairings are named after C. Dudley Langford, who posed the problem of constructing them in 1958. Langford's problem is the task of finding Langford pairings for a given value of ''n''. The closely related concept of a Skolem sequence is defined in the same way, but instead permutes the sequence 0, 0, 1, 1, ..., ''n'' − 1, ''n'' − 1. Example A Langford pairing for ''n'' = 3 is given by the sequence 2, 3, 1, 2, 1, 3. Properties Langford pairings exist only when ''n'' is congruent to 0 or 3 modulo 4; for instance, there is no Langford pairing when ''n'' = 1, 2, or 5. The numbers of different Langford pairings for ''n'' = 1, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Langford Pairing
In combinatorial mathematics, a Langford pairing, also called a Langford sequence, is a permutation of the sequence of 2''n'' numbers 1, 1, 2, 2, ..., ''n'', ''n'' in which the two 1s are one unit apart, the two 2s are two units apart, and more generally the two copies of each number ''k'' are ''k'' units apart. Langford pairings are named after C. Dudley Langford, who posed the problem of constructing them in 1958. Langford's problem is the task of finding Langford pairings for a given value of ''n''. The closely related concept of a Skolem sequence is defined in the same way, but instead permutes the sequence 0, 0, 1, 1, ..., ''n'' − 1, ''n'' − 1. Example A Langford pairing for ''n'' = 3 is given by the sequence 2, 3, 1, 2, 1, 3. Properties Langford pairings exist only when ''n'' is congruent to 0 or 3 modulo 4; for instance, there is no Langford pairing when ''n'' = 1, 2, or 5. The numbers of different Langford pairings for ''n'' = 1, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Combinatorics
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 and from evolutionary biology to computer science. Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry, as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ''ad hoc'' solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is gra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set. Permutations differ from combinations, which are selections of some members of a set regardless of order. For example, written as tuples, there are six permutations of the set , namely (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). These are all the possible orderings of this three-element set. Anagrams of words whose letters are different are also permutations: the letters are already ordered in the original word, and the anagram is a reordering of the letters. The study of permutations of finite sets is an important topic in the fields of combinatorics and group theory. Permutations are used in almost every branch of mathematics, and in many other fields of scie ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Modular Arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ''Disquisitiones Arithmeticae'', published in 1801. A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00. Simple addition would result in , but clocks "wrap around" every 12 hours. Because the hour number starts over at zero when it reaches 12, this is arithmetic ''modulo'' 12. In terms of the definition below, 15 is ''congruent'' to 3 modulo 12, so "15:00" on a 24-hour clock is displayed "3:00" on a 12-hour clock. Congruence Given an integer , called a modulus, two integers and are said to be congruent modulo , if is a divisor of their difference (that is, if there is an integer such that ). Congruence modulo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Exact Cover Problem
In the mathematical field of combinatorics, given a collection of subsets of a Set (mathematics), set , an exact cover is a subcollection of such that each element in is contained in ''exactly one'' subset in . In other words, is a partition of a set, partition of consisting of subsets contained in . One says that each element in is covered by exactly one subset in . An exact cover is a kind of cover (topology), cover. In computer science, the exact cover problem is a decision problem to determine if an exact cover exists. The exact cover problem is NP-complete This book is a classic, developing the theory, then cataloguing ''many'' NP-Complete problems. and is one of Karp's 21 NP-complete problems. It is NP-complete even when each subset in contains exactly three elements; this restricted problem is known as exact cover by 3-sets, often abbreviated X3C. The exact cover problem is a kind of constraint satisfaction problem. An exact cover problem can be represented by an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Steiner Triple System
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line. In combinatorial mathematics, a Steiner system (named after Jakob Steiner) is a type of block design, specifically a t-design with λ = 1 and ''t'' = 2 or (recently) ''t'' ≥ 2. A Steiner system with parameters ''t'', ''k'', ''n'', written S(''t'',''k'',''n''), is an ''n''-element set ''S'' together with a set of ''k''-element subsets of ''S'' (called blocks) with the property that each ''t''-element subset of ''S'' is contained in exactly one block. In an alternate notation for block designs, an S(''t'',''k'',''n'') would be a ''t''-(''n'',''k'',1) design. This definition is relatively new. The classical definition of Steiner systems also required that ''k'' = ''t'' + 1. An S(2,3,''n'') was (and still is) called a ''Steiner triple'' (or ''triad'') ''system'', while an S(3,4,''n'') is called a ''Steiner quad ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Multiplication
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division. The result of a multiplication operation is called a ''product''. The multiplication of whole numbers may be thought of as repeated addition; that is, the multiplication of two numbers is equivalent to adding as many copies of one of them, the ''multiplicand'', as the quantity of the other one, the ''multiplier''. Both numbers can be referred to as ''factors''. :a\times b = \underbrace_ For example, 4 multiplied by 3, often written as 3 \times 4 and spoken as "3 times 4", can be calculated by adding 3 copies of 4 together: :3 \times 4 = 4 + 4 + 4 = 12 Here, 3 (the ''multiplier'') and 4 (the ''multiplicand'') are the ''factors'', and 12 is the ''product''. One of the main properties of multiplication is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stirling Permutation
In combinatorial mathematics, a Stirling permutation of order ''k'' is a permutation of the multiset 1, 1, 2, 2, ..., ''k'', ''k'' (with two copies of each value from 1 to ''k'') with the additional property that, for each value ''i'' appearing in the permutation, the values between the two copies of ''i'' are larger than ''i''. For instance, the 15 Stirling permutations of order three are :1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3; :1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1; :1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1; :1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1; :3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1. The number of Stirling permutations of order ''k'' is given by the double factorial (2''k'' − 1)!!. Stirling permutations were introduced by in order to show that certain numbers (the numbers of Stirling permutations with a fixed number of descents) are non-negative. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
The Art Of Computer Programming
''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of computer programming for sequential machines. When Knuth began the project in 1962, he originally conceived of it as a single book with twelve chapters. The first three volumes of what was then expected to be a seven-volume set were published in 1968, 1969, and 1973. Work began in earnest on Volume 4 in 1973, but was suspended in 1977 for work on typesetting prompted by the second edition of Volume 2. Writing of the final copy of Volume 4A began in longhand in 2001, and the first online pre-fascicle, 2A, appeared later in 2001. The first published installment of Volume 4 appeared in paperback as Fascicle 2 in 2005. The hardback Volume 4A, combining Volume 4, Fascicles 0–4, was published in 2011. Volume 4, Fascicle 6 ("Satisfiability") was rel ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete Mathematics (journal)
''Discrete Mathematics'' is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications. It was established in 1971 and is published by North-Holland Publishing Company. It publishes both short notes, full length contributions, as well as survey articles. In addition, the journal publishes a number of special issues each year dedicated to a particular topic. Although originally it published articles in French and German, it now allows only English language articles. The editor-in-chief is Douglas West ( University of Illinois, Urbana). History The journal was established in 1971. The very first article it published was written by Paul Erdős, who went on to publish a total of 84 papers in the journal. Abstracting and indexing The journal is abstracted and indexed in: According to the ''Journal Citation Reports'', the journal has a 2020 impact factor of 0.87. Notable publications * The 1972 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Combinatorics
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 and from evolutionary biology to computer science. Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry, as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ''ad hoc'' solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is gra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
