Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: EGS of many-sorted combinatorial species

Peva Blanchard (Aug 02 2024 at 10:54):

A (single-sorted) combinatorial species is a functor $F : B \to B$ where $B$ is the groupoid of finite sets with bijections. The exponential generating series of $F$ is

$$F_{egs}(z) = \sum_{n \ge 0} |F[n]| \cdot \frac{z^n}{n!}$$

There is a generalization of species to model many-sorted data. Let $S$ be a finite set of sorts. A (finite) colored set is a function $\chi: U \to S$ where $U$ is a finite set. Let $B_S$ denote the groupoid of finite colored sets with color-preserving bijections. A $S$-sorted combinatorial species is a functor $F: B_S \to B$.

One should be able to assign a multi-variate exponential generating series to $F$. Instead of a single variable $z$, we have a variable $z_s$ for every sort $s \in S$. It seems to me that the egs of $F$ should be

$$F_{egs}((z_s ~|~ s \in S)) = \sum_{l \ge 0}\sum_{[\chi] \in Iso(S^l)} |F[\chi]| \cdot \frac{z_{\chi}}{\chi!}$$

where:

• $[\chi]$ runs over the isomorphism classes of colored sets $\{1,\dots,l\} \to S$
• $z_{\chi} = \prod_{1 \le i \le l} z_{\chi(i)}$
• and $\chi! = \prod_{s \in S} m_s!$ where $m_s$ is the number of occurrences of $s$ in $\chi$.

Is it the correct definition?

John Baez (Aug 02 2024 at 11:19):

Yes. Multi-variable species and their generating functions have already been put to good use in Flajolet and Sedgewick's excellent book Analytic Combinatorics. You can get a link to a free copy and see applications to the properties of random permutations in my page Random permutations.

By the way, it's also good to use mixed exponential/ordinary generating functions, e.g. for structures like "a permutation of an n-element set with k cycles".

Peva Blanchard (Aug 02 2024 at 12:13):

Great thank you!

Eric M Downes (Aug 02 2024 at 12:20):

The link on Flajolet's (delightfully retro) site is broken atm, but here is a copy of AC (hosted by Sedgewick)

John Baez (Aug 02 2024 at 12:44):

Thanks. I'll update the link.