Enumeration of m-ary cacti

according to their vertex and degree distributions

Miklós Bóna Michel Bousquet Gilbert Labelle Pierre Leroux

LACIM

Université du Québec à Montréal Montréal, Québec, Canada

April 17, 1998

Proposed Running Head: Enumeration of m-ary cacti

Send proofs to: Pierre Leroux LACIM Université du Québec à Montréal C.P. 8888, Succursale Centre-ville Montréal, Québec, H3C 3P8 CANADA

Enumeration of m-ary cacti according to their color and degree distributions

Miklós Bóna Michel Bousquet Gilbert Labelle Pierre Leroux

LACIM Université du Québec à Montréal Montréal, Québec, H3C 3P8 Canada

April 17, 1998

Abstract

We enumerate cyclically colored m-gonal plane cacti (called m-ary cacti) according to the degree distribution of vertices of each color. This combinatorial problem is motivated by the topological classification of complex polynomials having at most m critical values, studied by Zvonkin and others. The corresponding problem for rooted m-ary cacti has been solved by Goulden and Jackson in connection with factorizations of a cyclic permutation into m permutations with given cycle types. We obtain explicit formulae for both the labeled and unlabeled m-ary cacti, according to both the vertex-degree and vertex-color distributions, and also for unlabeled m-ary cacti according to the order of their automorphism group. To achieve our goal, we prove a dissymmetry theorem for m-cacti extending the well-known Otter’s formula for trees and use an m-variable generalization of Chottin’s 2-variable Lagrange inversion formula.

1 Introduction

A cactus is a connected simple graph in which each edge lies in exactly one elementary cycle. It is equivalent to say that all blocks (2-connected components) of a cactus are elementary cycles, i.e., polygons. An m-cactus is a cactus all of whose polygons are m-gons, for some fixed m ≥ 2. By convention, a 2-cactus is simply a tree. These graphs are also called “Husimi trees”, and their definition was given by Uhlenbeck [18] and Riddell [14] following a paper by Husimi [12] on the cluster integrals in the theory of condensation in statistical mechanics.

A plane m-cactus is an embedding of an m-cactus into the plane so that every edge is incident with the unbounded region. An m-ary cactus is a plane m-cactus whose vertices are cyclically mcolored 1, 2, ⋯, m counterclockwise within each m-gon. For technical reasons, we also consider a single vertex colored in any one of the m colors to be an m-ary cactus. A quaternary cactus is shown on Figure 1.

The goal of this paper is to enumerate m-ary cacti according to the degree distributions of vertices of each color. This extends previous results [13] of two of the authors on the enumeration of bicolored plane trees according to their degree distributions to general m ≥ 2.

We define the degree of a vertex in a cactus to be the number of m-gons adjacent to that vertex. Note that it is twice the number of edges adjacent to the given vertex. Let c be any m-ary cactus. Let k_{ij} be the number of vertices of color i and degree j, of c and let k_{i} = (k_{i0}, k_{i1}, k_{i2}, ⋯). Moreover, let n_{i} = ∑_{j} k_{ij} be the number of vertices of color i, let n = ∑_{i} n_{i} be the total number of vertices, and let p be the number of polygons in c.

For example, in Figure 1, the vertex-degree distributions are

k_{1} = (0, 7, 1, 0, 1, 0, ⋯) = 1^{7}2^{1}4^{1}, k_{2} = (0, 7, 3, 0, 0, 0, ⋯) = 1^{7}2^{3},
k_{3} = (0, 8, 1, 1, 0, 0, ⋯) = 1^{8}2^{1}3^{1}, k_{4} = (0, 9, 2, 0, 0, 0, ⋯) = 1^{9}2^{2},
p = 13, n_{1} = 9, n_{2} = 10, n_{3} = 10, n_{4} = 11, and n = 40.

Figure 1: A quaternary cactus.

Clearly, for any m-ary cactus c with n vertices and p polygons we have

∑_{j} jk_{ij} = p, for all i,  (1)

since each polygon contains exactly one vertex of color i, and also

n = (m − 1)p + 1,  (2)

as one sees easily by induction on p. Also note the technical condition

p ≥ 1 ⇒ k_{i0} = 0 for all i.  (3)

Conditions (1), (2) and (3) are called the coherence conditions. If a degree distribution does not fulfill the coherence conditions, then the number of m-ary cacti with that distribution is 0.

Conversely, if the coherence conditions are satisfied, then it can be shown by induction on p that there exists at least one m-ary cactus having the given degree distribution, see [6]. The question is to determine how many there are. The following notations are needed: for any sequence of integers a = (a_{j})_{j≥0}, any integer h ≥ 1 and any m-tuple k⃗ = (k_{1}, k_{2}, ⋯ k_{m}) of sequences k_{i} = (k_{ij})_{j≥0}, set

s(a) = ∑_{j≥0} a_{j}, \frac{a}{d} = (\frac{a_{j}}{d})_{j≥0},

and also

\binom{s(a)}{a} = \binom{s(a)}{a_{0}, a_{1}, ⋯}, multinomial coefficient, Supp(a) = \{j ≥ 0|a_{j} ≠ 0\},

and δ^{h} = (δ_{j}^{h})_{j≥0}, where δ_{j}^{h} is the Kronecker symbol. Denote Div(h, k⃗) = Div(h, k_{1}, k_{2}, ⋯ k_{m}) the set of (positive) common divisors of h and all k_{ij}, and σk⃗ = (k_{2}, k_{3}, ⋯ k_{m}, k_{1}), the cyclic shift of k⃗.

The main objective of this paper is to prove the following Theorem:

Theorem 1 Let p ≥ 1 be an integer, and k⃗ = (k_{1}, k_{2}, ⋯ k_{m}) be a given m-tuple of sequences of nonnegative integers k_{i} = (k_{ij})_{j≥0} satisfying the coherence conditions (1) – (3), with n_{i} = ∑_{j≥0} k_{ij} and n = ∑_{i=1}^{m} n_{i}. Then the number K̃(k⃗) of all unlabeled m-ary cacti having vertex distribution k⃗ is given by

K̃(k⃗) = F̃(k⃗) + F̃(σk⃗) + F̃(σ^{2}k⃗) + ⋯ + F̃(σ^{m−1}k⃗) − (m − 1)G̃(k⃗),  (4)

where

F̃(k⃗) = F̃(k_{1}, k_{2}, ⋯, k_{m}) = \frac{p^{m−2}}{∏_{j≠1} n_{j}} ∑_{h,d} ϕ(d)\binom{(n_{1} − 1)/d}{(k_{1} − δ^{h})/d} ∏_{j≠1} \binom{n_{j}/d}{k_{j}/d},  (5)

where ϕ denotes the arithmetic Euler totient function and the sum is taken over all pairs (h, d) of positive integers such that h ∈ Supp(k_{1}) and d ∈ Div(h, k_{1} − δ^{h}, k_{2}, ⋯, k_{m}), and

G̃(k⃗) = \frac{p^{m−1}}{∏_{i=1}^{m} n_{i}} · ∏_{i=1}^{m} \binom{n_{i}}{k_{i}}.  (6)

This result is motivated by the topological classification of complex polynomials having at most m critical values. Indeed, the preimage, under such a polynomial, of an m-gon joining the m “critical values” z_{1}, z_{2}, ⋯, z_{m} yields an m-ary cactus whose degree distributions correspond to the multiplicities of the critical points. See [6] for more details.

