At the same time, people have a profound understanding and research on numbers. In the process of the formation and development of various mathematical branches closely related to shapes, such as geometry, topology and category theory, the diversity of numbers and shapes is gradually discovered from the diversity of shapes, and various skills of numbers and shapes are produced. Modern set theory and mathematical logic reflect the potential combination of number and shape. However, modern algebraic topology and algebraic geometry closely link numbers with shapes. All these have had and will continue to have a far-reaching impact on the formation and development of modern combinatorics centered on digital skills.
From this point of view, combinatorics is closely related to other branches of mathematics. Some of its research contents and methods come from various branches and are also applied to various branches. Of course, combinatorics, like other branches of mathematics, has its own unique research problems and methods, which stem from people's discovery and understanding of numbers, shapes and their relationships in the objective world. For example, in the Book of Changes in ancient China, the period of 60 years was recorded by ten heavenly stems and twelve earthly branches, and the Rubik's Cube was recorded in the river map of Luoshu, which was the earliest combination problem and even architectural contextualism.
During the two centuries of 1 1 and 12, Jia Xian discovered the binomial coefficient, which Yang Hui recorded in his book "The Law of Continuing Ancient Confusion". This is what China usually calls Yang Hui Triangle. In fact, in the12nd century, this combination number was also discovered by the second Bashgalo in India. This triangle was taught by Persian philosophers in the13rd century. In the west, Blaise Pascal discovered this triangle in the middle of17th century. This triangle is also widely used in other branches of mathematics. At the same time, Pascal and Fermat both found many results of classical combinatorics related to probability theory. Therefore, westerners believe that combinatorics began in17th century. The word combinatorics was first applied in the mathematical sense by the German mathematician Leibniz. Perhaps, at that time, he had a premonition that it would flourish in the future. However, it was not until the Euler era in the18th century that combinatorics began to develop as a science, because at that time, he solved the problem of the Seven Bridges in Konigsberg and discovered the simple relationship between the number of vertices, the number of edges and the number of faces of a polyhedron (first of all, in the case of a convex polyhedron, that is, the plan), which is the Euler formula. Even the creator of the Hamiltonian circle that people say today should be Euler. All these make Euler not only an important part of combinatorics-graph theory, but also a pioneer in the development of topology, occupying the center of modern mathematics stage. At the same time, his conjecture about the Latin square in combinatorial design, another important part of combinatorics, is called Euler conjecture, which was not completely solved until 1959.
/kloc-At the beginning of the 9th century, the combination coefficient proposed by Gauss, now called Gauss coefficient, also plays an important role in classical combinatorics. At the same time, he also studied the intersection of closed curves on the plane, and the conjecture put forward from this was called Gaussian conjecture, which was not solved until the 20 th century. This problem not only contributes to topology, but also contributes to the development of graph theory in combinatorics. /kloc-In the 9th century, a branch of Boolean algebra, which was discovered by george boole, has become the cornerstone of the order theory in combinatorics. Of course, during this period, people have also studied many other combination problems, most of which are entertaining.
At the beginning of the 20th century, Poincare developed the concept and method of combinatorics by combining polyhedron problems, which made modern topology develop from combinatorial topology to algebraic topology. In the middle and late 20th century, the rapid development of combinatorics may be unexpected. First of all, in 1920, Fisher (R.A) and Yates (F F.) developed the statistical theory of experimental design, which led to the formation and development of information theory, especially coding theory. 1939, kantorovich (канн) in 1947, Dantzig (G.B) gave a general linear programming model and theory, and his simplex method laid the foundation of this theory, and expounded the combination of its solution sets. Until today, it is still one of the most widely used mathematical methods. These have led to the formation and development of a series of problems in operational research represented by network flow. It opens up a new branch of combinatorics, which is called combinatorial optimization at present. In 1950s, China also discovered and solved a graph operation method called linear programming of transportation problems, which is similar to the general network flow theory. On this basis, the internationally renowned Chinese postman problem has emerged.
On the other hand, since 1940, Tutte (W.T), who was born in England, has made a series of achievements on graph theory in solving puzzles, which not only opened up many new research fields in the development of graph theory, but also played a core role in the development of matroid theory and combinatorial geometry proposed by Whitney (H H.) in the 1930s. It is particularly worth mentioning that during this period, with the development of electronic technology and computer science, the potential power of combinatorics has become increasingly apparent. At the same time, it also puts forward many new research topics for the development of combinatorics. For example, computer-aided design centered on large-scale and ultra-large-scale integrated circuit design has raised endless problems. The research and development of some of these problems are forming a new geometry, which is combinatorial computational geometry. Regarding the complexity of the algorithm, since Cook (S.A) put forward NP-complete theory in 196 1, this idea has penetrated into all branches of combinatorics, even some branches of mathematics and computer science.
In the past 20 years, some challenging problems have been solved by combinatorics, even in the whole field of mathematics. For example, in 1926, B.L. proposed the proof of the product sum conjecture of double random matrices; Heawood (,P.J.) proposed a solution to the coloring conjecture of curved graphs in 1890; Computer verification of the famous four-color theorem and discovery of new combinatorial invariants for kink problems. In mathematics, interdisciplinary subjects closely related to combinatorics, such as combinatorial topology, combinatorial geometry, combinatorial number theory, combinatorial matrix theory and combinatorial group theory, have been or are being formed. In addition, combinatorics is also infiltrating into all aspects of other natural and social sciences, such as physics, mechanics, chemistry, biology, genetics, psychology, economics, management and even politics.
According to the research and development status of combinatorics, it can be divided into the following five branches: classical combinatorics, combinatorial design, combinatorial order, graphs and hypergraphs, combinatorial polyhedron and optimization. Because combinatorics involves almost all branches of mathematics, it may be as impossible to establish a unified theory as mathematics itself. However, how to establish some unified theories on the basis of the above five branches, or form some new branches of mathematics independently from combinatorics, will be of great significance to the 20th century. Among contemporary mathematicians in China, Hua, Wu Wenjun, Ke Zhao, Wan Zhexian, Lu Jiaxi and others have made early contributions in different fields of combinatorics. Among them, the systematic work of Wan Zhexian and his research group in finite geometry not only has an impact on combinatorial design but also on the study of graphic symmetry. Lu Jiaxi's series of articles on disjoint Steiner triple sets not only solved a difficult problem in combinatorial design, but also the methods he created were useful to later researchers.
In 1772, the French mathematician Vandermonde, (A.-T.) used [n]p to express the number of permutations in which p is taken from n different elements at a time.
Euler (L.), a Swiss mathematician, used 177 1 and 1778 to represent the combination number of p elements of n different elements.
1830, the British mathematician peacock (g) introduced the symbol Cr to represent the number of r in a combination of n elements.
1869 or earlier, Goodwin of Cambridge used the symbol nPr to indicate the arrangement number of R elements taken out of N elements at a time, and this usage has continued to this day. According to this method, nPn is equivalent to n! .
1872, German mathematician B. A. von introduced the symbol (np) to express the same meaning, and this combination of symbols (combined symbols) has been used to this day.
In 1880, Potts (R R.) indicates the number of combinations and permutations of R from n elements by nCr and nPr respectively.
In 1886, Whit-worth (A.W) uses Cnr and Pnr to represent the same meaning, and he also uses Rnr to represent the number of repeatable combinations.
1899, British mathematician and physicist Chrystal, G. used nPr and nCr to indicate the number of permutations and combinations of R non-repeating elements taken from N different elements at a time, and nHr to indicate the number of repeatable permutations in the same sense. These three symbols are still widely used today.
1904, German mathematician Neto (E.) wrote an encyclopedia dictionary, in which Arn stands for the above-mentioned nPr, Crn stands for the above-mentioned nCr, and the latter is also represented by the symbol (n r). These symbols are also used in modern times.
In addition, in gossip, it is also applied to permutation and combination.