Enumeration by Stabilizer Class of Patterns with Local Restrictions

Ifor Morris and Christopher D. Wensley

School of Mathematics University of Wales, Bangor Gwynedd LL57 1UT, U.K.

                        i.morris/c.d.wensley@bangor.ac.uk

Submitted: May 24, 1996; Accepted: July 29, 1996.

Abstract

We consider patterns of colourings of G-sets where certain forbidden sub-colourings are excluded. An algorithm is developed for the calculation of inventories of patterns with a prescribed stabilizer class.

1 Introduction

The theory of pattern enumeration is concerned with a finite group G acting as the group of symmetries of a set X, a set of colours C, and the action of G on the set C^{X} of colourings of X. By a pattern we mean the G-orbit of a colouring.

Williamson [6] used a combination of the inclusion - exclusion rule with Redfield/Pólya theory to enumerate patterns of colourings which do not contain colourings of specified subsets of X using chosen subsets of C. The aim of this note is to enumerate the subset of these patterns which are stabilized by a chosen conjugacy class of subgroups of G.

We use two examples to illustrate the main features of the method. Firstly we discuss a particular example used by Williamson which involves the enumeration of patterns of 8-bead necklaces that do not include particular sub-colourings called a-rooted trees. A second example is taken from the counting of isomers in chemical enumeration. We consider colourings of the 8 vertices of a trigonal dodecahedron in which the vertices are of two types, 4-valent and 5-valent, and such that adjacent vertices have different colours. The additional feature here is that excluded colourings may be constructed in different ways from sets of forbidden sub-colourings.

1991 Mathematics Subject Classification: 05A15, 05E05.

Keywords: pattern enumeration, inventory, subgroup lattice, isomer.

We end by writing down a general algorithm for enumerating inventories of patterns which exclude an arbitrary number of sub-colourings that are specified using an arbitrary partition of the set of colours.

2 Pattern enumeration

We first recall some of our notation and results from [4] and [5]. Enumeration by stabilizer class using tables of marks is also discussed in detail in Chapter 3 of [1].

Denote by L_{G} and P_{G} the subgroup lattice and the poset of conjugacy classes [H] of subgroups of a group G. Let A be a commutative algebra over the rationals. The incidence algebra AIA(L_{G}) has a subalgebra ACA(L_{G}) of conjugacy functions satisfying

f(H, K) = f(g^{−1}Hg, g^{−1}Kg) for all H, K ≤ G and g ∈ G.

There is an algebra homomorphism from ACA(L_{G}) to AIA(P_{G}) which maps f to f̌ where

f̌([H], [K]) = ∑_{K′∈K} f(H, K′).

Let ζ be the zeta function on L_{G} with inverse the Möbius function μ, and let γ be the conjugacy diagonal function defined by γ(K) = |G| / |K| |[K]|. The mark function ϕ ∈ AIA(P_{G}), where ϕ([H], [K]) is the number of left cosets in (G/K) fixed under left multiplication by H, has a factorisation ϕ = ζ̌γ. When a total ordering of the classes [K] has been chosen, compatible with the partial order on P_{G}, the marks form an upper triangular matrix M(ϕ), known as the table of marks of G, whose inverse is the Burnside matrix M(ϕ^{−1}).

Given a diagonal conjugacy function Δ on L_{G} we obtain τ̌ from α and τ where

α = μΔζ, τ = γ^{−1}αγ, τ̌ = ϕ^{−1}Δϕ.  (1)

The values α(H, K) may be calculated successively, working downwards from K using the intervals [H, K], by the formulae

α(K, K) = Δ(K), ∑_{H≤J≤K} α(H, J) = 0 when H ≠ K.  (2)

In the case K = G,

τ̌([H], [G]) = α(H, G)/γ(H).  (3)

We now summarise the basic ingredients of generalised Redfield/Pólya enumeration (see, for example, [1], Chapter 2, or [5], Section 5). Let G be a subgroup of the symmetric group S_{n} and let A = Λ_{ℓ} ⊗ ℚ where Λ_{ℓ} is the ring of symmetric polynomials in a set of indeterminates Ξ_{ℓ} = {ξ_{1}, ξ_{2}, …, ξ_{ℓ}}, generated by the power sums p_{d} = ∑_{i=1}^{ℓ} ξ_{i}^{d}. When we wish to consider two sorts of indeterminates, we write Ξ_{ℓ} = {η_{1}, …, η_{j}, θ_{1}, …, θ_{k}}, j + k = ℓ, and we denote by q_{d}, r_{d} the power sums in η_{i}, θ_{i} respectively, so that p_{d} = q_{d} + r_{d} for all d ≥ 1.