The correction factor G̃(k⃗) in formula (4) enumerates the rooted (that is, pointed at a polygon) m-ary cacti with vertex-degree distribution k⃗. This was proved by Goulden and Jackson [8], who also showed that these cacti represent the decomposition of the circular permutation (1, 2, ⋯, p) as a product of m permutations g_{1}, g_{2}, ⋯, g_{m}, where for i = 1, ⋯, m, g_{i} has cyclic type (1^{k_{i1}}2^{k_{i2}} ⋯). Rooting a cactus has the effect of forbidding any automorphism. Thus rooted cacti are asymmetric structures and their enumeration is somewhat easier. It follows that the number of labeled unrooted cacti with degree distribution k⃗ is given by

\frac{n_{1}!n_{2}! ⋯ n_{m}!}{p} G̃(k⃗)  (7)

and hence that

∑_{c} \frac{1}{|Aut(c)|} = \frac{1}{p} G̃(k⃗),  (8)

where the sum is taken over all unlabeled cacti c with degree distribution k⃗, and Aut(c) denotes the (color-preserving) automorphism group of c. This formula can be used, as in [6], to check that all cacti having a given degree distribution have been found.

As we will see later, the individual terms F̃(σ^{i−1}k⃗), i = 1, ⋯, m in (4) also have a combinatorial interpretation: they count unlabeled cacti which are pointed at a vertex of color i. Formula (4) is easy to program and demands little computation time. Table 1 gives some values of F̃(k⃗), G̃(k⃗), K̃(k⃗) and also of \overline{K}(k⃗), the number of asymmetric cacti with degree distribution k⃗. The formula for \overline{K}(k⃗) is obtained from that for K̃(k⃗) by replacing the Euler function ϕ by the arithmetic Möbius function function μ in (5).

\begin{matrix}m & k⃗ & (F̃(σ^{i−1}k⃗)), i = 1, ⋯, m & G̃(k⃗) & K̃(k⃗) & \overline{K}(k⃗) \\ 2 & (1^{5}3^{2}, 2^{7}) & (8, 7) & 14 & 1 & 1 \\ 2 & (1^{2}2^{2}4^{1}, 1^{2}2^{4}) & (76, 90) & 150 & 16 & 14 \\ 3 & (1^{3}2^{3}, 1^{3}2^{3}, 1^{6}3^{1}) & (600, 600, 702) & 900 & 102 & 99 \\ 3 & (1^{2}2^{1}, 1^{2}2^{1}, 1^{2}2^{1}) & (12, 12, 12) & 16 & 4 & 4 \\ 3 & (1^{2}2^{2}, 1^{2}2^{2}, 1^{4}2^{1}) & (54, 54, 69) & 81 & 15 & 12 \\ 3 & (1^{3}2^{1}4^{1}, 1^{3}2^{3}, 1^{7}2^{1}) & (600, 720, 960) & 1080 & 120 & 120 \\ 3 & (1^{3}2^{2}, 1^{3}2^{2}, 1^{3}2^{2}) & (280, 280, 280) & 392 & 56 & 56 \\ 3 & (1^{2}3^{2}, 1^{4}2^{2}, 1^{6}2^{1}) & (120, 180, 212) & 240 & 32 & 28 \\ 3 & (2^{4}, 1^{4}2^{2}, 1^{6}2^{1}) & (20, 30, 36) & 40 & 6 & 4 \\ 3 & (1^{4}4^{1}, 1^{4}2^{2}, 1^{4}2^{2}) & (252, 300, 300) & 400 & 52 & 48 \\ 3 & (1^{2}2^{3}, 1^{4}2^{2}, 1^{4}2^{2}) & (504, 600, 600) & 800 & 104 & 96 \\ 4 & (1^{4}2^{2}, 1^{4}2^{2}, 1^{4}2^{2}, 1^{6}2^{1}) & (6000, 6000, 6000, 7008) & 8000 & 1008 & 992 \end{matrix}

Table 1: The number of cacti and of asymmetric cacti according to their vertex-degree distributions.

The main tool in eliminating the pointing is a Dissymmetry theorem which expresses the class of m-ary cacti in terms of other species that can be enumerated using Lagrange inversion. This theorem is related to the Dissimilarity characteristic theorem for (nonplanar) cacti, due to Harary and Norman [9], and leads to an extension of Otter’s formula for trees. It is established in section 2 together with other necessary functional equations relating various species of m-ary cacti.

In section 3 we establish a particular form of a multidimensional Lagrange inversion, which is well adapted to the present situation. It extends the previously known two-dimensional case, in the spirit of Chottin’s formulae [4] [5], and use the crucial observation due to Goulden and Jackson [8] that a certain Jacobian matrix reduces to a rank-1 matrix. We then use these results in section 4 to enumerate both labeled and unlabeled m-ary cacti according to both their vertexdegree end vertex-color distributions (see Tables 1 and 2). In particular, we prove Theorem 1.

In the last section, we first enumerate unlabeled m-ary cacti according to the order of their automorphism group and to their color and degree distributions. We then present some related enumerative results, concerning labeled free m-ary cacti and unlabeled rooted m-ary cacti having p polygons. The latter are found to be equinumerous with m-ary ordered rooted trees having p vertices. We also state a closely related result due to Bousquet-Mélou and Schaeffer on rooted m-ary constellations, having p polygons.

We have used the species formulation as a helpful unifying framework in this paper. A basic reference for the theory of species is the book [1]. However, the paper remains accessible to anyone with a knowledge of Pólya theory applied to graphical enumeration (see [10]).

2 Functional equations for m-ary cacti

We consider the class K of m-ary cacti as an m-sort species. This means that an m-ary cactus is seen as a structure constructed on an m-tuple of sets (U_{1}, U_{2}, ⋯, U_{m}), the elements of U_{i} being the (labels for) vertices of color i. Moreover, the relabeling bijections, and in particular, the automorphisms of m-ary cacti are required to preserve the sorts of elements, that is, the colors. Although we are interested in the enumeration of unlabeled cacti, it is easier to establish the functional equations by giving bijections between labeled structures. If we ensure that these bijections are natural, that is, that they commute with any relabeling, thus defining an isomorphism of species, then the consequences for both the labeled (exponential) generating function

K(x_{1}, x_{2}, ⋯, x_{m}) = ∑_{n_{1},n_{2},···,n_{m}} |K[n_{1}, n_{2}, ⋯, n_{m}]|\frac{x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}}{n_{1}! ⋯ n_{m}!}  (9)

and the unlabeled (ordinary) generating function

K̃(x_{1}, x_{2}, ⋯, x_{m}) = ∑_{n_{1},n_{2},···,n_{m}} K̃(n_{1}, n_{2}, ⋯, n_{m})x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}  (10)

are automatic. Here K[n_{1}, n_{2}, ⋯, n_{m}] denotes the set of m-ary cacti over the multiset [n_{1}] + [n_{2}]+⋯+[n_{m}], with [n] = {1, 2, ⋯, n}, and K̃(n_{1}, n_{2}, ⋯, n_{m}) denotes the number of unlabeled m-ary cacti having n_{i} vertices of color i, for all i = 1, ⋯, m.

Note that the plane embedding of an m-ary cactus c is completely characterized by the specification, for each vertex v of c, of a circular permutation on the polygons adjacent to v. We now introduce the following subsidiary m-sort species:

• K^{◇} : species of rooted (that is, pointed at a polygon) m-ary cacti

• K^{•_{i}} : species of mary cacti, pointed at a vertex of color i,

• A_{i} : species of m-ary cacti, planted at a vertex of color i.

