Enumeration of m-ary cacti

• Published in 1998
• Added on 2018-10-23

The purpose of this paper is to enumerate various classes of cyclically colored m-gonal plane cacti, called m-ary cacti. This combinatorial problem is motivated by the topological classification of complex polynomials having at most m critical values, studied by Zvonkin and others. We obtain explicit formulae for both labelled and unlabelled m-ary cacti, according to i) the number of polygons, ii) the vertex-color distribution, iii) the vertex-degree distribution of each color. We also enumerate m-ary cacti according to the order of their automorphism group. Using a generalization of Otter's formula, we express the species of m-ary cacti in terms of rooted and of pointed cacti. A variant of the m-dimensional Lagrange inversion is then used to enumerate these structures. The method of Liskovets for the enumeration of unrooted planar maps can also be adapted to m-ary cacti.

Comment

The number of binary cacti is the number of Truchet tiles.

Links

• http://arxiv.org/abs/math/9804119v2
• http://arxiv.org/pdf/math/9804119v2

Other information

BibTeX entry

@article{Enumerationofmarycacti,
	key = {Enumerationofmarycacti},
	type = {article},
	title = {Enumeration of m-ary cacti},
	author = {Miklos Bona and Michel Bousquet and Gilbert Labelle and Pierre Leroux},
	abstract = {The purpose of this paper is to enumerate various classes of cyclically
colored m-gonal plane cacti, called m-ary cacti. This combinatorial problem is
motivated by the topological classification of complex polynomials having at
most m critical values, studied by Zvonkin and others. We obtain explicit
formulae for both labelled and unlabelled m-ary cacti, according to i) the
number of polygons, ii) the vertex-color distribution, iii) the vertex-degree
distribution of each color. We also enumerate m-ary cacti according to the
order of their automorphism group. Using a generalization of Otter's formula,
we express the species of m-ary cacti in terms of rooted and of pointed cacti.
A variant of the m-dimensional Lagrange inversion is then used to enumerate
these structures. The method of Liskovets for the enumeration of unrooted
planar maps can also be adapted to m-ary cacti.},
	comment = {The number of binary cacti is the number of Truchet tiles.},
	date_added = {2018-10-23},
	date_published = {1998-04-10},
	urls = {http://arxiv.org/abs/math/9804119v2,http://arxiv.org/pdf/math/9804119v2},
	collections = {Attention-grabbing titles,Combinatorics,Things to make and do},
	url = {http://arxiv.org/abs/math/9804119v2 http://arxiv.org/pdf/math/9804119v2},
	year = 1998,
	urldate = {2018-10-23},
	archivePrefix = {arXiv},
	eprint = {math/9804119},
	primaryClass = {math.CO}
}