14
$\begingroup$

Yesterday I asked the question Why should a combinatorialist know category theory?, where Chris Taylor suggested me to have a look at combinatorial species. I had heard the term before but I haven't read more about it that than its entry on Wikipedia. To me it looks essentially like analytic combinatorics dressed in the language of categories. Is this correct? Can we do things with species that are impossible with analytic combinatorics (or vice versa)?

$\endgroup$
10
$\begingroup$

Analytic combinatorics tells you how to extract useful information from a generating function. The theory of combinatorial species is, among other things, an elegant way of writing down generating functions from a description of a combinatorial problem. So the two are complementary.

I recommend Bergeron, Labelle, and Leroux's Combinatorial Species and Tree-like Structures to really get a feel for the latter.

$\endgroup$
  • $\begingroup$ Thanks, I will have a look at it! In the preface it says "The only prerequisites are a good knowledge of basic algebra and analysis and some familiarity with discrete mathematics." Does this mean that I can learn the category theory needed as I go? Or is category theory included in "a good knowledge of basic algebra"? $\endgroup$ – Carolus Apr 6 '13 at 6:21
  • 2
    $\begingroup$ You don't really need to know any category theory as such. $\endgroup$ – Qiaochu Yuan Apr 6 '13 at 6:32
6
$\begingroup$

Analytic combinatorics uses generating functions that are power series of functions analytic in some region. The location of singularities and the residues or asymptotic behavior near the singularities are used to treat the asymptotics of the coefficients. These are non-formal calculations that cannot be done in any direct way with formal power series.

Species is an enriched version of the completely formal use of exponential generating functions. It is not necessary for the series to converge anywhere. Very roughly, it is finite counting, but keeping track of automorphisms or other "structure".

$\endgroup$
5
$\begingroup$

I would offer the following difference between the two.

Species theory offers an extremely formal framework to define a combinatorial class. It is powerful enough to address the question of when does a specification makes sense(*), which analytic combinatorics does not. It is a context in which one can model many analytic phenomena combinatorially, (esp. differential equations) and address meta question like how many combinatorial classes exist. It is a step beyond Polya enumeration, and as such it does not only deal with exponential generating functions, also provides access to ordinary generating functions.

The techniques of analytic combinatorics (say, as in the text by Flajolet and Sedgewick) are far more concrete. They concentrate on a few operators: cycles, sets, etc. and then go much further in the analysis of related generating function. As such, there is more focus on algorithms (and implementations) and methods which work in precise contexts. The singularities tell the story of both counting and parameter distribution, which is remarkable.

I hope that helps.

(*) This article translates some of the conditions into remarkably straightforward conditions. http://www.sciencedirect.com/science/article/pii/S0097316512000908 Algorithms for combinatorial structures: Well-founded systems and Newton iterations Carine Pivoteau, Bruno Salvy, Michèle Soria

$\endgroup$
4
$\begingroup$

At the time of writing that Wikipedia article on Analytic combinatorics does not at all get into the meat of analytic combinatorics which is the complex analysis part. The article only covers the symbolic part which is the first half of the book on Analytic Combinatorics: http://algo.inria.fr/flajolet/Publications/book.pdf

The second half of the book is the analysis part about asymptotics mentioned in zyx's answer.

$\endgroup$
  • 1
    $\begingroup$ Yes of course, the book is a better reference. Thanks. $\endgroup$ – Carolus Apr 6 '13 at 5:45

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.