A planted cactus is similar to a pointed cactus except that a pair of half-edges is attached to the pointed vertex, thus contributing 1 more to the degree of this vertex, and preventing the adjacent polygons to fully rotate around it. See Figure 2.

Proposition 1 We have the following isomorphisms of species, for i = 1, ⋯, m:

A_{i} = X_{i}L(Â_{i})  (11)
K^{•_{i}} = X_{i}(1 + C(Â_{i}))  (12)
K^{◇} = A_{1}A_{2} ⋯ A_{m},  (13)

where X_{i} denotes the species of singletons of sort (or color) i, Â_{i} := ∏_{j≠i} A_{j} denotes the product of all Aj except A_{i}, C denotes the species of (non-empty) circular permutations and L denotes that of (possibly empty) permutations, that is, more precisely, of linear orders (or lists).

Figure 2: A planted ternary cactus.

Proof: As observed above, the plane embedding of a planted m-ary cactus determines a linear order on the neighboring polygons of the pointed vertex. If this vertex, say of color 1, is removed, each of these adjacent polygons can be simply decomposed into the product of m−1 planted mary cacti with roots of color 2, 3, ⋯, m. Since this data completely specifies the planted cactus, we have equation (11). See Figure 2 for the illustration of the equation A_{1} = X_{1}L(A_{2}A_{3}) in the ternary (m = 3) case.

Equation (12) is similar to (11) except that for pointed cacti the polygons adjacent to the pointed vertex can freely rotate around it. Figure 3 illustrates the equation K^{•_{3}} = X_{3}(1 + C(A_{1}A_{2})). Equation (13) is immediate. See Figure 4. □

Remark that equations (11) and (13) are essentially due to Goulden and Jackson [8].

Recall that in a connected graph g, a vertex x belongs to the center of g if the maximal distance from x to any other vertex is minimal. In particular, if g is a cactus, then it is easy to see that the center of g is either a single vertex or a polygon. Now let c be an m-ary cactus. In this case we define the center in a slightly different way: if the previous definition yields a polygon P as the center of c, then we will take the color-1 vertex of P to be the center of c. If the previous definition yields a vertex y as the center of c, then we leave this definition unchanged. So the center of an m-ary cactus is always a vertex.

The main result of this section is the following.

Figure 3: A ternary cactus pointed at vertex v.

Figure 4: A rooted ternary cactus.

Theorem 2 Dissymmetry theorem for m-ary cacti. There is an isomorphism of species

K^{•_{1}} + K^{•_{2}} + ⋯ + K^{•_{m}} = K + (m − 1)K^{◇}  (14)

Proof: For clarity, we prove the theorem for m = 3, the proof for general m being analogous.

The left hand side corresponds to cacti which have been pointed at one vertex, of color 1, 2, or 3. The first member of the right hand side corresponds to cacti which have been pointed in a canonical way, at their center. So what remains to construct is a natural bijection from triangular cacti pointed not in their center onto two cases of ordered triplets of planted ternary cacti at a vertex of color 1, 2 and 3, respectively.

So let c be a ternary cactus pointed at a vertex x of color 1 which is different from the center Z of c. Suppose the shortest path from x to Z starts with the edge e = {x, y}, and let T be the unique triangle containing e (see Figure 5). Then we cut all three edges of T and thus separate c into three smaller cacti, which are planted in a vertex of color 1, 2 and 3 respectively, that is, an A_{1}A_{2}A_{3}-structure.

It is easy to see that we could have obtained this same triplet in another way. Indeed, if the vertices of T are x, y and z, then pointing the cactus c at z would have resulted in this same triplet. So this operation does define a map into 2A_{1}A_{2}A_{3}.

To see that our algorithm is reversible, take any 3-tuple of cacti which are planted in vertices x, y and z of color 1, 2, and 3 respectively. Join x, y and z by a triangle to get the cactus c, and look for its center Z. If Z comes from the component of x, then we can point either y or z in c, if Z comes from the component of y, then we can point either x or z in c, finally, if Z comes from the component of z, then we can point either x or y in c. It is then a simple matter to number each of these cases in order to make this correspondance bijective, completing the proof. □

Figure 5: K^{•_{1}} + K^{•_{2}} + K^{•_{3}} = K + 2K^{⋄}

Corollary 1 The species K of m-ary cacti can be written as

K = ∑_{i=1}^{m} K^{•_{i}} − (m − 1)K^{◇} = ∑_{i=1}^{m} X_{i}(1 + C)(Â_{i}) − (m − 1) ∏_{i=1}^{m} A_{i}  (15)
□

The consequences for the labeled and unlabeled generating functions then follow from general principles. For i = 1, ⋯ m, we have:

A_{i}(x) = x_{i} \frac{1}{1 − Â_{i}(x)}  (16)

Ã_{i}(x) = x_{i} \frac{1}{1 − ˜ Â_{i}(x)}  (17)

from which it follows that Ã_{i}(x) = A_{i}(x) since ˜ Â_{i} = ˆ Ã_{i}. This expresses the fact that planted cacti are asymmetric structures. Moreover,

K^{•_{i}}(x) = x_{i}(1 + log \frac{1}{1 − Â_{i}(x)}),  (18)

K̃^{•_{i}}(x) = x_{i}(1 + ∑_{d≥1} \frac{ϕ(d)}{d} log \frac{1}{1 − Â_{i}(x^{d})}),  (19)

where x^{d} := (x_{1}^{d}, x_{2}^{d}, ⋯, x_{m}^{d}). We also have

K^{◇}(x) = K̃^{◇}(x) = A_{1}(x) ⋯ A_{m}(x)  (20)

and finally,

K̃(x) = ∑_{i=1}^{m} K̃^{•_{i}}(x) − (m − 1)K^{◇}(x).  (21)

In order to enumerate m-ary cacti according to their degree distributions, we introduce weights in the form of monomials w(c) = ∏_{i,j} r_{ij}^{k_{ij}} with i = 1, ⋯, m and j ≥ 0, for a cactus c having degree distribution k⃗ = (k_{ij}). In other words, the variable r_{ij} acts as a counter for (or marks) vertices of color i and degree j. We also use the notation r_{i} to denote the sequence (r_{i0}, r_{i1}, ⋯). We denote by K_{w}, K_{w}^{◇}, and K_{w}^{•_{i}} the corresponding species of m-ary cacti, weighted in this manner. We denote by A_{i,r} the species of planted (at a vertex of color i) m-ary cacti similarly weighted by degree. The functional equations (11)–(15) can then be extended as follows:

A_{i,r} = X_{i}(r_{i,1} + r_{i,2}Â_{i,r}^{2} + r_{i,3}Â_{i,r}^{3} + ⋯)  (22)

where Â_{i,r} = ∏_{j≠i} A_{i,r},

K_{w}^{•_{i}} = X_{i}(r_{i,0} + r_{i,1}C_{1}(Â_{i,r}) + r_{i,2}C_{2}(Â_{i,r}) + ⋯),  (23)

where C_{k} denotes the species of circular permutations of length k,

K_{w}^{◇} = ∏_{i=1}^{m} A_{i,r},  (24)

and

K_{w} = ∑_{i=1}^{m} K_{w}^{•_{i}} − (m − 1)K_{w}^{◇}.  (25)

The important point here is that the weights behave multiplicatively, with respect to the operations of product and partitional composition. The consequences for the labeled and unlabeled generating functions are as follows:

