Unlabeling combinatorial species (cycle index series)

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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.

Previously on combinatorial species

Labeled species

The species $$$F$$$ is a rule that produces:

For each finite set $$$A$$$, a finite set
Unable to parse markup [type=CF_MATHJAX]
consisting of all possible structures defined by the species $$$F$$$ that can be built using the elements of $$$A$$$ as atoms;
For each bijection
Unable to parse markup [type=CF_MATHJAX]
, a bijection
Unable to parse markup [type=CF_MATHJAX]
between the structures
Unable to parse markup [type=CF_MATHJAX]
and
Unable to parse markup [type=CF_MATHJAX]
, that describes how structures change if we change one set of atoms for another.

When we use the term "atoms", we mean the units used to enumerate the species, such as the vertices of a graph, the pairs of brackets in a bracket sequence, etc. For example, you may see

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

for the species of labeled trees below:

Labeled trees on sets
Unable to parse markup [type=CF_MATHJAX]
,
Unable to parse markup [type=CF_MATHJAX]
and
Unable to parse markup [type=CF_MATHJAX]
.
The image by Júlio Reis is distributed under CC BY-SA 3.0 license.

Unlabeled structures

The theory of combinatorial species described in the previous blog post is based on an assumption that all atoms are pairwise distinguishable ("labeled"). I also very briefly mentioned the concept of unlabeled structures in the end of the previous blog post:

On the left and on the right are equivalent trees. In the middle is the representation of their unlabeled structure.

We say that two structures

Unable to parse markup [type=CF_MATHJAX]

are equivalent if one can be obtained from the other by re-ordering the atoms in $$$A$$$. For example, on the picture above all the trees on the bottom row are equivalent to each other, as well as all the trees on 3 rows above it.

All unlabeled ordered trees on
Unable to parse markup [type=CF_MATHJAX]
vertices.

An unlabeled structure is what we get by essentially erasing the "labels" from the elements of

Unable to parse markup [type=CF_MATHJAX]

and treating atoms as indistinguishable from each other. Formally, it is an equivalence class in

Unable to parse markup [type=CF_MATHJAX]

with regard to the equivalence relation defined above.

Species composition

Perhaps a single most powerful aspect of combinatorial species is the notion of species composition.

A $$$G$$$-structure is formed on each set of the atom partition, and an $$$F$$$-structure is formed on top of the partition itself.
The image by Brent Yorgey is distributed under CC BY-SA 3.0 license.

Informally, a composition of species $$$F$$$ and $$$G$$$ is a species

Unable to parse markup [type=CF_MATHJAX]

whose combinatorial structure can be described as an $$$F$$$-structure whose atoms are substituted by instances of $$$G$$$-structures.

Function species is a set of cycles of rooted trees
An illustration from Combinatorial Species article by François Bergeron

Species composition allows us to think about one species as a combination of simpler species. Typical example of which is a species of permutations which can be interpreted as a species of sets of cycles due to cyclic presentation of permutations.

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 permutation

Unable to parse markup [type=CF_MATHJAX]

on the underlying set of atoms, it will produce a new object

Unable to parse markup [type=CF_MATHJAX]

. There is a total of $$$n!$$$ possible permutations $$$\sigma$$$ of $$$n$$$ atoms, and when we apply

Unable 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 applying

Unable to parse markup [type=CF_MATHJAX]

to $$$o$$$, the number of permutations $$$\sigma$$$ that produce

Unable 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 that

Unable to parse markup [type=CF_MATHJAX]

, there is a permutation

Unable to parse markup [type=CF_MATHJAX]

such that

Unable 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 of

Unable to parse markup [type=CF_MATHJAX]

, if we consider them as a multiset, each unique one is counted

Unable to parse markup [type=CF_MATHJAX]

times, where

Unable 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 of

Unable to parse markup [type=CF_MATHJAX]

, that is

Unable 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 set

Unable 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 union

Unable to parse markup [type=CF_MATHJAX]

as the full set of atoms. So, an object $$$o$$$ of species

Unable to parse markup [type=CF_MATHJAX]

can be described by an object

Unable to parse markup [type=CF_MATHJAX]

and a family of objects

