Rubina Parvin: Generating functions and their applications to counting

Abstract

This thesis investigates generating functions and their applications in combinatorial enumeration, emphasizing how these tools simplify the process of counting complex, structured objects. It provides a clear introduction to ordinary, exponential, and Dirichlet generating functions, explaining their definitions, uses, and connections to problems in combinatorics, analysis, and number theory.

The thesis examines how algebraic operations on exponential generating functions correspond to fundamental combinatorial constructions, such as combining, partitioning, and relabeling labeled sets. It also demonstrates how generating functions can be used to solve recurrence relations, using the Catalan numbers as a key example.

A major focus is the Exponential Formula, which relates the generating functions of connected components to the generating function of the total structure they form. Through the framework of cards, decks, and hands, this result is illustrated with applications to permutations and labeled graphs. Overall, the thesis presents generating functions as powerful and unifying tools in modern combinatorics.