A_{i,r}(x) = x_{i}(r_{i,1} + r_{i,2}Â_{i,r}(x) + r_{i,3}Â_{i,r}^{2}(x) + ⋯),  (26)
Ã_{i,r}(x) = A_{i,r}(x),  (27)
K_{w}^{•_{i}}(x) = x_{i}(r_{i,0} + ∑_{h≥1} \frac{r_{i,h}}{h} Â_{i,r}^{h}(x)),  (28)

K̃_{w}^{•_{i}}(x) = x_{i}(r_{i,0} + ∑_{h≥1} \frac{r_{i,h}}{h} ∑_{d|h} ϕ(d)Â_{i,r^{d}}^{h/d}(x^{d})),  (29)

where r^{d} denotes the set of variables {r_{i,j}^{d}}, for i = 1, ⋯, m, j ≥ 0. We also have

K_{w}^{◇}(x) = K̃_{w}^{◇}(x) = ∏_{i=1}^{m} A_{i,r}(x),  (30)

and finally,

K̃_{w}(x) = ∑_{i=1}^{m} K̃_{w}^{•_{i}}(x) − (m − 1)K_{w}^{◇}(x).  (31)

3 Multidimensional Lagrange inversion techniques

In this section we establish a special form of multidimensional Lagrange inversion, which can be directly applied to m-ary cacti. First recall the standard form of Lagrange inversion, due to Good. See Theorem 1.2.9, 1, of [7] or the equivalent formula (28b) of [1].

Theorem 3 Good’s Lagrange Inversion Formula. Let A_{1}, A_{2}, ⋯ A_{m} be formal power series in the variables x_{1}, x_{2}, ⋯, x_{m} such that the relations A_{i} = x_{i}R_{i}(A_{1}, A_{2}, ⋯, A_{m}) are satisfied for all i = 1, ⋯, m. Then for any formal power series F (t_{1}, t_{2}, ⋯, t_{m}) we have:

[x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}]F (A_{1}(x), ⋯, A_{m}(x)) = [t_{1}^{n_{1}} ⋯ t_{m}^{n_{m}}]F (t)|K(t)|R_{1}^{n_{1}}(t) ⋯ R_{m}^{n_{m}}(t),  (32)

where t = (t_{1}, t_{2}, ⋯, t_{m}) and K(t) is the m × m matrix whose (i, j)-th entry is

K(t)_{ij} = δ_{ij} − \frac{t_{j}}{R_{i}(t)} · \frac{∂R_{i}(t)}{∂t_{j}}.  (33)
□

There is a particularly simple two-dimensional case of this formula, the alternating case, which we will call the Chottin formula. In the papers [4] [5], Chottin worked extensively on the two-dimensional Lagrange inversion and its combinatorial proof.

Theorem 4 Chottin Formula. Let A(x, y) and B(x, y) be two formal power series satisfying the relations A = xΦ(B) and B = yΨ(A), where Φ(t) and Ψ(s) are given formal power series. Then, for any nonnegative integers α and β we have:

[x^{n}y^{m}]A^{α}B^{β} = (1 − \frac{(n − α)(m − β)}{nm})[s^{n−α}t^{m−β}]Φ^{n}(t)Ψ^{m}(s), n ≥ 1, m ≥ 1. (34)
□

We extend this result into m dimensions. This is the main result of this section.

Theorem 5 Generalized Chottin formula. Let A_{1}, A_{2}, ⋯, A_{m} be formal power series in the variables x_{1}, x_{2}, ⋯, x_{m} such that for i = 1, ⋯, m, the relations A_{i} = x_{i}Φ_{i}(Â_{i}) are satisfied, where the Φ_{i} are given formal power series of one variable, and Â_{i} = ∏_{j≠i} A_{j}. Also let n = (n_{1}, ⋯, n_{m}) with n_{i} ≥ 1 and let α_{1}, ⋯, α_{m} be nonnegative integers. Set n = ∑_{i=1}^{m} n_{i} and α = ∑_{i=1}^{m} α_{i}. Suppose that the following coherence conditions are satisfied:

n_{i} ≥ α_{i}, \frac{n − α}{m − 1} = β is an integer.

Then

[x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}]A_{1}^{α_{1}} ⋯ A_{m}^{α_{m}} = D · [s_{1}^{β_{1}} ⋯ s_{m}^{β_{m}}]Φ_{1}^{n_{1}}(s_{1}) ⋯ Φ_{m}^{n_{m}}(s_{m}),  (35)

where

D = ∏_{i=1}^{m}(1 + \frac{β_{i}}{n_{i}}) − ∑_{j=1}^{m} \frac{β_{j}}{n_{j}} ∏_{i≠j}(1 + \frac{β_{i}}{n_{i}}),  (36)

and β_{i} = β − n_{i} + α_{i}.

Proof: We use Theorem 3 with R_{i}(t_{1}, ⋯ t_{m}) = Φ_{i}(t̂_{i}), where t̂_{i} = ∏_{j≠i} t_{j}. We take advantage of some very useful observations made by Goulden and Jackson in [8] to compute the determinant |K(t)|. Indeed, for i = 1, 2, ⋯, m, we have

t_{j} \frac{∂R_{i}}{∂t_{i}} = 0,

as R_{i}(t) does not depend on t_{i}, and for j ≠ i,

t_{j} \frac{∂R_{i}}{∂t_{j}} = t̂_{i}Φ′_{i}(t̂_{i})

is independent of j. We set Ψ_{i}(t̂_{i}) = t̂_{i}Φ′_{i}(t̂_{i}) and write Ψ_{i} = Ψ_{i}(t̂_{i}), Φ_{i} = Φ_{i}(t̂_{i}).

The definition of K(t) then yields, after routine transformations:

|K(t)| = \frac{∏_{i=1}^{m}(Φ_{i} + Ψ_{i})}{∏_{i=1}^{m} Φ_{i}} · |δ_{ij} − \frac{Ψ_{i}}{Ψ_{i} + Φ_{i}} |.

Let A_{ij} = (1 − \frac{Ψ_{i}}{Ψ_{i}+Φ_{i}}) and note that the rank of A is 1 as all its columns are equal. So, by the Sherman-Morrison formula [16] we have |I +A| = 1+trace(A). Therefore, the previous equation yields

|K(t)| = \frac{∏_{i=1}^{m}(Φ_{i} + Ψ_{i})}{∏_{i=1}^{m} Φ_{i}} · (1 − ∑_{i=1}^{m} \frac{Ψ_{i}}{Ψ_{i} + Φ_{i}}).  (37)

It follows from the Lagrange inversion formula (32) that

[x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}]A_{1}^{α_{1}} ⋯ A_{m}^{α_{m}} = [t_{1}^{n_{1}} ⋯ t_{m}^{n_{m}}]t_{1}^{α_{1}} ⋯ t_{m}^{α_{m}} · |K(t)| ∏_{i=1}^{m} Φ_{i}^{n_{i}}

= [t_{1}^{n_{1}−α_{1}} ⋯ t_{m}^{n_{m}−α_{m}}](∏_{i=1}^{m} Φ_{i}^{n_{i}−1}(Φ_{i} + Ψ_{i}))(1 − ∑_{i=1}^{m} \frac{Ψ_{i}}{Ψ_{i} + Φ_{i}}). (38)

Now let us define the coefficients c_{i,β_{i}} by

Φ_{i}^{n_{i}}(t̂_{i}) = ∑_{β_{i}≥0} c_{i,β_{i}} t̂_{i}^{β_{i}},  (39)

which implies, by the definition of Ψ_{i} that

