Counting Theory Of S～((n))-factors And Applications

In this thesis, the author gives a series of counting formulas about Sⁿ-factors. by means of methods of analyzing components of graphs and combinatorial enumerations (see Chapter 1, Chapter 2, Chapter 3 and Chapter 4). By using of the counting formulas and methods and ideas of combinatorics, the author gives the explicit formulas of the mean colour numbers of classes of graphs and characterization for the mean colour number μ(G) of any graphs. The author proposes the concept of associated numbers (see Chapter 6). By mechanical method of proving, the author gives its generating function, and does a series of research about the associated numbers and gets some of combinatorial identities. These combinatorial identities are related to a great deal of numbers, for examples, Pell number, Lucas number, Fibonacci number, the two kinds of Stirling numbers and two kinds of Chebyshev polynomials.In the thesis, main results are as follows :1. For a regular m-furcating tree, a recurrence formula of the number of all its Sⁿ -factors is obtained by analyzing the relation among t, t and m of sub-furcating trees and by adopting methods of components of graphs (see Chapter 1). Specially, m = 2, the recurrence formula of a regular binary tree is obtained. Recurrences of regular m-furcating trees have a number of usages in computer and combinatorial words (or code).2. By using of formulas of convolutions, the author obtains the counting formulas and combinatorial identities of complete i-partite graphs (see Chapter 2). Moreover, the author obtains some combinatorial identities by the formulas of convolutions of N(G|-, k).3. By analyzing components of graphs and enumerative techniques, the author obtains the explicit formula of the chromatic polynomials of graphs, specially, presents the explicit formula of the chromatic polynomials of complete t-partite graph related to the Stirling numbers S(n, k) of the second kind.4. The author derives the relation formulas between the numbers of Sⁿ -factors and coefficients of the chromatic polynomials (see Chapter 4), and shows explicit formulas of a number of graphs, for examples, n — 3-regular graphs, special complementary tree T of any tree T. So that these provide new ways for solving the mean colour numbers (defined by Bartels and Welsh, 1995).5. The author proposes a concept of associated numbers (see Chapter 6), gives the generating functions by mechanized method, and discusses combinatorial formulas on associated numbers, finally, obtained a number of combinatorial identities related to Pell numbers, Fibonacci numbers and Chebyshev polynomials.6. Based on computing technique of combinatorics, the representing formula of difference operator of N(G|-,k) is derived (see Chapter 7). By analyzing components of graphs and the representing formulas of the numbers of Sⁿ-factors, the author gives a great deal of classical...