Chen Jia *, Yang Guangchong (Department of Computing Science, Chengdu University of Information Technology, Chengdu, Sichuan 6 10225)

This paper introduces the concept, origin and main research contents of combinatorial mathematics, analyzes the characteristics of combinatorial mathematics, expounds the connection between combinatorial mathematics and computer software, and emphatically illustrates the important application of Ramsey number in computer science information retrieval and packet switching network.

Keywords: combinatorial mathematics; Combinatorial algorithm; Ramsey number;

Information retrieval; Graph classification number in packet-switched networks: O 157

Document ID: A*

Combinatorial mathematics is a comprehensive frontier subject developed with the development of computer science in recent years.

There are many different views about what combinatorial mathematics is. Richard A. Brualdi 5 inductive combinatorics 6 holds that combinatorics is the study of the arrangement of things according to certain rules, which mainly includes the study of existence, counting and known arrangement. In Daniel I. A. Cohen's Five Basic Skills 6 of Combinatorial Theory, it is described as follows: Combinatorial mathematics is to study how many things are described or how many ways something happens. Based on the above viewpoint, combinatorial mathematics is the mathematical problem involved in the main research/arrangement of things.

2 The main content of combinatorics research Compared with traditional mathematics courses, combinatorics studies the mathematical relations between discrete things, including existential problems, counting problems, constructive problems and optimization problems, and its main content is counting and enumerating. Counting problem is the most studied content in combinatorics, which appears in all branches of mathematics. Computer science needs to study algorithms, and it needs to estimate the amount of computation and storage units needed by algorithms, that is, the analysis of time complexity and space complexity of algorithms. The research of combinatorial mathematics mainly includes the following contents [1- 3]: permutation and combination; Generating function and recurrence relation; Exclusion principle and pigeon nest principle; Burnside theorem and p? Lya theorem; Linear programming and so on. 3 Combinatorial Mathematics and Computer Software 3 1 1 Combinatorial Mathematics in the information age Modern mathematics can be divided into two categories: one is the study of continuous objects, such as analysis and equations, and the other is the study of combinatorial mathematics of discrete objects. Computer science is the science of algorithm, the object of computer processing is discrete data, and the science of studying discrete objects is only combinatorial mathematics. Therefore, in the information age today, combinatorial mathematics is the mathematics of the information age. 3 12 Application of Combinatorial Mathematics in Computer Software With the development of computer science, combinatorial mathematics is also developing rapidly, and the theoretical progress of combinatorial mathematics has also promoted the development of computer science. Today, with the unprecedented development of computer software, the corresponding mathematical foundation is needed. Combinatorial mathematics, as the theoretical basis of most computer software design, goes without saying. Combinatorial mathematics is widely used in computers. Computer software is inseparable from the research of various algorithms. In order to measure the efficiency of an algorithm, it is necessary to estimate the number of steps (such as arithmetic operation, binary comparison, program call, etc.). ) to solve the given input (problem) with this algorithm. Therefore, it is necessary to estimate the amount of computation and the number of storage units required by the algorithm, which is the content of the counting problem, and the main research content of combinatorial mathematical analysis is counting.

And enumeration methods and theories.

The Development of Combinatorial Mathematics in Foreign Software Industry Throughout the world, the United States is in an absolute monopoly position. A fundamental reason for this phenomenon is the rapid development of computer science in the United States. Many of the most authoritative people in computer science today come from combinatorial mathematics. The most important computer science departments in the United States (MIT, Princeton, Stanford, Harvard, Yale,,) have first-class combinatorial mathematicians. Combinatorial mathematics has long been a very important subject abroad, and it can even be said to be the basis of computer science. Some big companies, such as IBM, AT & amp； T has the strongest joint research center in the world. The U.S. government has also established the Center for Discrete Mathematics and Theoretical Computer Science, DIMACS (with Princeton University, Rutgers University, AT & amp； T co-founded, located at Rutgers University), the center has always been an important research position of combinatorial mathematics theory computer science. The application of Ramsey number in computer science 4 1 1 Ramsey theorem and Ramsey number are well known. If n+ 1 pigeon flies into n pigeon nests at the same time, at least two pigeons must fly into one pigeon nest. This is the famous pigeon nest principle (also called pigeon hole principle). It is simple and obvious in correctness, but it has a wide range of applications. The principle of pigeon's nest can be summarized as follows: Ramsey theorem set q 1, q2,,, qn; T is a positive integer, and QIET (I = 1, 2, n) has the smallest positive integer R (denoted as r (q 1, q2, q n；; T) makes: For any group of M elements, if mEr puts all T elements of S into N boxes, there is an i (1FiFn) and a q i element, and all T elements are in the ith box. This is called r (q 1, q2, QN; T) is Ramsey number. The above theorem was put forward and proved by Ramsey 1930. When t= 1, Ramsey's theorem is a strengthened pigeon's nest principle, and it is easy to find r (q 1, q2,, qn; 1) = Eni =1qi-n+ 1 Ramsey theorem is an important existence theorem in combinatorics, and its publication has promoted the development of mathematical sciences such as combinatorics, and the study of Ramsey theorem and Ramsey number itself has become an important branch of combinatorics at present) n+1. Ramsey theorem only guarantees the existence of Ramsey number, but does not give an effective method to calculate Ramsey number. At present, the problem of determining Ramsey number is still a big unsolved problem, and it is difficult to find a very small Ramsey number. However, because of its important theoretical value and wide application value, it is very meaningful to determine Ramsey number. The following two examples illustrate the important applications of Ramsey number in computer science fields such as information retrieval and packet-switched network design. 4 12 information retrieval information retrieval is a basic and important problem in computer science. How to organize data and what kind of search method to use have great influence on the efficiency of retrieval. Method of bisection algorithm on the famous ordered list structure is a very effective method, so is method of bisection the best algorithm? Yao [4] gave a positive answer to this question by using Ramsey number. Specifically, suppose a table has n different items whose elements are taken from the key space M={ 1, 2,,, m}, and hope to find a way to store any n-ary subset s of m in the table, so it is easy to answer the following question: Is X in S? The rule of how to store n-ary subsets of m is called table structure or (m, n)- table structure. The simplest table structure is an ordered table structure, which lists the elements in S in ascending order. More generally, it is a table structure sorted by arrangement. The method is to fix an arrangement of {1, 2,,, n} and list the elements in S in the order of arrangement. The computational complexity of information retrieval depends on the table structure and search strategy. The measure of complexity is the number of queries required to determine whether X is in S in the worst case. For example, for an ordered table structure, if method of bisection is used, the number of queries required is [log2( n+ 1)]. Complexity f (m, n) is defined as the minimum complexity under all (m, n)- table structures and search strategies. Regarding f (m, n), Yao [4] proved that the theorem 1 holds for every n, and the existence of N (n) makes f (m, n)=[log2( n+ 1)] hold for everyone (n). According to this theorem, for m large enough, ordered table structure is the most effective information retrieval method.