ABSTRACT

Ordinary and exponential generating functions have always been the favorite tool in enumerative combinatorics. Generating functions for set functions offer the same advantages and increase the range of applications. In fact, exponential generating functions operate on set functions, and it is even possible to work with derivatives of set functions. Combinatorial techniques such as the Möbius inversion are then replaced by standard algebraic operations. This chapter describes the basic theory of set functions is fully developed, and provides many applications of it to graph polynomials. It shows that set functions and their generating functions provide short proofs for many classical and new theorems about graph polynomials. Moreover, they can be used for computer calculations. By working recursively with derivations, calculating one single product is often sufficient. Therefore, set functions can provide an efficient way of calculating graph polynomials. More advanced applications of set functions can be found.