Φ_{i}^{n_{i}−1}(t̂_{i})Ψ_{i}(t̂_{i}) = ∑_{β_{i}≥0} \frac{β_{i}}{n_{i}} c_{i,β_{i}} t̂_{i}^{β_{i}}.  (40)

Recall that n = ∑_{i=1}^{m} n_{i} and α = ∑_{i=1}^{m} α_{i}, and denote β = ∑_{i=1}^{m} β_{i}. Then t_{1}^{n_{1}−α_{1}} ⋯ t_{m}^{n_{m}−α_{m}} = t̂^{β_{1}} ⋯ t̂^{β_{m}} if and only if β − β_{i} = n_{i} − α_{i} for all i, and summing these equations for 1 ≤ i ≤ m, we get (m − 1)β = n − α and β_{i} = β − n_{i} + α_{i}. We then conclude that (38) equals

[t̂_{1}^{β_{1}} ⋯ t̂_{m}^{β_{m}}](∏_{i=1}^{m} Φ_{i}^{n_{i}−1}(Φ_{i} + Ψ_{i})) · (1 − ∑_{i=1}^{m} \frac{Ψ_{i}}{Ψ_{i} + Φ_{i}}) = D · [s_{1}^{β_{1}} ⋯ s_{m}^{β_{m}}]Φ_{1}^{n_{1}}(s_{1}) ⋯ Φ_{m}^{n_{m}}(s_{m}),

where D is given by (36), completing the proof. □

The following special cases are particularly useful:

1. α_{1} = α_{2} = ⋯ α_{m} = 1, with the condition that (n − 1)/(m − 1) = p is a positive integer. Then we find that β = p − 1, β_{i} = p − n_{i} and D = p^{m−1}/ ∏_{i=1}^{m} n_{i}, and we have

[x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}]A_{1} ⋯ A_{m} = \frac{p^{m−1}}{∏_{i=1}^{m} n_{i}} · [s_{1}^{p−n_{1}} ⋯ s_{m}^{p−n_{m}}]Φ_{1}^{n_{1}}(s_{1}) ⋯ Φ_{m}^{n_{m}}(s_{m}).  (41)

2. α_{1} = 0, α_{2} = ⋯ α_{m} = k ≥ 1, with the condition that (∑_{i} a_{i})/(m − 1) = q is an integer. Then we find that β = q − k, β_{1} = q − a_{1} − k, β_{i} = q − a_{i}, for i = 2, ⋯ m, and that D = q^{m−2}k/ ∏_{i≠1} a_{i}, and we have, writing Â_{1} = A_{2}A_{3} ⋯ A_{m},

[x_{1}^{a_{1}} ⋯ x_{m}^{a_{m}}]Â_{1}^{k}(x) = \frac{q^{m−2}k}{∏_{i≠1} a_{i}} · [s_{1}^{q−a_{1}−k}s_{2}^{q−a_{2}} ⋯ s_{m}^{q−a_{m}}]Φ_{1}^{a_{1}}(s_{1}) ⋯ Φ_{m}^{a_{m}}(s_{m}).  (42)

3. Under the condition that (∑_{i} a_{i})/(m − 1) = q is an integer, it follows from (42) that for any formal power series F (s) we have

[x_{1}^{a_{1}} ⋯ x_{m}^{a_{m}}]F (Â_{1}) = \frac{q^{m−2}}{∏_{i≠1} a_{i}} · [s_{1}^{q−a_{1}−1}s_{2}^{q−a_{2}} ⋯ s_{m}^{q−a_{m}}]F′(s_{1})Φ_{1}^{a_{1}}(s_{1}) ⋯ Φ_{m}^{a_{m}}(s_{m}). (43)

4 Enumeration of m-ary cacti

4.1 Labeled m-ary cacti with given vertex-color distribution

Let n⃗ = (n_{1}, n_{2}, ⋯, n_{m}) be a vector of nonnegative integers and set n = ∑_{i} n_{i}. We say that a cactus c has vertex-color distribution n⃗ if c has n_{i} vertices of color i, for i = 1, ⋯, m.

Lemma 1 There exists an m-ary cactus having vertex distribution n⃗ if and only if

1. p = (n − 1)/(m − 1) is an integer,

2. p ≥ 1 ⇒ n_{i} ≤ p, for i = 1, ⋯, m.

Proof: The conditions are clearly necessary since in any m-ary cacti we have n = (m − 1)p + 1, where p is the number of polygons.

Sufficiency is proved by induction on p. If p = 0, then n = 1, and we have a 1-vertex cactus. If p ≥ 1, then all components of n⃗ are strictly positive since otherwise, supposing for example that n_{1} = 0, we find

n = ∑_{i=2}^{m} n_{i} ≤ (m − 1)p = n − 1,

a contradiction. Hence we have n_{i} ≥ 1, for all i. If p = 1, then n_{i} = 1 for all i, and we have a cactus with a single polygon. If p > 1, we must have n_{i} < p for some i, since otherwise n = mp and n = p(m − 1) + 1 leads to a contradiction. Assume, say, n_{m} < p and define a new vector n′ by n′_{m} = n_{m} and n′_{i} = n_{i} − 1 for i = 1, ⋯, m − 1. This vector n′ satisfies the conditions 1 and 2 with (n′ − 1)/(m − 1) = p − 1 and we can apply the induction hypothesis to construct a cactus with vertex distribution n′. It suffices then to add a new polygon to this cactus, attached to any existing vertex of color m to obtain a cactus with vertex-color distribution equal to n⃗. □

Observe that when conditions 1 and 2 are satisfied, then p is the number of polygons and p ≥ 1 ⇒ n_{i} ≥ 1 for all i.

Suppose now that the vector n⃗ = (n_{1}, n_{2}, ⋯, n_{m}) satisfies conditions 1 and 2 of Lemma 1. Let K(n⃗) denote the number of m-ary cacti over the multiset of vertices [n_{1}] + [n_{2}] + ⋯ + [n_{m}], that is, of labeled cacti with vertex-color distribution n⃗. Similarly let K^{◇}(n⃗) denote the number of labeled rooted m-ary cacti with vertex distribution n⃗. Then we have K^{◇}(n⃗) = pK(n⃗) and, for p ≥ 1,

K(n⃗) = \frac{1}{p}K^{◇}(n⃗).  (44)

Thus it suffices to enumerate labeled rooted cacti. Since rooted cacti are asymmetric structures, we have

K^{◇}(n⃗) = (∏_{i=1}^{m} n_{i}!)K̃^{◇}(n⃗),  (45)

where K̃^{◇}(n⃗) is the number of unlabeled rooted cati with vertex-color distribution n⃗. We now compute this number.

Theorem 6 Let n⃗ = (n_{1}, n_{2}, ⋯, n_{m}) be a vector of nonnegative integers satisfying the conditions 1 and 2 of Lemma 1, with p ≥ 1. Then the number of unlabeled rooted m-ary cacti having vertex distribution n⃗ is given by

K̃^{◇}(n⃗) = \frac{1}{p} ∏_{i=1}^{m} \binom{p}{n_{i}}.  (46)

Proof: Recall that K̃^{◇}(x) = K^{◇}(x) = A_{1}(x)A_{2}(x) ⋯ A_{m}(x) and that the A_{i}(x) satisfy functional equation (16). Hence we can use the special case 1 of the Generalized Chottin formula, i.e. (41) with Φ_{i}(s) = L(s) = 1/(1 − s) for all i. Hence we find that