Let V be a G-set and w : V → A a weight function. The weight of a subset U ⊆ V is defined to be w(U) = ∑_{u∈U} w(u). For g ∈ G and H ≤ G we denote the weights of the fixed point subsets Fix_{V} (g) and Fix_{V} (H) by w(V, g) and w(V, H) respectively. If Ω is a transversal for the set of orbits V/G and w is constant on each orbit, the inventory of V is w(Ω). Each g ∈ G determines a partition π_{g} = (n^{m_{n}} … 2^{m_{2}}1^{m_{1}}) of n, in which the parts are the lengths of the disjoint cycles, and hence a symmetric function

p_{g} = p_{n}^{m_{n}} … p_{2}^{m_{2}}p_{1}^{m_{1}} = w(V, g) ∈ Λ_{ℓ},

the combined weight of all the elements fixed by g. The Cauchy-Frobenius Lemma states that

w(Ω) = \frac{1}{|G|} ∑_{g∈G} p_{g}.

Similarly, each subgroup H of G determines a partition π_{H} = (π_{1}, π_{2}, …, π_{h}) ⊢ n, in which the parts are the lengths of the orbits, and hence a symmetric function

p_{H} = p_{π_{1}}p_{π_{2}} … p_{π_{h}} = w(V, H) ∈ Λ_{ℓ},

the weight of all the elements fixed by H.

Defining Δ_{p} ∈ ACA(L_{G}), H ↦ p_{H}, we obtain by (1)

τ̌_{p} = ϕ^{−1}Δ_{p}ϕ ∈ AIA(P_{G}).

(The matrix M(τ̌_{p}) is the transition matrix between β-operations and λ-operations of degree n in a β-ring (see [5], Corollary 5.2).)

Let V_{[H]} be the subset of V whose elements have stabilizer class [H] and let Ω_{[H]} be a transversal for V_{[H]}/G. The [H]-inventories w(Ω_{[H]}) of V may be obtained by multiplying the vector whose elements are the values of Δ_{p} by the Burnside matrix ([1], Section 3.3). Since this vector forms the final column of the matrix M(Δϕ), these inventories are the entries τ̌_{p}([H], [G]) in the last column of M(τ̌_{p}).

Now let X be an n-element G-set, let C = {c_{1}, c_{2}, …, c_{ℓ}} be a set of colours and let w_{C} : C → A, c_{i} ↦ ξ_{i} be a weight function on the colours. The set V = C^{X} of colourings of X has weight function

w : V → A, χ ↦ ∏_{x∈X} w_{C}(χ(x)).

Pólya’s fundamental theorem states that the inventory of V is the cycle index

Cyc(G; p_{1}, p_{2}, …, p_{n}) = \frac{1}{|G|} ∑_{g∈G} p_{g} ∈ A.

3 Williamson’s example

Given a set X = {1, 2, …, 8} of 8 beads on a circular necklace, consider the set V_{0} = C^{X} of colourings of the beads using a set of colours C = A ∪ B, A = {a_{1}, a_{2}, …, a_{j}}, B = {b_{1}, b_{2}, …, b_{k}}, A ∩ B = ∅. The dihedral group D_{16} acts as the group of symmetries of the uncoloured necklace and has cycle index, expressed as a polynomial in j = |A|, k = |B|:

Cyc(D_{16}, {j, k}) = j^{8} + j^{7}k + 4j^{6}k^{2} + 5j^{5}k^{3} + 8j^{4}k^{4} + 5j^{3}k^{5} + 4j^{2}k^{6} + jk^{7} + k^{8}.

There are 30 patterns when j = k = 1; 987 patterns when j = 2 and k = 1; and 7680 patterns when j = k = 2.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; I; C′_{2}; C_{2}; C′′_{2}; K′; C_{4}; K′′; D′_{8}; C_{8}; D′′_{8}; D_{16}; (p_{1}^{8} − 4p_{2}^{3}p_{1}^{2} − 5p_{2}^{4} + 4p_{4}p_{2}^{2} + 4p_{4}^{2})/16; (p_{2}^{4} − 2p_{4}p_{2}^{2} − p_{4}^{2} + 2p_{8})/8; (p_{2}^{3}p_{1}^{2} − p_{4}p_{2}^{2})/2; (p_{2}^{4} − p_{4}^{2})/2; (p_{4}p_{2}^{2} − p_{4}^{2})/2; 0; (p_{4}^{2} − p_{8})/2; 0; 0; p_{8}; (1^{8}); (2^{3}1^{2}); (42^{2}); (4^{2}); (1^{8}); (2^{4}); (4^{2}); (8); (p_{4}^{2} − p_{8})/2; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·]
Figure 1: Subgroup Lattice of D_{16} and values τ̌_{p}([H], [D_{16}]).

