Hi everyone!
In my previous blog, I wrote about how generating functions can be used to enumerated labeled species. In this blog, I want to continue the topic by writing about how one can account for different kinds of symmetries when counting different combinatorial structures. Ultimately, we will end up deriving and hopefully understanding the analogue of Pólya enumeration theorem in species.
Difficulty: ★★★★☆
Prerequisites:
- Familiarity with combinatorial species (see my prev. blog), OR
- Very good intuition with enumerative combinatorics, genfuncs and recap below.
I will try to use plain language rather than formulas as much as possible, as it seems to be the preferred format for readers.
Recap
Below is a very brief recap of the most important things from the previous article. I tried to keep it as informal as possible.
If $$$A(x)$$$ and $$$B(x)$$$ are the generating functions for species $$$A$$$ and $$$B$$$, then $$$A(B(x))$$$ is the generating function for their composition.
It is a fundamental result for labeled species. Unfortunately, there is no simple analogue with unlabeled structures, and deriving the composition formula in some reasonable formulation for them is the ultimate goal of this article.