Generating Functions

Roughly speaking, a generating function is a polynomial in one or more variables (in expanded form), whose exponents are real numbers and whose coefficients are the numbers we are seeking. Generating functions are widely used in probability theory ([7], [8], or [9]) and combinatorics [10]. In this article we use the word "polynomial" in a nonstandard sense. Usually polynomials have integer exponents only. Because Mathematica works well with this kind of "generalized polynomials," we use them instead.

For instance, if Stat is a discrete statistic with possible values , its generating function is defined as

where the argument plays only an auxiliary role. Thus, if Stat is a binomial distributed with parameters and , we have

The generating function of a discrete statistic Stat contains all the information about its distribution. Given the generating function, it is thus possible to calculate (as well as plot or tabulate)

of Stat (the letter "G" in the name of these functions indicates that we base our calculations on the generating function of Stat). The following easy and relatively fast procedures are useful in this context:

Now we give an example of an application of generating functions in combinatorics. For instance, if we divide numbered balls randomly among urns and denote by the number of cases that balls come into urn balls come into urn , then the generating function of these numbers is defined as

where the arguments again play only an auxiliary role.