A Hasse diagram for the subgroup lattice of D_{16} is shown in Figure 1, where horizontal dashed lines join the subgroups in a conjugacy class [H]. The class [C′_{2}] , (resp. [C′′_{2}] ) contains those reflections whose axis does (resp. does not) pass through a pair of beads. Dotted lines partition the lattice of D_{16} into subposets in which the subgroups have constant orbit type π_{H} ⊢ 8. The poset formed by these regions is isomorphic to the subposet {π_{H} |H ≤ D_{16}} of the poset of all partitions of 8. Values τ̌_{p}([H], [D_{16}]) are shown for each conjugacy class [H]. Note that τ̌_{p}([H], [D_{16}) = 0 when the subgroups in [H] are not maximal in the subposet of type π_{H}.

Summing over all subgroup classes, we obtain the cycle index:

∑_{H≤D_{16}} τ̌_{p}([H], [D_{16}]) = Cyc(D_{16}; p_{1}, …, p_{8}) = \frac{1}{16}(p_{1}^{8} + 4p_{2}^{3}p_{1}^{2} + 5p_{2}^{4} + 2p_{4}^{2} + 4p_{8}).

When Δ is an arbitrary diagonal function, constant on these subposets, the non-zero values of τ̌([H], [D_{16}]) are given in Table 1.

H τ̌([H], [D_{16}])
D_{16} Δ(D_{16})
D′_{8} (Δ(D′_{8}) − Δ(D_{16}))/2
K′′ (Δ(K′′) − Δ(D_{16}))/2
K′ (Δ(K′) − Δ(D′_{8}))/2
C′′_{2} (Δ(C′′_{2}) − Δ(K′′))/2
C′_{2} (Δ(C′_{2}) − Δ(K′))/2
C_{2} (Δ(C_{2}) − 2Δ(K′) − 2Δ(K′′) + Δ(D′_{8}) + 2Δ(D_{16}))/8
I (Δ(I) − Δ(C_{2}) − 4Δ(C′_{2}) − 4Δ(C′′_{2}) + 4Δ(K′) + 4Δ(K′′))/16

Table 1: Values of τ̌ for arbitrary Δ.

Williamson’s problem was to determine the number of patterns which do not contain an a-rooted tree, namely a coloured subpattern of the form marked in Figure 2.

[figure: ∗; •; ∗; •; ∗; ∗; ∘; ∗; ∘ ∈ A, • ∈ B, ∗ ∈ C = A ∪ B]

Figure 2: A necklace containing an a-rooted tree.

In the case ℓ = 2, Ξ = {η, θ}, rewriting the τ̌_{p}([H], [D_{16}]) we obtain symmetric functions in η and θ as listed in Table 2. The 30 monomials correspond to the 30 colourings of the necklace with the set {a, b}. Just 13 of these have no a-rooted tree ([6], Figure 4).

Let P = {P_{1}, P_{2}, …, P_{8}} be the set of properties such that χ ∈ V_{0} satisfies P_{i} if χ contains an a-rooted tree with bead i as root. For Q ⊆ P let

V_{Q} = {χ ∈ V_{0} | χ satisfies P_{i} for all P_{i} ∈ Q}.

\begin{matrix}(8) & D_{16} & η^{8} + θ^{8} \\ (4^{2}) & D′_{8} & η^{4}θ^{4} \\ (4^{2}) & K′′ & η^{4}θ^{4} \\ (42^{2}) & K′ & η^{6}θ^{2} + η^{2}θ^{6} \\ (2^{4}) & C′′_{2} & 2(η^{6}θ^{2} + η^{2}θ^{6}) + 2η^{4}θ^{4} \\ (2^{3}1^{2}) & C′_{2} & (η^{7}θ + ηθ^{7}) + (η^{6}θ^{2} + η^{2}θ^{6}) + 3(η^{5}θ^{3} + η^{3}θ^{5}) + 2η^{4}θ^{4} \\ (1^{8}) & I & 2(η^{5}θ^{3} + η^{3}θ^{5}) + 2η^{4}θ^{4} \end{matrix}

Table 2: Non-zero values of τ̌_{p}([H], [D_{16}]) when ℓ = 2 (30 terms).

We represent the elements of V_{Q} by colourings having a marked a-rooted tree at each bead i for which P_{i} ∈ Q. If V_{f} is the set of colourings with no a-rooted tree then, using the principle of inclusion-exclusion, we define Δ_{f} ∈ ACA(L_{G}) by

Δ_{f}(H) = w(V_{f}, H) = ∑_{Q⊆P}(−1)^{|Q|} w(V_{Q}, H).  (4)

If a colouring χ contains e a-rooted trees, then χ belongs to 2^{e} of the subsets V_{Q} and, if fixed by H, contributes (1 − 1)^{e} = 0 to the sum (4). Only 47 of the 256 subsets V_{Q} are non-empty. For example, V_{{P_{1},P_{4}}} = ∅ since properties P_{1} and P_{4} require beads 1 and 4 to be coloured with both A and B.

The first stage of the solution is to produce a complete set of marked template patterns T_{t} containing all possible arrangements of one or more a-rooted trees, modulo the group action. Such templates may be considered as patterns using {a, b, c} as the set of colours: beads in the marked trees are coloured a (for the root) or b, the remaining beads are coloured c. In simple cases the templates can be found by inspection. In general, Williamson’s multilinear techniques ([6], Section 2) may be used to construct them.

[figure: T_{4}; ∗; •; ∘; •; ∗; •; ∘; •; a; a; T_{5}; ∘; •; •; •; •; •; ∘; ∘; a; a; a; T_{6}; ∘; •; ∗; •; ∘; •; ∘; •; a; a; a; T_{7}; ∘; •; ∘; •; ∘; •; ∘; •; a; a; a; a; T_{0}; ∗; ∗; ∗; ∗; ∗; ∗; ∗; ∗; T_{1}; ∗; •; ∗; •; ∗; ∗; ∘; ∗; a; T_{2}; ∗; •; •; •; •; ∗; ∘; ∘; a; a; T_{3}; ∘; •; ∗; •; ∗; •; ∘; ∗; a; a]

Figure 3: The 8 template patterns T_{t}.

The 8 templates for our example are shown in Figure 3, where ∘, •, ∗ denote vertices coloured a, b, c respectively. Since an a-rooted tree is uniquely determined by the location of its root, we mark each tree by placing an a next to the root bead. Denoting by ν_{t} the number of a-rooted trees in T_{t}, we have ν_{0} = 0, ν_{1} = 1, ν_{2} = ν_{3} = ν_{4} = 2, ν_{5} = ν_{6} = 3 and ν_{7} = 4.

The stabilizer classes for these templates are given in Table 3.

Template T_{0} T_{1} T_{2} T_{3} T_{4} T_{5} T_{6} T_{7}
Size of orbit  1 8 8 8 4 8 8 2
Stabilizer class D_{16} C′_{2} C′′_{2} C′_{2} K′ C′_{2} C′_{2} D′_{8}

Table 3: Stabilizers of the templates.

For ψ a template colouring in T_{t}, partition X into subsets X_{ψa}, X_{ψb}, X_{ψc} of beads coloured a, b, c respectively. A marked colouring of type T_{t} is obtained by recolouring the beads in X_{ψa}, X_{ψb}, X_{ψc} with colours from A, B, C respectively. If V_{t} denotes the set of marked colourings of type T_{t} then

|V_{t}| = |T_{t}| j^{|X_{ψa}|} k^{|X_{ψb}|} ℓ^{|X_{ψc}|}.

Since these template colourings include exactly the 47 non-empty V_{Q}, equation (4) may be rewritten as

Δ_{f}(H) = ∑_{t=0}^{7}(−1)^{ν_{t}} w(V_{t}, H).  (5)

In our example |V_{1}| = 8jk^{2}ℓ^{5} so when j = k = 1 there are 256 colourings with a single marked a-rooted tree. These colourings form 30 marked patterns and in Figure 4 we give a transversal for V_{1}/D_{16}, where ∼ indicates different markings of the same colouring. (It is a coincidence that V_{0}/D_{16} contains 30 patterns and V_{1}/D_{16} contains 30 marked patterns.)

Redefine the weight of each colour by

w_{C} : C → A, a_{i} ↦ η_{i} (1 ≤ i ≤ j), b_{i} ↦ θ_{i} (1 ≤ i ≤ k).

Let Ω_{t} be a transversal for the patterns V_{t}/D_{16}. For each class [H] we require the [H]- inventory w(Ω_{t}) as a polynomial in the power sums p_{d}, q_{d} and r_{d}. Let X/H = {O_{1}, …, O_{h}} and let the orbit O_{i} contain d_{i} beads. Let V_{ψ} be the set of marked colourings of type T_{t} obtained from ψ ∈ T_{t}. Just as p_{H} is a product of power sums, one for each orbit, so the total weight w(V_{ψ}, H) of colourings fixed by H is a product of h factors. If O_{i} contains a bead coloured a and a bead coloured b then Fix_{V_{ψ}}(H) is empty and w(V_{ψ}, H) = 0. If O_{i} contains only vertices in X_{ψc} then O_{i} contributes a factor p_{d_{i}} = (q_{d_{i}} +r_{d_{i}}). If O_{i} only contains vertices from X_{ψa} ∪X_{ψc} (resp. X_{ψb} ∪X_{ψc}) then O_{i} contributes q_{d_{i}} (resp. r_{d_{i}}). We thus obtain Δ_{t} ∈ AIA(P_{G}) where

Δ_{t}([H]) = w(V_{t}, H) = ∑_{ψ∈T_{t}} w(V_{ψ}, H) ∈ A.  (6)

the electronic journal of combinatorics 3 (1996), #R28 8

[figure: C′_{2}; •; ∘; •; •; •; •; •; ∘; a; ∼; C′_{2}; •; ∘; •; •; •; •; •; ∘; a; K′; •; ∘; •; •; •; ∘; •; •; a; ∼; K′; •; ∘; •; •; •; ∘; •; •; a; C′_{2}; •; ∘; •; •; •; •; •; •; a; C′_{2}; •; ∘; •; •; •; ∘; •; ∘; a; ∼; C′_{2}; •; ∘; •; •; •; ∘; •; ∘; a; ∼; C′_{2}; •; ∘; •; •; •; ∘; •; ∘; a; C′′_{2}; ∘; ∘; •; •; •; •; •; •; a; ∼; C′′_{2}; ∘; ∘; •; •; •; •; •; •; a; C′_{2}; ∘; ∘; •; •; •; •; •; ∘; a; ∼; C′_{2}; ∘; ∘; •; •; •; •; •; ∘; a; ∼; C′_{2}; ∘; ∘; •; •; •; •; •; ∘; a; I; ∘; ∘; •; •; •; •; ∘; •; a; I; ∘; ∘; •; •; •; ∘; •; •; a; I; ∘; •; •; ∘; •; ∘; •; ∘; a; D′_{8}; •; ∘; •; ∘; •; ∘; •; ∘; a; ∼; D′_{8}; •; ∘; •; ∘; •; ∘; •; ∘; a; ∼; D′_{8}; •; ∘; •; ∘; •; ∘; •; ∘; a; ∼; D′_{8}; •; ∘; •; ∘; •; ∘; •; ∘; a; C′′_{2}; ∘; ∘; •; •; •; •; ∘; ∘; a; ∼; C′′_{2}; ∘; ∘; •; •; •; •; ∘; ∘; a; I; ∘; ∘; •; •; •; ∘; •; ∘; a; ∼; I; ∘; ∘; •; •; •; ∘; •; ∘; a; C′_{2}; ∘; ∘; •; •; ∘; •; •; ∘; a; C′_{2}; ∘; ∘; •; ∘; •; ∘; ∘; ∘; a; C′_{2}; ∘; ∘; •; •; •; ∘; ∘; ∘; a; I; ∘; •; •; ∘; •; ∘; ∘; ∘; a; C′_{2}; •; ∘; •; ∘; •; ∘; ∘; ∘; a; ∼; C′_{2}; •; ∘; •; ∘; •; ∘; ∘; ∘; a]

Figure 4: The 30 marked patterns of type T_{1} and their stabilizer classes.

Reversing the order of summation in ∑_{H′∈[H]} ∑_{ψ∈T_{t}} w(V_{ψ}, H′), we obtain an alternative formula

Δ_{t}([H]) = \frac{|T_{t}|}{|[H]|} ∑_{H′∈[H]} w(V_{ψ}, H′),  (7)

which is more convenient when the size of [H] is small compared with that of T_{t}. Since Δ_{t} is a conjugacy function we may define τ̌_{t} = ϕ^{−1}Δ_{t}ϕ and so τ̌_{t}([H], [D_{16}]) is the inventory w(Ω_{t}).

Equations (4) and (5) define a conjugacy function Δ_{f} where Δ_{f}(H) is the total weight of the colourings which are free of a-rooted trees. The corresponding τ̌_{f} is given by a similar inclusion-exclusion formula:

τ̌_{f} = ϕ^{−1}Δ_{f}ϕ = ϕ^{−1} ∑_{t=0}^{7}(−1)^{ν_{t}}Δ_{t}ϕ = ∑_{t=0}^{7}(−1)^{ν_{t}}ϕ^{−1}Δ_{t}ϕ = ∑_{t=0}^{7}(−1)^{ν_{t}} τ̌_{t}.

and w(Ω_{f,[H]}) = τ̌_{f}([H], [D_{16}]) where Ω_{f} is a transversal for patterns with no a-rooted tree.

H  Δ_{f}(H)
D_{16}, D′′_{8}, C_{8} p_{8}
D′_{8}, C_{4}  p_{4}^{2} − 2q_{4}r_{4}
K′′  p_{4}^{2}
K′  p_{4}p_{2}^{2} − 2p_{2}q_{2}r_{4} + q_{2}^{2}r_{4} − q_{4}r_{2}^{2}
C′′_{2}  p_{2}^{4} − 2p_{2}q_{2}r_{2}^{2}
C′_{2}  p_{2}^{3}p_{1}^{2} − 2p_{2}^{2}p_{1}q_{1}r_{2} − 2p_{2}p_{1}q_{2}r_{2}r_{1} + p_{2}q_{1}^{2}r_{2}^{2} − p_{1}^{2}q_{2}r_{2}^{2} + 2p_{1}q_{2}q_{1}r_{2}^{2}
+2q_{2}q_{1}r_{2}^{2}r_{1} + q_{2}^{2}r_{2}r_{1}^{2} − q_{2}q_{1}^{2}r_{2}^{2}
C_{2}  p_{2}^{4} − 4p_{2}q_{2}r_{2}^{2} + 2q_{2}^{2}r_{2}^{2}
I  p_{1}^{8} − 8p_{1}^{5}q_{1}r_{1}^{2} + 12p_{1}^{2}q_{1}^{2}r_{1}^{4} + 8p_{1}^{3}q_{1}^{2}r_{1}^{3} − 8p_{1}q_{1}^{3}r_{1}^{4} − 8q_{1}^{3}r_{1}^{5} + 2q_{1}^{4}r_{1}^{4}

Table 4: Weights of colourings with no a-rooted tree.

The values of Δ_{f} are given in Table 4 and may be substituted in Table 1 to give the [H]-inventories for Ω_{f}. The first four of these contain relatively few terms:

τ̌_{f}([D_{16}], [D_{16}]) = p_{8} = Ση_{1}^{8} + Σθ_{1}^{8}
τ̌_{f}([D′_{8}], [D_{16}]) = (p_{4}^{2} − p_{8})/2 − q_{4}r_{4} = Ση_{1}^{4}η_{2}^{4} + Σθ_{1}^{4}θ_{2}^{4}
τ̌_{f}([K′′], [D_{16}]) = (p_{4}^{2} − p_{8})/2 = Ση_{1}^{4}η_{2}^{4} + Ση_{1}^{4}θ_{1}^{4} + Σθ_{1}^{4}θ_{2}^{4}
τ̌_{f}([K′], [D_{16}]) = q_{4}(q_{2}^{2} − q_{4})/2 + q_{4}q_{2}r_{2} + r_{4}(r_{2}^{2} − r_{4})/2
= Ση_{1}^{6}η_{2}^{2} + Ση_{1}^{4}η_{2}^{2}η_{3}^{2} + Ση_{1}^{6}θ_{1}^{2} + Ση_{1}^{4}η_{2}^{2}θ_{1}^{2} + Σθ_{1}^{6}θ_{2}^{2} + Σθ_{1}^{4}θ_{2}^{2}θ_{3}^{2}

4 The trigonal dodecahedron

In [2] and [3] Lloyd has applied Redfield/Pólya methods to the enumeration of chemical isomers. In this situation the G-set X = {1, …, 8} is a molecule whose elements are termed sites, and these sites are ’coloured’ with ligands which are groupings of one or more atoms.

[figure: ∘; ∘; ∘; ∘; •; •; •; •; 1; 2; 3; 4; 5; 6; 7; 8]

Figure 5: The trigonal dodecahedron.

There are chemical compounds which have eight ligands situated at the vertices of a trigonal dodecahedron (see Figure 5). The rotation group of the polyhedron contains three half-turns about mutually perpendicular axes, and the full rotation group is isomorphic to the dihedral group D_{8} with elements

(),  (13)(24)(57)(68), (12)(34)(58)(67), (14)(23)(56)(78), (13)(68),  (24)(57),  (1432)(5876),  (1234)(5678).

Since four of the sites are 4-valent and the remainder 5-valent, we colour {1, 2, 3, 4} with a set of ligands A and {5, 6, 7, 8} with a second set B. The appropriate cycle index is therefore

Cyc(D_{8}, \{q_{i}, r_{i} | 1 ≤ i ≤ 4\}) = \frac{1}{8}(q_{1}^{4}r_{1}^{4} + 2q_{2}q_{1}^{2}r_{2}r_{1}^{2} + 3q_{2}^{2}r_{2}^{2} + 2q_{4}r_{4}).

We suppose, as before, that |A| = j, |B| = k, and consider the enumeration of nonadjacent colourings χ : colourings such that no two adjacent sites contain the same ligand. In this example the set of properties is P = {P_{13}, P_{24}, P_{56}, P_{67}, P_{78}, P_{58}} where χ satisfies P_{ih} if sites i and h contain the same ligand. First we restrict to the subset P_{A} = {P_{13}, P_{24}}, and call χ A-adjacent if χ(1) = χ(3) or χ(2) = χ(4). Then we apply the restriction to the square {5, 6, 7, 8}, using P_{B} = {P_{56}, P_{67}, P_{78}, P_{58}}.

The only adjacent pairs of sites coloured with A are {1, 3} and {2, 4}. Fix a_{i} ∈ A and partition A as {a_{i}} ∪ Ā_{i}. There are only four types of marked template pattern, colouring X with {a_{i}, a_{h}, a, b}, as shown in Figure 6.

The inclusion-exclusion formula for the weight of the set A_{f} of colourings which are not A-adjacent is

Δ_{A_{f}} = Δ_{0} − ∑_{i=1}^{j} Δ_{1i} + ∑_{i=1}^{j} Δ_{2i} + ∑_{i≠h} Δ_{2ih}.

[figure: T_{0}; ∘; ∘; ∘; ∘; •; •; •; •; a; a; a; a; b; b; b; b; T_{1i}; ∘; ∘; ∘; ∘; •; •; •; •; a_{i}; a; a_{i}; a; b; b; b; b; T_{2ii}; ∘; ∘; ∘; ∘; •; •; •; •; a_{i}; a_{i}; a_{i}; a_{i}; b; b; b; b; T_{2ih}; ∘; ∘; ∘; ∘; •; •; •; •; a_{i}; a_{h}; a_{i}; a_{h}; b; b; b; b]

Figure 6: A-adjacent templates.

The individual w(V_{t}, H) need not be symmetric functions, but become so under summation, as in

∑_{i=1}^{j} w(V_{2ih}, K) = ∑_{i≠h} η_{i}^{2}η_{h}^{2}r_{2}^{2} = \frac{1}{2}(q_{2}^{2} − q_{4})r_{2}^{2}.

The only non-zero weights and [H]-enumerators are shown in Table 5.

\begin{matrix}[H] & Δ_{A_{f}} (H) & τ̌_{A_{f}} ([H], [D_{16}]) \\ C′′_{2} & (q_{2}^{2} − q_{4})r_{2}^{2} & (q_{2}^{2} − q_{4})r_{2}^{2}/2 \\ I & (q_{1}^{2} − q_{2})^{2}r_{1}^{4} & ((q_{1}^{2} − q_{2})^{2}r_{1}^{4} − 2(q_{2}^{2} − q_{4})r_{2}^{2})/8 \end{matrix}

Table 5: Enumerators of non-A-adjacent patterns.

Now consider colourings in which adjacent sites among {5, 6, 7, 8} contain different ligands but with no restriction on {1, 2, 3, 4}. The marked templates are shown in Figure 7.

[figure: T_{3i}; ∘; ∘; ∘; ∘; •; •; •; •; a; a; a; a; b_{i}; b_{i}; b; b; T_{4i}; ∘; ∘; ∘; ∘; •; •; •; •; a; a; a; a; b_{i}; b_{i}; b; b_{i}; T_{5ih}; ∘; ∘; ∘; ∘; •; •; •; •; a; a; a; a; b_{i}; b_{i}; b_{h}; b_{h}; T_{5ii}; ∘; ∘; ∘; ∘; •; •; •; •; a; a; a; a; b_{i}; b_{i}; b_{i}; b_{i}]

Figure 7: B-adjacent templates.

Because each site belongs to two adjacent pairs it is not the case, as in Williamson’s example, that distinct Q, Q′ ⊆ P always give rise to different marked templates. In fact subsets

{P_{56}, P_{78}}, {P_{67}, P_{58}},
{P_{56}, P_{67}, P_{78}}, {P_{56}, P_{67}, P_{58}}, {P_{56}, P_{78}, P_{58}}, {P_{67}, P_{78}, P_{58}},
{P_{56}, P_{67}, P_{78}, P_{58}}

all give rise to marked templates T_{5ii}. Thus, when converting the general inclusion-exclusion formula (4) to a formula involving the Δ_{t}, the coefficient of Δ_{5ii} is 2 − 4 + 1 = −1. The full formula is:

Δ_{B_{f}} = Δ_{0} − ∑_{i=1}^{k} Δ_{3i} + ∑_{i=1}^{k} Δ_{4i} + ∑_{i≠h} Δ_{5ih} − ∑_{i=1}^{k} Δ_{5ii}.

The only non-zero weights are

Δ_{B_{f}} (K) = Δ_{B_{f}} (C_{2}) = q_{2}^{2}(r_{2}^{2} − r_{4}),
Δ_{B_{f}} (C′′′_{2}) = q_{2}q_{1}^{2}(r_{2}r_{1}^{2} − 2r_{3}r_{1} + r_{4}),
Δ_{B_{f}} (I) = q_{1}^{4}(r_{1}^{4} − 4r_{2}r_{1}^{2} + 4r_{3}r_{1} + 2r_{2}^{2} − 3r_{4}),

where the subgroups in class [C′′′_{2}] are generated by the reflections in the planes 1, 3, 6, 8 and 2, 4, 5, 7 and K is their join. The non-zero [H]-enumerators for B-adjacent free patterns are

τ̌_{B_{f}} ([K], [D_{8}]) = Δ_{B_{f}} (K)/2,
τ̌_{B_{f}} ([C′′′_{2}], [D_{8}]) = (Δ_{B_{f}} (C′′′_{2}) − Δ_{B_{f}} (K))/2,
τ̌_{B_{f}} ([I], [D_{8}]) = (Δ_{B_{f}} (I) − 2Δ_{B_{f}} (C′′′_{2}) + Δ_{B_{f}} (K))/8.

In order to deal with non-adjacent colourings, we should need to consider all possible adjacencies, leading to a total of 20 marked templates. We omit the details.

5 The general algorithm

The following algorithm applies to an enumeration problem interpreted as the counting of patterns of valid colourings having a chosen stabilizer class [H] in a group G. Colourings are invalid if they satisfy one or more of a set P = {P_{1}, P_{2}, …, P_{λ}} of forbidden properties. These properties may be expressed in terms of a partition /A_{1}/A_{2}/ … /A_{κ}/ of a set of colours C. If A_{i} = {a_{i1}, a_{i2}, …, a_{ij_{i}}} and ∑_{i=1}^{κ} j_{i} = ℓ, take Ξ to be a set of ℓ indeterminates {η_{ih} | 1 ≤ i ≤ κ, 1 ≤ h ≤ j_{i}} and let w_{c} : C → A, a_{ih} ↦ η_{ih}, be the corresponding weight function. Denote by q_{id} the power sum ∑_{h=1}^{j_{i}} η_{ih}^{d} and by V_{f} the set of valid colourings.

Algorithm 5.1

1. Use Williamson’s multilinear techniques to obtain a complete set of marked template patterns T_{t} coloured with a set of colours {c_{1}, c_{2}, …, c_{κ}}.

2. For each template T_{t} and for each [H] ≤ [K] ≤ [G] determine, using formulae (6) and (7), the weights Δ_{t}([K]) = w(V_{t}, K) as polynomials in the q_{id}.

3. Determine the total weight Δ_{f}([K]) of colourings in V_{f} fixed by K by rewriting the inclusion-exclusion formula (4) for the λ properties as a signed sum of the Δ_{t}([K]).

4. Calculate values of α_{f} = μΔ_{f}ζ and τ̌_{f} = ϕ^{−1}Δ_{f}ϕ using equations (2) and (3), working down from [G] over the interval [ [H], [G] ] of P_{G}.

Theorem 5.2 The polynomial τ̌_{f}([H], [G]) is the [H]-inventory for patterns of valid colourings. When this polynomial is expressed as a polynomial in the indeterminates η_{ih}, the coefficient of ∏ η_{ih}^{d_{ih}} is the number of patterns in which colour a_{ih} is used d_{ih} times.

References

[1] Kerber, A., Algebraic combinatorics via finite group actions, (Bibliographisches Institut Wissenschaftsverlag, Mannheim, 1991).

[2] Lloyd, E.K., Redfield’s papers and their relevance to counting isomers and isomerizations, Discrete Applied Math. 19 (1988) 289-304.

[3] Lloyd, E.K., Marks of permutation groups and isomer enumeration, J. Math. Chemistry 11 (1992) 207-222.

[4] Morris, I. and Wensley, C.D. Adams operations and λ-operations in β-rings, Discrete Math. 50 (1984) 253-270.

[5] Morris, I. and Wensley, C.D., Cycle indices and subgroup lattices, Discrete Math. 118 (1993) 173-195.

[6] Williamson, S.G., The combinatorial analysis of patterns and the principle of inclusion-exclusion, Discrete Math. 1 (1972) 357-388.