Analytic combinatorics is a fascinating branch of mathematics with astonishing results (for the novice), e.g. that the number $a_n$ of distinct rooted binary trees with exactly $n$ branching nodes is the coefficient $c_n$ of the expansion of the function

$$c(z) = \frac{1- \sqrt{1 - 4z}}{2z}$$

which happens to be the Catalan number $C_n$.

Very roughly stated, the typical problem in analytic combinatorics is: Given a combinatorial species out of a family of species $S$, find a analytic function $f(z)$ (its generating function) in a family of functions $F$ such that the coefficients $c_n$ of $f$'s expansion give the numbers $a_n$ of (finite) members of the species characterized by $n$.

I assume that $S$ and $F$ can be (and usually are) chosen such that for all (at least sufficiently gentle) combinatorial species $s \in S$ there is a function $f \in F$, such that $f$ is the generating function of $s$.

My question is: Is there an example of natural families $S$ and $F$ with a significant amount of (sufficiently gentle) functions $f$ (ideally all) such that there is an $s \in S$ which $f$ is the generating function of?

Or are there heuristic arguments that for all natural families $S$ and $F$ for possibly almost all $f \in F$ there is no combinatorial species $s \in S$ which $f$ is the generating function of?

(A natural family $F$ should not be a super-family $F'$ with all non-generating functions excluded.)


Your Answer

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

Browse other questions tagged or ask your own question.