8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ In addition to the theory of species being a good source for your question 1, so is chapter 5 of Enumerative Combinatorics, Volume 2, by Richard Stanley. $\endgroup$ – Patricia Hersh Nov 10 '12 at 15:27
12
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If you are interested in connections between combinatorics and harmonic analysis in general, whether or not they have to do with generating functions, you could try googling "Kakeya set" or "arithmetic combinatorics" as a couple of starting points. $\endgroup$ – Patricia Hersh Nov 12 '12 at 22:37
6
$\begingroup$
  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...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Yuan, the graded set is quite clear, but the moment generating function is still beyond me. $\endgroup$ – Harry Huang Nov 10 '12 at 8:34
  • $\begingroup$ Regarding your 2nd answer, if you consider instead the continuous case, then 'analog' of the moment generating function is the Laplace transform, which I think has to do with the relation they mean with harmonic analysis. $\endgroup$ – Camilo Sarmiento Nov 12 '12 at 17:24
3
$\begingroup$

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 Gower's warns, the division line is often not so clear cut, but this could be what Doubilet, Rota, and Stanley were alluding to.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Dear Tony, I don't quite get your comments on (3). What I'm trying to ask is, what are the connections between harmonic analysis and combinatorics. $\endgroup$ – Harry Huang Nov 11 '12 at 7:47
  • $\begingroup$ Well, it seems what Tony means is that he doesn't know what Doubilet, Rota, and Stanley meant when they wrote that. Which, if we read your question, seems to be what you were asking. $\endgroup$ – Todd Trimble Dec 20 '19 at 1:08
  • $\begingroup$ 'Gowers' (hence 'Gowers's'), not 'Gower', by the way. $\endgroup$ – LSpice Dec 20 '19 at 4:43
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ pdf = probability density function, not to be confused with the cumulative distribution en.m.wikipedia.org/wiki/Probability_density_function. See a relevant overview in intro of "An umbral setting for cumulants and factorial moments" by E. Di Nardo, D. Senato arxiv.org/abs/math/0412052 $\endgroup$ – Tom Copeland Jan 4 at 20:57
  • $\begingroup$ One could define a formal pdf by, say, taking the inverse Laplace transform of the e.g.f. $e^{-b.t}$. $\endgroup$ – Tom Copeland Jan 20 at 17:34
  • $\begingroup$ For relation to free probability, moments, cumulants, see "Three lectures on free probability" by Novak and LaCroix arxiv.org/abs/1205.2097 (search therein for Rota and Stanley also). $\endgroup$ – Tom Copeland Oct 13 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.