1
$\begingroup$

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

$\endgroup$

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.