The Application Of Probabilistic Methods In Combinatorics

The probabilistic method is a powerful tool for tackling many problems in discrete mathematics, especially in combinatorics. This method is roughly divided into tow types: one is the noconstructive method; the other is the constructive method. The noconstructive method is useful for establishing the existence of combinatorial structures with certain properties. With constructive method, many combinatorial numbers are represented to moments of some random variables.This thesis, which is divided into three parts, is concerned with the application of probabilistic methods in combinatorial numbers and random graph.In chapter 1, the author simply introduces the history and development of probabilistic methods in combinatorics, and then naturally brings up the problems investigated on. Meanwhile, some preliminary knowledge is introduced.In chapter 2, the author studies the noconstructive method which includes the basic probabilistic method and the linearity of expectation.The chapter 3 investigates the constructive method which means that many combinatorial numbers, such as Stirling number, Bell number, harmonic number, Fibonacci number and the number of derangement, are represented to moments of some random variables. This method is used in the computation of combinatorial sums, discovery and proof of combinatorial identities. The author mainly studies the probabilistic representation of a special combinatorial number. Meanwhile, some special values of both kinds of Stirling numbers are obtained. Some new recurrence formulas and identities related to both kinds of Stirling numbers are found.