K̃^{◇}(n⃗) = [x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}]A_{1}(x) ⋯ A_{m}(x)
= \frac{p^{m−1}}{∏_{i=1}^{m} n_{i}} ∏_{i=1}^{m}[s_{i}^{p−n_{i}}](1 − s_{i})^{−n_{i}}

= \frac{p^{m−1}}{∏_{i=1}^{m} n_{i}} ∏_{i=1}^{m} \binom{p − 1}{n_{i} − 1},

which implies (46). □

Putting together equations (44)–(46) yields the following:

Corollary 2 If conditions 1 and 2 of lemma 1 are satisfied, the number of labeled m-ary cacti with vertex-color distribution n⃗ = (n_{1}, n_{2}, ⋯, n_{m}) is given by

K(n⃗) = p^{m−2} ∏_{i=1}^{m}(p − n_{i} + 1)^{<n_{i}−1>},  (47)

where x^{<k>} denotes the rising factorial x(x + 1) ⋯ (x + k − 1).

Remark: This extends the formula n_{1}^{<n_{2}−1>}n_{2}^{<n_{1}−1>} for the number of labeled plane bicolored trees with vertex-color distribution (n_{1}, n_{2}) (see formula (2.7) of [13]), to general m ≥ 2.

4.2 Labeled m-ary cacti with given vertex-degree distribution

To find the number K(k⃗) of labeled m-ary cacti having vertex degree distribution k⃗ = (k_{ij}), where i = 1, ⋯, m and j ≥ 0, a similar approach can be followed. As we mentioned in the introduction, we have

K(k⃗) = \frac{n_{1}! ⋯ n_{m}!}{p}K̃^{◇}(k⃗).  (48)

Theorem 7 Goulden and Jackson [8]. Let k⃗ = (k_{1}, ⋯, k_{m}) be a vector of sequences of nonnegative integers satisfying the coherence conditions (1)–(3), with p ≥ 1. Then

K̃^{◇}(k⃗) = \frac{p^{m−1}}{∏_{i=1}^{m} n_{i}} ∏_{i=1}^{m} \binom{n_{i}}{k_{i}} = G̃(k⃗).  (49)

Proof: Recall that K_{w}^{◇}(x) = K̃_{w}^{◇}(x) = ∏_{i=1}^{m} A_{i,r}(x) and also recall equations (26). Again, we use the generalized Chottin formula (41), with

Φ_{i}(s) = Ψ_{r_{i}}(s) := r_{i1} + r_{i2}s + r_{i3}s^{2} + ⋯  (50)

Then we have

K̃_{w}^{◇}(k⃗) = [∏_{i,j} r_{ij}^{k_{ij}}][∏_{i} x_{i}^{n_{i}}]K_{w}^{◇}(x) = \frac{p^{m−1}}{∏_{i} n_{i}} [∏_{i,j} r_{ij}^{k_{ij}}][∏_{i} s_{i}^{p−n_{i}}] ∏_{i=1}^{m} Φ_{i}^{n_{i}}(s_{i}).  (51)

which implies (49). □

Corollary 3 The number K(k⃗) of labeled m-ary cacti having vertex degree distribution k⃗, assuming that conditions (1)–(3) are satisfied, with p ≥ 1, is given by

K(k⃗) = p^{m−2} ∏_{i=1}^{m}(n_{i} − 1)!\binom{n_{i}}{k_{i}}.  (52)

4.3 Unlabeled m-ary cacti

In order to compute the numbers K̃(n⃗) and K̃(k⃗) of unlabeled m-ary cacti having vertex-color distribution n⃗ and vertex degree distribution k⃗, we use formulae (21) and (31), respectively. We then have

K̃(n⃗) = ∑_{i=1}^{m} K̃^{•_{i}}(n⃗) − (m − 1)K̃^{⋄}(n⃗),  (53)

K̃(k⃗) = ∑_{i=1}^{m} K̃^{•_{i}}(k⃗) − (m − 1)G̃(k⃗),  (54)

where

K̃^{•_{i}}(n⃗) = [x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}]K̃^{•_{i}}[x]
K̃^{•_{i}}(k⃗) = [∏ r_{ij}^{k_{ij}}][∏ x_{i}^{n_{i}}]K̃_{w}^{•_{i}}[x]

are the numbers of unlabeled m-ary cacti pointed at a vertex of color i and having distributions n⃗ and k⃗, respectively.

For reasons of symmetry, it is sufficient to consider the case i = 1.

4.3.1 Vertex-color distribution

Theorem 8 Let n⃗ = (n_{1}, ⋯, n_{m}) be a vector of nonnegative integers satisfying the conditions 1 and 2 of lemma 1, with p ≥ 1. Then we have

K̃^{•_{1}}(n⃗) = \frac{p − n_{1} + 1}{p^{2}} ∑_{d|(n⃗−e⃗_{1})} ϕ(d) (\begin{matrix}p/d \\ (n_{1} − 1)/d \end{matrix}) ∏_{i≠1} (\begin{matrix}p/d \\ n_{i}/d \end{matrix}) ,  (55)

where e⃗_{1} = (1, 0, ⋯, 0).

Proof: Recall equation (19), with i = 1. In what follows we use the special case 3 of the generalized Chottin formula, i.e. (43), with F (s) = log \frac{1}{1−s} and a_{1} = (n_{1} − 1)/d, a_{2} = n_{2}/d, ⋯,a_{m} = n_{m}/d, so that q = p/d. We find

K̃^{•_{1}}(n⃗) = [x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}](K̃^{•_{1}}(x) − x_{1})
= [x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}]x_{1} ∑_{d≥1} \frac{ϕ(d)}{d} log \frac{1}{1 − Â_{1}(x^{d})}

= [x^{n⃗−e⃗_{1}}] ∑_{d≥1} \frac{ϕ(d)}{d} log \frac{1}{1 − Â_{1}(x^{d})}

= ∑_{d|(p,n⃗−e⃗_{1})} \frac{ϕ(d)}{d}[x^{(n⃗−e⃗_{1})/d}] log \frac{1}{1 − Â_{1}(x)}

= ∑_{d|(p,n⃗−e⃗_{1})} ϕ(d)\frac{p^{m−2}}{∏_{i=2}^{m} n_{i}} · [s1^{\frac{p−n_{1}−d+1}{d}}](\frac{1}{1 − s_{1}} )^{\frac{n_{1}+d−1}{d}} ∏_{i=2}^{m}[si^{\frac{q−n_{i}}{d}}](\frac{1}{1 − s_{i}})^{n_{i}/d}

= ∑_{d|(n⃗−e⃗_{1})} ϕ(d)\frac{p^{m−2}}{∏_{i=2}^{m} n_{i}} \binom{(p − d)/d}{(n_{1} − 1)/d} ∏_{i=2}^{m} \binom{(p − d)/d}{(n_{i} − d)/d},

which is equivalent to (55). □

Replacing i = 1 by i = 2, 3, ⋯, m in (55) yields all K̃^{•_{i}}(n⃗). The following corollary then follows from (53).

Corollary 4 Let n⃗ be as in the previous theorem. Then the number K̃(n⃗) of unlabeled m-ary cacti with vertex degree distribution n⃗ is given by

K̃(n⃗) = ∑_{i=1}^{m} \frac{p − n_{i} + 1}{p^{2}} ∑_{d|(p,n⃗−e⃗_{i})} ϕ(d) \binom{p/d}{(n_{i} − 1)/d} ∏_{j≠i} \binom{p/d}{n_{j}/d} − \frac{m − 1}{p} ∏_{i} \binom{p}{n_{i}}.  (56)
□

