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.
How unlabeled structures work
Let's take a closer look on the equivalence classes that are formed when we enumerate unlabeled structures. What is common for the elements of an equivalence class? How to compute the size of an equivalence class? How to enumerate the elements of a given equivalence class, if a single representative is known?
Let $$$|A|=n$$$. Consider an object
Unable to parse markup [type=CF_MATHJAX]
of the species $$$F$$$. If we use a permutationUnable to parse markup [type=CF_MATHJAX]
on the underlying set of atoms, it will produce a new objectUnable to parse markup [type=CF_MATHJAX]
. There is a total of $$$n!$$$ possible permutations $$$\sigma$$$ of $$$n$$$ atoms, and when we applyUnable to parse markup [type=CF_MATHJAX]
to a specific object $$$o$$$ for all permutations $$$\sigma$$$, we obtain all the elements of its equivalence class defined above.Claim 1. For every object
Unable to parse markup [type=CF_MATHJAX]
that may be produced as a result of applyingUnable to parse markup [type=CF_MATHJAX]
to $$$o$$$, the number of permutations $$$\sigma$$$ that produceUnable to parse markup [type=CF_MATHJAX]
is the same as the number of permutations that produce $$$o$$$ itself.Explanation. Let $$$\tau$$$ be a permutation such that
Unable to parse markup [type=CF_MATHJAX]
. Then for any permutation $$$\sigma$$$ such thatUnable to parse markup [type=CF_MATHJAX]
, there is a permutationUnable to parse markup [type=CF_MATHJAX]
such thatUnable to parse markup [type=CF_MATHJAX]
. Same is true in the other direction.The permutations $$$\sigma$$$ such that
Unable to parse markup [type=CF_MATHJAX]
are called the automorphisms of the object $$$o$$$. So among $$$n!$$$ values ofUnable to parse markup [type=CF_MATHJAX]
, if we consider them as a multiset, each unique one is countedUnable to parse markup [type=CF_MATHJAX]
times, whereUnable to parse markup [type=CF_MATHJAX]
is the set of automorphisms of $$$o$$$.This allows us to say that the size of the equivalence class of $$$o$$$ is exactly
Unable to parse markup [type=CF_MATHJAX]
.Burnside lemma
The result above is very useful, as now instead of counting the number of equivalence classes we instead can "distribute" the counting among all the elements, that is we may represent the total number of equivalence classes as
Unable to parse markup [type=CF_MATHJAX]
In this way, the elements from the same equivalence class, when summed up together, will produce $$$1$$$.
On the other hand, the sum of
Unable to parse markup [type=CF_MATHJAX]
can be reformulated as follows:Unable to parse markup [type=CF_MATHJAX]
where
Unable to parse markup [type=CF_MATHJAX]
is the number of fixed points ofUnable to parse markup [type=CF_MATHJAX]
, that isUnable to parse markup [type=CF_MATHJAX]
.This gives the following alternative formula for the number of the equivalence classes:
Unable to parse markup [type=CF_MATHJAX]
also known as the Burnside lemma. That being said, the number of unlabeled structure on $$$n$$$ atoms of the species equates to the average number of fixed points over all permutations of length $$$n$$$. This key observation allows us to apply key properties of expected values to compute the number of equivalence classes, in particular use the linearity of expected value.
Automorphisms and fixed points for compositions
To construct an
Unable to parse markup [type=CF_MATHJAX]
structure, we first build an $$$F$$$-structure on a setUnable to parse markup [type=CF_MATHJAX]
, and then substitute the $$$i$$$-th of its atoms with a $$$G$$$-structure built on the set $$$A_i$$$. Then, we treat the disjoint unionUnable to parse markup [type=CF_MATHJAX]
as the full set of atoms. So, an object $$$o$$$ of speciesUnable to parse markup [type=CF_MATHJAX]
can be described by an objectUnable to parse markup [type=CF_MATHJAX]
and a family of objectsUnable to parse markup [type=CF_MATHJAX]
, whereUnable to parse markup [type=CF_MATHJAX]
.Automorphisms of a given object
Consider a permutation
Unable to parse markup [type=CF_MATHJAX]
. What should hold for it to be an automorphism of $$$o$$$?First of all, it should preserve the structure of $$$f$$$. The object $$$f$$$ is built on top of the sets
Unable to parse markup [type=CF_MATHJAX]
, and to preserve the structure of $$$f$$$, the permutation $$$\sigma$$$ should only map these sets to each other. In other words, it should map a set $$$A_i$$$ to a set $$$A_j$$$ such thatUnable to parse markup [type=CF_MATHJAX]
, and the functionUnable to parse markup [type=CF_MATHJAX]
defined from such mapping should be a permutations, which is, in turn, an automorphism of $$$f$$$.Then, if we look on a transition from $$$A_i$$$ to
Unable to parse markup [type=CF_MATHJAX]
, the permutation $$$\sigma$$$ should be consistent with the mappingUnable to parse markup [type=CF_MATHJAX]
. In other words, if we restrict the domain of $$$\sigma$$$ from the whole $$$A$$$ to its subset $$$A_i$$$, the resulting mappingUnable to parse markup [type=CF_MATHJAX]
should map the object $$$g_i$$$ into the objectUnable to parse markup [type=CF_MATHJAX]
.That being said, each permutation of interest
Unable to parse markup [type=CF_MATHJAX]
can be described by a permutationUnable to parse markup [type=CF_MATHJAX]
, which is an automorphism of $$$f$$$, and a family of bijectionsUnable to parse markup [type=CF_MATHJAX]
, such thatUnable to parse markup [type=CF_MATHJAX]
maps $$$g_i$$$ toUnable to parse markup [type=CF_MATHJAX]
.Fixed points of a given permutation
Such setting allows us to think about what should hold for an object
Unable to parse markup [type=CF_MATHJAX]
to be a fixed point of $$$\sigma$$$?- The object $$$f$$$ must be a fixed point of
Unable to parse markup [type=CF_MATHJAX]
; - For each
Unable to parse markup [type=CF_MATHJAX]
it must hold thatUnable to parse markup [type=CF_MATHJAX]
.
The first criteria is understandable and is in line with what we have studied so far. What about the second, though? When is it true?
Essentially, it means that in a cycle decomposition of the permutation
Unable to parse markup [type=CF_MATHJAX]
, for each cycleUnable to parse markup [type=CF_MATHJAX]
we're allowed to choose a single distinct elementUnable to parse markup [type=CF_MATHJAX]
in such way that it is a fixed point of a permutationUnable to parse markup [type=CF_MATHJAX]
, and all the other ones will be uniquely defined by the mappingsUnable to parse markup [type=CF_MATHJAX]
.Objects
Unable to parse markup [type=CF_MATHJAX]
on a cycleUnable to parse markup [type=CF_MATHJAX]
Let
Unable to parse markup [type=CF_MATHJAX]
. What do we get if we average the amount of fixed pointsUnable to parse markup [type=CF_MATHJAX]
of $$$\tau$$$ over all permutations $$$\tau$$$? It follows from the Burnside lemma that we get the number of distinct unlabeled structures of species $$$G$$$ on $$$t$$$ atoms. The neat part here is that for each cycle inUnable to parse markup [type=CF_MATHJAX]
it could be done independently, multiplying the amounts to get the average amount for a fixed permutationUnable to parse markup [type=CF_MATHJAX]
.Averaging over all permutations
In other words, to count the average amount of fixed points of
Unable to parse markup [type=CF_MATHJAX]
, we can do the following:- Consider a permutation
Unable to parse markup [type=CF_MATHJAX]
; - Pick a fixed point of
Unable to parse markup [type=CF_MATHJAX]
as an $$$F$$$-structure; - For each cycle of
Unable to parse markup [type=CF_MATHJAX]
, pick an unlabeled structure $$$g$$$ of $$$G$$$ and duplicate it on the whole cycleUnable to parse markup [type=CF_MATHJAX]
; - Average the counts over all permutations
Unable to parse markup [type=CF_MATHJAX]
by dividing with $$$k!$$$.
These considerations boil down to the following essential formula:
Unable to parse markup [type=CF_MATHJAX]
where
Unable to parse markup [type=CF_MATHJAX]
is the number of cycles of length $$$j$$$ inUnable to parse markup [type=CF_MATHJAX]
, and the ordinary generating functions $$$G(x)$$$ andUnable to parse markup [type=CF_MATHJAX]
are defined asUnable to parse markup [type=CF_MATHJAX]
In other words, the functions are defined in such way that
Unable to parse markup [type=CF_MATHJAX]
andUnable to parse markup [type=CF_MATHJAX]
are the numbers of unlabeled $$$G$$$-structures andUnable to parse markup [type=CF_MATHJAX]
-structures correspondingly on $$$n$$$ atoms, corresponding to OGFs defined for unlabeled structures in the previous article.Intuitively,
Unable to parse markup [type=CF_MATHJAX]
is a generating functions for sets of $$$j$$$ equal unlabeled structures of species $$$G$$$, so we pick $$$|c|$$$ same $$$G$$$-structures for each cycle $$$c$$$ of length $$$|c|$$$ and then multiply the generating functions over all cycles, as it is done independently.If you're not convinced yet, you can find a bit more technical and rigorous (but less intuitive) computation below to get the same result.
Cycle index series
looking on the formula above, we may define a multivariate formal power series
Unable to parse markup [type=CF_MATHJAX]
which allows to rewrite
Unable to parse markup [type=CF_MATHJAX]
as the formal power series composition:Unable to parse markup [type=CF_MATHJAX]
The multivariate power series
Unable to parse markup [type=CF_MATHJAX]
is called the cycle index series of the species $$$F$$$ and it holds a tremendous amount of information about the structure of the species. In particular, we may note that the exponential generating function of the species is simplyUnable to parse markup [type=CF_MATHJAX]
As to count labeled structures it is sufficient to count the fixed points of identity permutations (for which all cycles have length $$$1$$$).
and the ordinary generating function of unlabeled structures of the species is nothing but
Unable to parse markup [type=CF_MATHJAX]
as we may perceive the species as a composition of itself with an "atom" species $$$x$$$.
This is the composition formula for the unlabeled structures that we sought for.
Why is it called a cycle index series?
The definition of a cycle index series above may be rewritten in terms of automorphisms:
Unable to parse markup [type=CF_MATHJAX]
where
Unable to parse markup [type=CF_MATHJAX]
.Substituting
Unable to parse markup [type=CF_MATHJAX]
, and recalling that the equivalence class of $$$o$$$ hasUnable to parse markup [type=CF_MATHJAX]
objects, we may rewrite the sum above asUnable to parse markup [type=CF_MATHJAX]
where
Unable to parse markup [type=CF_MATHJAX]
is the set of representatives of unlabeled equivalence classes ofUnable to parse markup [type=CF_MATHJAX]
.For a given set of permutations that is closed under composition (so-called permutation group) $$$G$$$, the polynomial
Unable to parse markup [type=CF_MATHJAX]
is known more widely as the cycle index of $$$G$$$. That being said, the cycle index series
Unable to parse markup [type=CF_MATHJAX]
is the formal sum of cycle indices over all unlabeled structures of the species $$$F$$$ of all possible sizes.Atom colorings
Note that for in all discussions above we assumed that either all atoms are distinct from each other (labeled) or indistinguishable (unlabeled). In a bit more generic setting we may assume that each atom is colored in one of $$$s$$$ distinct colors.
In this case, the number of indistinguishable structures built on such set of atoms is
Unable to parse markup [type=CF_MATHJAX]
, as we enumerated fixed points ofUnable to parse markup [type=CF_MATHJAX]
by coloring all atoms on each cycle in the same color.Correspondingly, if we want to also keep track of the total number of atoms in cycle index series, we should use
Unable to parse markup [type=CF_MATHJAX]
Then, the coefficient
Unable to parse markup [type=CF_MATHJAX]
will denote the number of $$$F$$$-structure on $$$n$$$ atoms, such that each atom is colored in one of $$$s$$$ distinct colors.Examples
There are two famous species $$$F$$$ with known composition formulas. Specifically, the cycles and sets.
Let's derive explicit form for their cycle index series, and from that obtain the operators
Unable to parse markup [type=CF_MATHJAX]
and $$$\operatorname{MSET}$$$:Cycles
Consider a cycle of length $$$n$$$. What do its automorphisms look like? Its automorphisms are:
- A permutation with this cycle as its cycle presentation;
- Powers of this permutation.
This is a total of $$$n$$$ elements. When we raise the cycle to the power $$$k$$$, we obtain a set of
Unable to parse markup [type=CF_MATHJAX]
of lengthUnable to parse markup [type=CF_MATHJAX]
each.For example, raising single cyclic shift
Unable to parse markup [type=CF_MATHJAX]
with cycle presentationUnable to parse markup [type=CF_MATHJAX]
to the power $$$3$$$, we get a permutationUnable to parse markup [type=CF_MATHJAX]
with a cycle presentationUnable to parse markup [type=CF_MATHJAX]
. Note that all cycles of length $$$n$$$ are isomorphic to each other, meaning that there is a unique unlabeled cycle of length $$$n$$$ with the cycle indexUnable to parse markup [type=CF_MATHJAX]
The last formula is due to the fact that there are
Unable to parse markup [type=CF_MATHJAX]
numbers $$$k$$$ such thatUnable to parse markup [type=CF_MATHJAX]
. If we sum it up over all $$$n$$$, we getUnable to parse markup [type=CF_MATHJAX]
then substituting
Unable to parse markup [type=CF_MATHJAX]
, we getUnable to parse markup [type=CF_MATHJAX]
making it into
Unable to parse markup [type=CF_MATHJAX]
From this, the unlabeled composition formula of
Unable to parse markup [type=CF_MATHJAX]
species of cycles and arbitrary species $$$f$$$ with OGF $$$f(x)$$$ is:Unable to parse markup [type=CF_MATHJAX]
Sets
Now, in case of sets, we would get the same set no matter how we rearrange its elements. Again, there is a unique unlabeled set on $$$n$$$ vertices, and its automorphisms are all possible permutations, hence we have
Unable to parse markup [type=CF_MATHJAX]
Assuming that there are
Unable to parse markup [type=CF_MATHJAX]
cycles of length $$$k$$$, the formula above rewrites asUnable to parse markup [type=CF_MATHJAX]
Indeed, the number of ways to make a permutation with given
Unable to parse markup [type=CF_MATHJAX]
isUnable to parse markup [type=CF_MATHJAX]
as for
Unable to parse markup [type=CF_MATHJAX]
cycles of length $$$k$$$, you divide byUnable to parse markup [type=CF_MATHJAX]
to not double-count cyclic shifts and byUnable to parse markup [type=CF_MATHJAX]
to not double-count rearrangements of cycles.On the other hand, if we sum it up over all $$$n$$$, we get
Unable to parse markup [type=CF_MATHJAX]
Adding a new variable $$$y$$$ to track the sum of
Unable to parse markup [type=CF_MATHJAX]
, we can rewrite it as product of sums:Unable to parse markup [type=CF_MATHJAX]
Finally, substituting $$$y=1$$$, we get the sum over all possible $$$n$$$ as
Unable to parse markup [type=CF_MATHJAX]
and the composition formula with set species
Unable to parse markup [type=CF_MATHJAX]
The results above also yield simplified expression for
Unable to parse markup [type=CF_MATHJAX]
:Unable to parse markup [type=CF_MATHJAX]
Cycle index composition
In a very generic setting, one may prove the general formula:
Unable to parse markup [type=CF_MATHJAX]
Derivation, explanation and proof of this formula is left to the reader as an exercise.
Further reading
Asymmetry index series
In this article, we studied how to account for symmetries (automorphisms) when we transition from enumerating labeled structures to enumerating unlabeled ones. Another use-case which is worth studying are so-called asymmetric structures, that is the structures that only have the identity permutation as their single automorphism. In such structures, any unlabeled structure has exactly $$$n!$$$ ways to turn it into a labeled one, meaning that the OGF of the unlabeled structures and the EGF of corresponding labeled structures coincide.
In a similar fashion, it is possible to introduce a so-called "asymmetry index series", which we may then use to compose operators like
Unable to parse markup [type=CF_MATHJAX]
andUnable to parse markup [type=CF_MATHJAX]
on the generating functions of asymmetric structures. Maybe I will write more about it in future blog entries...