Question

The beginning of the paper On the foundations of combinatorial theory. VI. The idea of generating function (1972) link text says that

Since Laplace discovered the remarkable correspondence between set theoretic operations and operations on formal power series, and put it to use with great success to solve variety of combinatorial problems, generating functions (and their continuous analogues, namely, characteristic functions) have become essential probabilistic and combinatorial technique. A unified exposition of their theory, however, is lacking in the literature. This is not surprising, in view of the fact that all too often generating functions have been considered to be simply an application of the current methods of harmonic analysis.

Would someone explain the meaning of the paragraph in detail, please? Especially, what is

1. "the correspondence",

2. characteristic functions as continuous analogues of generating functions, and

3. the "current methods of harmonic analysis"?

Since I'm not familiar with harmonic analysis, I also wonder if "more current" methods in this discipline might aid solving combinatorial problems.

Answer 1

I guess I'll say something about question 1 beyond my comment above.

Below are a few points I took away from a graduate class on generating functions taught by Stanley and from an undergraduate class taught by Nantel Bergeron, the latter of which discussed André Joyal's theory of species for a few weeks. Clearly there are other MO users with more expertise on this than me, and they should feel free to edit my post if they are so inclined.

1. Exponential generating functions $\sum_{n\ge 0} a_n \frac{x^n}{n!}$ are handy for enumeration problems involving labeled objects, while ordinary generating functions $\sum_{n\ge 0} b_n x^n$ are more convenient for unlabeled objects. As an example, exponential generating functions work well for problems involving set partitions, i.e. ways of splitting a set $\{ 1,\dots ,n \} $ of distinguishable objects into blocks, while ordinary generating functions tend to work better for enumeration problems regarding integers partitions.

2. The operation of taking the derivative of a generating function $\sum_{n\ge 0} a_n \frac{x^n}{n!}$ and then multiplying by $x$ corresponds naturally to switching from having coefficients $a_n$ counting unmarked objects of size $n$ to a new generating function whose corresponding coefficient $na_n$ counts marked objects of size $n$. For instance, if $a_n$ counted committees of size $n$, then $na_n$ would count committees with a choice of chairperson.

3. Multiplying generating functions $\sum_{r\ge 0}a_r x^r$ and $\sum_{s\ge 0}b_s x^s$ corresponds to switching from having coefficients $a_r,b_s$ respectively counting objects of size $r,s$ in sets $A$ and $B$ to now letting the coefficient of $x^{r+s}$ in the product count the ordered pairs in $A\times B$ whose orders sum to $r+s$. While I wrote this for ordinary generating functions, there is also an analogous version for exponential generating functions where binomial coefficients do just what you would hope.

4. A consequence of 3 is that exponentiating an exponential generating function $F(x)$ to get $e^{F(x)}$ corresponds to switching from counting objects of size $n$ to counting collections of these objects where the orders of the elements in the collection sum to $n$. A concrete example is where the cofficients in $F(x)$ count permutations comprised of a single cycle of size $n$, whereas the coefficients in $e^{F(x)}$ count all permutations of size $n$ (having any number of cycles).

The various books, etc., written in the 40 years since that quote do quite a lot to systematize things. For instance, there is Enumerative Combinatorics, Volume 2, by Richard Stanley.

Regarding species, one thing I liked was that there were very nice diagrams people drew to depict operations such as above which were actually helpful for deducing combinatorial identities (as I recall). One or two of these pictures appear at: http://en.wikipedia.org/wiki/Combinatorial_species

Our discussion of species in the class of Bergeron was prefaced by a quote from our professor which I liked very much: that undergraduate classes deal primarily with categories while graduate classes deal mainly with functors. I think he said this to help prepare us for facing a functor.

Answer 2

Regarding the sentence A unified exposition of their theory, however, is lacking in the literature, I think the theory of combinatorial species was invented towards this aim. Indeed, combinatorial species were invented by Joyal in 1981 (9 years after On the foundations of combinatorial theory. VI.).

Regarding (3), I also have no idea what it means. I will however throw out the possibility that this could be another instance of Gower's two cultures phenomenon in mathematics. That is, there are the people who use generating functions as mainly a tool to solve problmes (I would classify myself into this group). And there are others who now study them as a theory in their own right, but those people didn't exist in 1972. Of course, as Gower's warns, the division line is often not so clear cut, but this could be what Doubilet, Rota, and Stanley were alluding to.

Answer 3

1. You can think of formal power series in one variable with non-negative integer coefficients as describing a notion of cardinality for "graded sets," namely sets $X$ equipped with a decomposition as the disjoint union $\bigsqcup X_n$ of finite subsets of $X$ consisting of the elements of "weight $n$." Equivalently, sets equipped with a function $X \to \mathbb{Z}_{\ge 0}$, usually some combinatorial parameter, with finite fibers. Graded sets admit a "graded disjoint union" and "graded product" which correspond to adding and multiplying formal power series.

2. If $X$ is a discrete random variable with $\mathbb{P}(X = k) = p_k$, the probability generating function $\sum p_k z^k$ can be written $\mathbb{E}(z^X)$. If you wanted to generalize this definition to continuous random variables it would be convenient to write $z = e^t$, which gives the moment generating function $\mathbb{E}(e^{tX})$.

3. I have no idea what this means. My notion of what generating functions are all about is inherited from things Rota and Stanley wrote, so I was never exposed to whatever viewpoint they are trying to refute...