\begin{matrix}n⃗ & K̃^{⋄}(n⃗) & K̃(n⃗) \\ (1, 3, 3) & 1 & 1 \\ (2, 3, 3) & 3 & 1 \\ (2, 3, 4) & 6 & 2 \\ (3, 3, 3) & 16 & 4 \\ (3, 3, 5) & 20 & 4 \\ (4, 4, 5) & 225 & 39 \\ (1, 3, 3, 3) & 1 & 1 \\ (2, 2, 3, 3) & 3 & 1 \\ (2, 3, 4, 4) & 6 & 2 \\ (3, 4, 4, 5) & 50 & 10 \\ (4, 4, 4, 4) & 125 & 25 \end{matrix}

Table 2: Unlabeled rooted and unrooted cacti according to their vertex-color distribution.

4.3.2 Vertex-degree distribution

We now prove Theorem 1. In concordance with the notation of the introduction, we write F̃(k⃗) = K̃^{•_{1}}(k⃗). We will use special case 2 of the generalized Chottin formula, i.e. (42), with Φ_{i}(s) = Ψ_{r_{i}^{d}}(s) (see (50)), k = h/d, a_{1} = (n_{1} − 1)/d, a_{2} = n_{2}/d, ⋯ and a_{m} = n_{m}/d, for which q = p/d, and A_{i} = A_{i,r^{d}}. We have, using formula (29) with i = 1, and defining the matrix δ^{1,h} = (δ_{i}^{1} · δ_{j}^{h})_{i,j},

F̃(k⃗) = [∏_{ij} r_{ij}^{k_{ij}}][∏_{i} x_{i}^{n_{i}}](K̃_{w}^{•_{1}}(x) − r_{1,0}x_{1})
= [r^{k}][x^{n}] ∑_{h≥1} \frac{x_{1}r_{1,h}}{h} ∑_{d|h} ϕ(d)Â_{1,r^{d}}^{h/d}(x^{d})

= ∑_{h≥1} \frac{1}{h} · [r^{k−δ^{1,h}}] ∑_{d|(h,n⃗−e⃗_{1})} ϕ(d)[x_{1}^{(n_{1}−1)/d}x_{2}^{n_{2}/d} ⋯ x_{m}^{n_{m}/d}]Â_{1,r^{d}}^{h/d}(x)

= \frac{p^{m−2}}{∏_{i≠1} n_{i}} ∑_{h,d} ϕ(d)[r^{k−δ^{1,h}}][s1^{\frac{p−n_{1}−h+1}{d}}]Ψr_{1}^{d}^{\frac{n_{1}−1}{d}} (s_{1}) ∏_{i≠1}[si^{\frac{p−n_{i}}{d}}]Ψr_{i}^{d}^{\frac{n_{i}}{d}} (s_{i})

= \frac{p^{m−2}}{∏_{i≠1} n_{i}} ∑_{h,d} ϕ(d)[r1^{\frac{k_{1}−δ^{h}}{d}}][s1^{\frac{p−n_{1}−h+1}{d}}]Ψr_{1}^{d}^{\frac{n_{1}−1}{d}} (s_{1}) ∏_{i≠1}[ri^{\frac{k_{i}}{d}}][si^{\frac{p−n_{i}}{d}}]Ψr_{i}^{\frac{n_{i}}{d}} (s_{i})

= \frac{p^{m−2}}{∏_{i≠1} n_{i}} ∑_{d,h} ϕ(d)\binom{(n_{1} − 1)/d}{(k_{1} − δ^{h})/d} ∏_{i=2}^{m} \binom{n_{i}/d}{k_{i}/d},  (57)

where the summation is taken over all ordered pairs (h, d) such that h ∈ Supp(k_{1}) and d divides h, p, k_{1} − δ^{h}, and all k_{i} with i ≥ 2.

For symmetry reasons it is obvious that

K̃^{•_{i}}(k⃗) = F̃(σ^{i−1}k⃗)  (58)

and Theorem 1 then follows from (54), (57) and (49).

5 Related enumerative results

5.1 Unlabeled m-ary cacti according to their automorphisms

Since automorphisms of m-ary cacti are required to preserve colors, the only possible symmetries of an m-ary cacti are rotations around a central vertex. See Figure 6. Let s ≥ 2 be an integer. Let K_{w,≥s} and K_{w,=s} denote the species of m-ary cacti whose automorphism group (necessarily cyclic) is of order a multiple of s, and exactly s, respectively. Then, following the notation of [13], section 3, we have

K_{w,≥s} = ∑_{i=1}^{m} X_{i}C_{r_{i},≥s}(Â_{i,r}),  (59)

K_{w,=s} = ∑_{i=1}^{m} X_{i}C_{r_{i},=s}(Â_{i,r})  (60)

We can determine the unlabeled generating series K̃_{w,≥s}(x) and K̃_{w,=s}(x) by formulas (3.2) and (3.3) of [13], essentially due to Stockmeyer. See [1], Exercise 4.4.16, and [17]. Extracting coefficients in these series is similar to the computations of subsection 4.3. We find the following.

Proposition 2 Let s ≥ 2 and p ≥ 1 be integers, and k⃗ = (k_{1}, k_{2}, ⋯, k_{m}) be an m-tuple of sequences of intergers satisfying the coherence conditions (1)–(3) with n_{i} = ∑_{j≥0} k_{ij} and n = ∑_{i} n_{i}. Then the numbers K̃_{≥s}(k⃗) and K̃_{=s}(k⃗) of unlabeled m-ary cacti with vertex degree distribution k⃗, and automorphism group of order a multiple of s, and exactly s, respectively, are given by

K̃_{≥s}(k⃗) = F̃_{≥s}(k⃗) + F̃_{≥s}(σk⃗) + ⋯ + F̃_{≥s}(σ^{m−1}k⃗),  (61)

and

K̃_{=s}(k⃗) = F̃_{=s}(k⃗) + F̃_{=s}(σk⃗) + ⋯ + F̃_{=s}(σ^{m−1}k⃗),  (62)

where

F̃_{≥s}(k⃗) = \frac{p^{m−2}s}{∏_{j≠1} n_{j}} ∑_{h,d} ϕ(d/s)\binom{(n_{1} − 1)/d}{(k_{1} − δ^{h})/d} ∏_{j≠1} \binom{n_{j}/d}{k_{j}/d}  (63)

and

F̃_{=s}(k⃗) = \frac{p^{m−2}s}{∏_{j≠1} n_{j}} ∑_{h,d} μ(d/s)\binom{(n_{1} − 1)/d}{(k_{1} − δ^{h})/d} ∏_{j≠1} \binom{n_{j}/d}{k_{j}/d},  (64)

the sum being taken over all pairs of integers p, d ≥ 1 such that h ∈ Supp(k_{1}), s|d, and d ∈ Div(h, k⃗ − δ^{1,h}). □.

Figure 6: A ternary cactus with a symmetry of order 3.

Similar but simpler computations yield the following for the vertex color distribution.

Proposition 3 Let s ≥ 2 be an integer, and let n⃗ = (n_{1}, ⋯, n_{m}) be a vector of positive integers satisfying conditions 1 and 2 of Lemma 1. Then the numbers K̃_{≥s}(n⃗) and K̃_{=s}(n⃗) of unlabeled m-ary cacti with vertex-color distribution n⃗ and automorphism group of order a multiple of s, and exactly s, respectively, are given by

