Interesting Esoterica

Enumeration of m-ary cacti

Article by Miklos Bona and Michel Bousquet and Gilbert Labelle and Pierre Leroux
  • Published in 1998
  • Added on
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


BibTeX entry

@article{Enumerationofmarycacti,
	title = {Enumeration of m-ary cacti},
	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.},
	url = {http://arxiv.org/abs/math/9804119v2 http://arxiv.org/pdf/math/9804119v2},
	year = 1998,
	author = {Miklos Bona and Michel Bousquet and Gilbert Labelle and Pierre Leroux},
	comment = {The number of binary cacti is the number of Truchet tiles.},
	urldate = {2018-10-23},
	archivePrefix = {arXiv},
	eprint = {math/9804119},
	primaryClass = {math.CO},
	collections = {attention-grabbing-titles,combinatorics,things-to-make-and-do}
}