Unable to parse markup [type=CF_MATHJAX]

, where

Unable 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 that

Unable to parse markup [type=CF_MATHJAX]

, and the function

Unable 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 mapping

Unable 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 mapping

Unable to parse markup [type=CF_MATHJAX]

should map the object $$$g_i$$$ into the object

Unable 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 permutation

Unable to parse markup [type=CF_MATHJAX]

, which is an automorphism of $$$f$$$, and a family of bijections

Unable to parse markup [type=CF_MATHJAX]

, such that

Unable to parse markup [type=CF_MATHJAX]

maps $$$g_i$$$ to

Unable 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 that
Unable 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 cycle

Unable to parse markup [type=CF_MATHJAX]

we're allowed to choose a single distinct element

Unable to parse markup [type=CF_MATHJAX]

in such way that it is a fixed point of a permutation

Unable to parse markup [type=CF_MATHJAX]

, and all the other ones will be uniquely defined by the mappings

Unable to parse markup [type=CF_MATHJAX]

Objects
Unable to parse markup [type=CF_MATHJAX]
on a cycle
Unable 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 points

Unable 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 in

Unable to parse markup [type=CF_MATHJAX]

it could be done independently, multiplying the amounts to get the average amount for a fixed permutation

Unable 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 cycle
Unable 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$$$ in

Unable to parse markup [type=CF_MATHJAX]

, and the ordinary generating functions $$$G(x)$$$ and

Unable to parse markup [type=CF_MATHJAX]

are defined as

Unable to parse markup [type=CF_MATHJAX]

In other words, the functions are defined in such way that

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

are the numbers of unlabeled $$$G$$$-structures and

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

Derivation

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 simply

Unable 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$$$ has

Unable to parse markup [type=CF_MATHJAX]

objects, we may rewrite the sum above as

Unable to parse markup [type=CF_MATHJAX]

where

Unable to parse markup [type=CF_MATHJAX]

is the set of representatives of unlabeled equivalence classes of

Unable 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 of

Unable 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 length

Unable to parse markup [type=CF_MATHJAX]

each.

For example, raising single cyclic shift

Unable to parse markup [type=CF_MATHJAX]

with cycle presentation

Unable to parse markup [type=CF_MATHJAX]

to the power $$$3$$$, we get a permutation

Unable to parse markup [type=CF_MATHJAX]

with a cycle presentation

Unable 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 index

Unable 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 that

Unable to parse markup [type=CF_MATHJAX]

. If we sum it up over all $$$n$$$, we get

Unable to parse markup [type=CF_MATHJAX]

then substituting

Unable to parse markup [type=CF_MATHJAX]

, we get

Unable 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 as

Unable to parse markup [type=CF_MATHJAX]

Indeed, the number of ways to make a permutation with given

Unable to parse markup [type=CF_MATHJAX]

as for

Unable to parse markup [type=CF_MATHJAX]

cycles of length $$$k$$$, you divide by

Unable to parse markup [type=CF_MATHJAX]

to not double-count cyclic shifts and by

Unable 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]

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.

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]

and

Unable to parse markup [type=CF_MATHJAX]

on the generating functions of asymmetric structures. Maybe I will write more about it in future blog entries...

Comments (3)

Show archived | Write comment?

ShivanshJ

22 months ago, # |

+40

I don't understand much, still I upvote!

→ Reply

adamant

← Rev. 3 →

+10

To provide a meaningful example of counting unlabeled species, consider unlabeled rooted trees on $$$n$$$ vertices (A000081). From the formula above it follows that the ordinary generating function $$$T(x)$$$ adheres to the equation

Differentiating this identity yields a simple recurrence

which also has a very nice and simple bijective proof, derived by Endagorion on Mathoverflow: link.

early-morning-dreams

+42

adamant's new contest's spoilers

adamant's blog

Recap

Labeled species

Unlabeled structures

Species composition

How unlabeled structures work

Burnside lemma

Automorphisms and fixed points for compositions

Automorphisms of a given object

Fixed points of a given permutation

Averaging over all permutations

Cycle index series

Why is it called a cycle index series?

Atom colorings

Examples

Cycles

Sets

Cycle index composition

Further reading

Asymmetry index series