Meaning of a quote of Doubilet, Rota and Stanley on harmonic analysis and combinatorics

Question

The beginning of the paper On the foundations of combinatorial theory. VI. The idea of generating function (1972) 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 a variety of combinatorial problems, generating functions (and their continuous analogues, namely, characteristic functions) have become an 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

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...

Answer 3

These two papers answer your question in the introductory paragraphs:

1. Norbert Wiener's "The historical background of harmonic analysis"

and

2. G. Mackey's "Harmonic analysis as the exploitation of symmetry--a historical survey".

The characteristic-function approach still abounds in generating series related to combinatorics in the umbral calculus / Sheffer sequences / finite operator calculus of Rota et al., where one might define the umbral variables as moments of distributions, defined by characteristic functions, and, of course, in quantum field theory and statistical mechanics with their diverse partition functions and cumulant-moment expansion theorems and associated enumerative diagrammatics, incuding Feynman diagrams, (cf. OEIS A036040 and A127671). E.g., the Laplace transform version gives \begin{gather*} (b_\cdot)^n = b_n = (-1)^n\left.\frac{d^n}{dt^n}\langle\exp(-tx)\rangle\right|_{t=0} \\ = (-1)^n\left.\frac{d^n}{dt^n} \int_0^\infty \exp(-tx)\operatorname{pdf}(x) dx\right|_{t=0} \\ = \int_0^\infty x^n\operatorname{pdf}(x) dx = \langle x^n\rangle, \end{gather*} where the characteristic function for the probability distribution function $\operatorname{pdf}(x)$ is

$$\langle\exp(-tx)\rangle = \int_0^\infty \exp(-tx)\operatorname{pdf}(x) dx .$$

There is an analogous Fourier transform characteristic function

$$\langle\exp(ixt)\rangle.$$

The gaussian distribution and the central limit theorem are key historical focal points in this appoach to probability theory, which is rife with enumerative combinatorics.

More recently, free probability theory employs the Cauchy transform to define characteristic functions for the generating functions of free moments, related to noncrossing partitions, parking functions, random matrices and the Wigner semicircular distribution—the counterpart to the gaussian distribution (cf. "A Simple Introduction to Free Probability Theory and Its Application to Random Matrices" by Xiang-Gen Xia, and A134264.)

---

---

(Update 4/1/2021) A walkthrough

First, for the correspondence, see the simple examples in this excerpt ("History of Probability (Part 5) – Laplace (1749-1827)" by Bob Rosenfeld, cf. blogpost by David Giles) of Laplace's use of generating functions (originating with Euler, but a phrase Laplace coined) to encode information on combinatorics ("putting balls in urns" as Rota once put it) and associated probabilities. A more sophisticated example is given by Ulrich in Quora. These generating functions were often generated from difference (recurrence) or differential equations or a mix thereof.

Note that Euler's integral rep for the Euler beta function is in the denominator of the ratio in Problem I of the excerpt and in this case is a convolution of probabilities (some refs state Laplace did not use convolutions). Now read Wiener's survey of the history of harmonic analysis up to the end of the second paragraph of page 59, in which convolution, or Faltung, is stressed. For another perspective on Laplace and probability generating functions, read up to page 551 of Mackey's survey.

Now jump to Loeb's "The world of generating functions and umbral calculus" and read in the section summarizing DR&S:

Thus, Doubilet, Rota, and Stanley have accomplished a tour de force —presenting a unified treatment of all known types of generating functions, and justifying our expectations as to what new types are yet to be found. [Stanley 1986] “The explanatory paradigm based on incidence algebras is this: connected with each special algebraic operator on a ‘variety’ of generating functions is a family of partially ordered sets.. . . The fundamental operation of convolution in the incidence algebra reflect the algebraic operator in question on generating functions. In this way, the particular algebraic operation acquires a combinatorial interpretation.”

Rota had two careers--first in probability theory and associated operators, second in the umbral / finite operator / Sheffer polynomial calculus and associated combinatorics. Di Nardo nicely summarizes the co-evolution of these two passions of Rota in "Symbolic calculus in mathematical statistics: A review."

(Joseph Kung in "Gian Carlo Rota: A biographical memoir" gives a broader sketch of Rota's interests and contributions, dividing his work into three periods.)

Edit 10/10/21: (Start)

From "Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups" by Armstrong

It is an observation of Rota from the 1960’s that the classical convolution of random variables is — in some sense — the same as Möbius inversion on the lattice of set partitions. Speicher proved an analogous result in a different setting: he showed that by restricting attention to the lattice of noncrossing set partitions, one obtains Voiculescu’s free convolution of random variables.

And from Möbius Inversion for Categories by Leinster:

In the mid-20th century, Möbius inversion (nLab) was generalized to arbitrary posets. Several people came up with this idea, but it’s usually associated with the name of Gian-Carlo Rota, who demonstrated its importance in enumerative combinatorics.

That the associations among probability calculus and enumerative combinatorics were constantly in Rota's thinking is further supported by a tangential comment in his preface to "Combinatorial Species and Tree-like Structures" by Joyal:

Species are related to generating functions in much the same way as random variables are related to probability distributions.

(End)

Answer 4

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 Gowers's two cultures phenomenon in mathematics. That is, there are the people who use generating functions as mainly a tool to solve problems (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 Gowers warns, the division line is often not so clear cut, but this could be what Doubilet, Rota, and Stanley were alluding to.