AutoGF : an automated system to calculate coefficients of generating functions

by 1972- Cao, Huantian

AutoGF, an automated system to calculate coefficients of generating functions, is developed in this thesis. The algorithms for power series manipulations such as addition, substraction, 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. Index words: Generating Function, Exponential Generating Function, Power Series, Graph Enumeration, Integer Partitions, Python AutoGF: An Automated System to Calculate Coefficients of Generating Functions by Huantian Cao B.S., China Textile University, China, 1994 M.S., China Textile University, China, 1997 Ph.D., The University of Georgia, 2000 A Thesis Submitted to the Graduate Faculty of The University of Georgia in Partial Fulfillment of the Requirements for the Degree Master of Science Athens, Georgia 2002 c? 2002 Huantian Cao All Rights Reserved AutoGF: An Automated System to Calculate Coefficients of Generating Functions by Huantian Cao Approved: Major Professor: Robert W. Robinson Committee: E. Rodney Canfield David Gries Electronic Version Approved: Gordhan L. Patel Dean of the Graduate School The University of Georgia May 2002