K̃_{≥s}(n⃗) = ∑_{i=1}^{m} \frac{s(p − n_{i} + 1)}{p^{2}} ∑_{d} ϕ(d/s)\binom{p/d}{(n_{i} − 1)/d} ∏_{j≠i} \binom{p/d}{n_{j}/d},  (65)

K̃_{=s}(n⃗) = ∑_{i=1}^{m} \frac{s(p − n_{i} + 1)}{p^{2}} ∑_{d} μ(d/s)\binom{p/d}{(n_{i} − 1)/d} ∏_{j≠i} \binom{p/d}{n_{j}/d},  (66)

the second summations being taken over all integers d such that s|d and d ∈ Div(p, n⃗ − e⃗_{i}). □

5.2 Free (labeled) m-ary cacti

A free m-ary cactus can be informally defined as an m-ary cactus without the plane embedding. In other words, the m-gons attached to a vertex are free to take any position with respect to each other. Denoting by F the species of free m-ary cacti , we have the functional equations

F^{◇} = A_{1}A_{2} ⋯ A_{m},  (67)

and, for i = 1, 2, ⋯, m,

A_{i} = X_{i}E(Â_{i}),  (68)

where E denotes the species of sets, for which

E(x) = e^{x}, Ẽ(x) = (1 − x)^{−1} and Z_{E}(x_{1}, x_{2}, ⋯) = e^{(∑_{i≥1} x_{i}/i)}.

The computations of subsection 4.1 for labeled m-ary cacti according to vertex-color distribution can be easily adapted to free m-ary cacti . We then find the following result.

Proposition 4 Let n⃗ = (n_{1}, ⋯, n_{m}) be a vector of positive integers satisfying conditions 1 and 2 of Lemma 1. Then the number F(n⃗) of labeled free m-ary cacti having vertex-color distribution n⃗ is given by

F(n⃗) = p^{m−2} ∏_{i=1}^{m} \frac{(n_{i} − 1)!n_{i}^{p−n_{i}}}{(p − n_{i})!} ,  (69)

where p = (∑_{i} n_{i} − 1)/(m − 1) is the number of polygons.

This extends Scoins formula n_{1}^{n_{2}−1}n_{2}^{n_{1}−1} for the number of labeled bicolored free trees with vertex-color distribution (n_{1}, n_{2}) to general m ≥ 2.

5.3 Rooted m-ary cacti and constellations having p polygons.

There is a bijection between cacti and special (m + 1)-colored plane trees obtained by replacing each m-gon by an m-star, that is a black vertex (black is the new color) joined to all the vertices of the polygon. In the resulting structure, each black vertex has degree m. We consider the color 1 to m as different shades of white (colors 1_{w} to m_{w}) and we call these structures m-ary bicolored trees. See Figure 7 for an illustration of this bijection when m = 3.

Figure 7: Bijection between ternary cacti and ternary bicolored trees.

If, as in Figure 7, the m-ary cactus is rooted, the distinguished polygon becomes a distinguished star. In this case, the information on the m-coloring and the rooting can be simply encoded by pointing the edge in the distinguished star joining the black vertex to the vertex with color 1_{w}. Hence, a rooted m-ary bicolored tree is simply a bicolored plane tree which is rooted (i.e. has a distinguished edge) and all of whose black vertices have degree m. See Figure 8. If moreover the m-ary cactus had p polygons, the associated m-ary bicolored tree will have p black vertices (of degree m) and (m − 1)p + 1 white vertices. Since we know how to enumerate plane bicolored trees according to degree and color distributions, we obtain the following result, using (51) with m = 2 and r_{2} = 1, or (2.8) of [13].

Figure 8: Rooted ternary bicolored tree.

Proposition 5 The number K̃^{⋄}(p) of (unlabeled) rooted m-ary cacti having p polygons is given by

K̃^{⋄}(p) = \frac{1}{(m − 1)p + 1} = (\begin{matrix}mp \\ p \end{matrix}) .  (70)
□

It is a well known fact that this last expression also represents the number of (unlabeled) m-ary ordered rooted trees having p vertices. A direct bijection can be given between these two classes of structures; see [2].

Figure 9: A rooted ternary constellation.

Another combinatorial object closely related to m-ary cacti is an m-ary constellation which is defined in a similar way as an m-ary cactus or a m-ary bicolored tree except that cycles of polygons are now allowed. Figure 9 shows a typical ternary constellation which is rooted, that is, has a distinguished star (or polygon). M. Bousquet-Mélou and G. Schaeffer [3] have found that the number C̃^{⋄}(p) of unlabeled rooted m-ary constellations having p polygons is given by

C̃^{⋄}(p) = \frac{(m + 1)m^{p−1}}{((m − 1)p + 2)((m − 1)p + 1)} (\begin{matrix}mp \\ p \end{matrix}) .  (71)

References

[1] F. Bergeron, G. Labelle, P. Leroux. Combinatorial species and tree-like structures, Encyclopedia of Mathematics and its Applications, Cambridge University Press, 1997.

[2] M. Bousquet. Opérations combinatoires sur les espèces de structures et applications, Thèse de doctorat, UQAM, 1998, (in preparation).

[3] M. Bousquet-Mélou, G. Schaeffer. Enumeration of planar constellations (in preparation).

[4] L. Chottin. Une démonstration combinatoire de la formule de Lagrange à deux variables, Discrete Math. 13, (1975), no. 3, 215–224.

[5] L. Chottin. Énumération d’arbres et formules d’inversion de séries formelles, J. Combin. Theory Ser. B, 31, (1981), no. 1, 23–45.

[6] M. El Marraki, N. Hanusse, J. Zipperer, A. Zvonkin. Cacti, Braids and Complex Polynomials, Séminaire Lotharingien de Combinatoire, (1997), Vol. 37, url address: http://cartan.u-strasbourg.fr/∼slc.

[7] I. P. Goulden, D. M. Jackson. Combinatorial Enumeration, John Wiley and Sons, New York, (1983).

[8] I. P. Goulden, D. M. Jackson, The Combinatorial Relationship Between Trees, Cacti and Certain Connection Coefficients for the Symmetric Group, European J. Comb. 13, (1992), 357–365.

[9] F. Harary, R. Z. Norman. Dissimilarity characteristic of Husimi trees, Ann. of Math. 58, (1953), 134-141.

[10] F. Harary, G. Palmer. Graphical Enumeration, Academic Press, New York, 1973.

[11] F. Harary, G. E. Uhlenbeck. On the number of Husimi trees, Proc. Nat. Acad. Sci. U.S.A, 39, (1953), 315-322.

[12] K. Husimi. Note on Mayer’s theory of cluster integrals, J. Chem. Phys, 18, (1950), 682-684.

[13] G. Labelle, P. Leroux. Enumeration of (uni- or bicolored) plane trees according to their degree distribution, Discrete Mathematics 157, (1996), 227–240.

[14] R. J. Riddell. Contributions to the theory of condensation, Dissertation, Univ. of Michigan, Ann Arbor, 1951.

[15] H. I. Scoins. The number of trees with nodes of alternate parity, Proc. Cambridge Philos. Soc. 58, (1962), 12-16.

[16] J. Sherman, W. J. Morrison. Adjustments of an inverse matrix corresponding to changes in the elements of a given row or a given column of the original matrix, Ann. Math. Stat., 20 (1949), 621.

[17] P. K. Stockmeyer. Enumeration of Graphs with Prescribed Automorphism Group, University of Michigan, Ann Arbor, (1971).

[18] G. E. Uhlenbeck, G. W. Ford. Lectures in Statistical Mechanics, Amer. Math. Soc. Providence, Rhode Island, 1963.