Huantian Cao

"An Automated System to Calculate Coefficients of Generating Functions"

Abstract:

AutoGF, an automated system to calculate coefficients of generating functions, is developed in this thesis. The algorithms for power series manipulations such as addition, subtraction, multiplication, division, powers, exponentiation, logorithm, reversion and composition are implemented in AutoGF. Maclaurin series provide the basis for calculating the coefficients of basic generating functions. User defined generating functions are also provided for. By writing a text file listing the algebraic steps defining a target generating function, the user of AutoGF can obtain the coefficients of very complicated generating functions.

Exponential generating functions are widely used to count labeled graphs and digraphs. By applying a Hadamard product to the coefficients of exponential generating functions, the exact numbers of labeled graphs or digraphs with different numbers of vertices can be obtained under various restrictions using AutoGF. This is demonstrated for connected graphs, blocks, connected eulerian graphs, acyclic digraphs, strong digraphs, and forests. The time performances of these graphical enumerations are investigated and their time complexities are estimated.

Generating functions can also be applied to count integer partitions. The numbers of all partitions and of partitions into distinct parts are calculated by using AutoGF. The time performances of these partition enumerations are investigated and their time complexities are estimated.