Some Applications Of The Generating Function In Combinatorial Counting Theory

The combinatorial counting theory is the most fundamental research orientation in combinatorics. It primarily studies the number of the placement ways which satisfy some specific conditions and also the computation problem. The basic principles and methods it uses include: the principle of inclusion and exclusion, the principle of Mobius inversion, Polya theory of counting, the method of generating function and so on. By use of the basic and widely applicable method of all the above methods-the method of generating function, the Lucas number and the Stirling numbers are studied in this paper, which play an important role in the combinatorial counting theory.The main results obtained in this thesis can be summarized as follows:Chapter 1 of this dissertation is devoted to introducing the two primary research objects of this paper: the Lucas number and the Stirling number. Their origin, definition, basic properties and the research situation are introduced.Chapter 2 introduces thoroughly the main method used in this paper: the generating function. By means of the point of abstract algebra, the generating function is defined as formal power series. And all the formal power series can form an integral domain after introducing a kind of addition and mutiplication of the formal power series. These give a rigorous theoretical basis to the four arithmetic operations of the generating function. In the end we display vividly some concrete applications of this method by illustration.In chapter 3 we apply the idea of generating function to the study of the generalized Lucas number. By means of various known generating functions of some sequences, some identities involving the squares and the cubics of this number are gotten. In addtion, by use of the obtained identities we give some congruence relations of the Lucas number.Chapter 4 is arranged as follows. At first we extend the two kinds of ordinary Stirling numbers from the combinatorial angle. According to the combinatorial sense of the generalized Stirling numbers , some basic recurrences they satisfy are given. Then we obtain all kinds of generating function of these numbers and study their basic properties. In the end many results related the generalized Stirling numbers are derived. Take the " triangle " recurrence, the " vertical " recurrence and the congruence property for example.