Meaning of a quote of Doubilet,Rota and Stanley on harmonic analysis and combinatorics - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T05:25:49Z http://mathoverflow.net/feeds/question/111970 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111970/meaning-of-a-quote-of-doubilet-rota-and-stanley-on-harmonic-analysis-and-combinat Meaning of a quote of Doubilet,Rota and Stanley on harmonic analysis and combinatorics Kingsley H.Y. Huang 2012-11-10T07:35:48Z 2012-11-12T17:06:33Z <p>The beginning of the paper On the foundations of combinatorial theory. VI. The idea of generating function (1972) <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.bsmsp/1200514223" rel="nofollow">link text</a> says that </p> <blockquote> <p>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.</p> </blockquote> <p>Would someone explain the meaning of the paragraph in detail, please? Especially, what is </p> <ol> <li><p>"the correspondence",</p></li> <li><p>characteristic functions as continuous analogues of generating functions, and</p></li> <li><p>the "current methods of harmonic analysis"? </p></li> </ol> <p>Since I'm not familiar with harmonic analysis, I also wonder if "more current" methods in this discipline might aid solving combinatorial problems.</p> http://mathoverflow.net/questions/111970/meaning-of-a-quote-of-doubilet-rota-and-stanley-on-harmonic-analysis-and-combinat/111971#111971 Answer by Qiaochu Yuan for Meaning of a quote of Doubilet,Rota and Stanley on harmonic analysis and combinatorics Qiaochu Yuan 2012-11-10T07:50:54Z 2012-11-10T07:50:54Z <ol> <li><p>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.</p></li> <li><p>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})$. </p></li> <li><p>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... </p></li> </ol> http://mathoverflow.net/questions/111970/meaning-of-a-quote-of-doubilet-rota-and-stanley-on-harmonic-analysis-and-combinat/111982#111982 Answer by Tony Huynh for Meaning of a quote of Doubilet,Rota and Stanley on harmonic analysis and combinatorics Tony Huynh 2012-11-10T12:02:30Z 2012-11-10T12:02:30Z <p>Regarding the sentence <em>A unified exposition of their theory, however, is lacking in the literature,</em> I think the theory of <a href="http://en.wikipedia.org/wiki/Combinatorial_species" rel="nofollow">combinatorial species</a> was invented towards this aim. Indeed, combinatorial species were invented by Joyal in 1981 (9 years after <em>On the foundations of combinatorial theory. VI.</em>).</p> <p>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 <a href="https://www.dpmms.cam.ac.uk/~wtg10/2cultures.pdf" rel="nofollow">two cultures</a> 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. </p> http://mathoverflow.net/questions/111970/meaning-of-a-quote-of-doubilet-rota-and-stanley-on-harmonic-analysis-and-combinat/112194#112194 Answer by Patricia Hersh for Meaning of a quote of Doubilet,Rota and Stanley on harmonic analysis and combinatorics Patricia Hersh 2012-11-12T17:06:33Z 2012-11-12T17:06:33Z <p>I guess I'll say something about question 1 beyond my comment above.</p> <p>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.</p> <ol> <li><p>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. </p></li> <li><p>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.</p></li> <li><p>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.</p></li> <li><p>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).</p></li> </ol> <p>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.</p> <p>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: <a href="http://en.wikipedia.org/wiki/Combinatorial_species" rel="nofollow">http://en.wikipedia.org/wiki/Combinatorial_species</a></p> <p>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. </p>