Manuel Kauers Hagenberg, June 22, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 13

Exercise 1 Let H × G act on Y^{X} as usual. Prove that the number of orbits of (H × G) \\ Y^{X} of cont_{f} is

⟨ ∏_{y∈Y} y^{cont_{f} (y)}⟩\frac{1}{|H||G|} ∑_{(h,g)∈H×G} ∏_{i=1}^{|X|}( ∑_{y∈Y_{h^{i}}} y^{i})^{a_{i}(ḡ)}

Let T be a complete set of representatives of (H × G) \\ Y^{X}. The weighted form of CF with W: Y → R ⊇ ℚ arbitrary and w: X^{Y} → R the product weight says

∑_{t∈T} w(t) = \frac{1}{|G||H|} ∑_{(g,h)∈G×H} ∑_{f∈Y_{(g,h)}^{X}} w(f).

By the same reasoning as in previous week’s Exercise 2, it can be shown that

∑_{f∈Y_{(g,h)}^{X}} w(f) = ∑_{f∈Y_{(g,h)}^{X}} ∏_{x∈X} W (f(x)) = ∏_{i=1}^{|X|}( ∑_{y∈Y_{h^{i}}} W (y)^{i})^{a_{i}(ḡ)},

therefore

∑_{t∈T} w(t) = \frac{1}{|G||H|} ∑_{(g,h)∈G×H} ∏_{i=1}^{|X|}( ∑_{y∈Y_{h^{i}}} W (y)^{i})^{a_{i}(ḡ)}.

Now assume Y ⊆ R and W (y) := y (y ∈ Y). Then

∏_{i=1}^{|X|}( ∑_{y∈Y_{h^{i}}} W (y)^{i})^{a_{i}(ḡ)} = ∑_{t∈T} w(t) = ∑_{t∈T} ∏_{x∈X} W (t(x)) = ∑_{t∈T} ∏_{y∈Y} y^{cont_{t}(y)}.

The claim follows.

Exercise 2 Let X be a G-set. Prove

\frac{1}{|G|} ∑_{g∈G} ∏_{i=1}^{|X|} z_{i}^{a_{i}(ḡ)} = \frac{1}{|Ḡ|} ∑_{ḡ∈Ḡ} ∏_{i=1}^{|X|} z_{i}^{a_{i}(ḡ)}.

G and Ḡ are isomorphic and δ is an isomorphism.

Exercise 3 Let C_{[n]} and D_{[n]} be the cyclic and the Dieder group, respectively. Prove

C(D_{[5]}, [5]) = \frac{1}{2}C(C_{[5]}, [5]) + \frac{1}{2}z_{1}z_{2}^{2}
C(D_{[6]}, [6]) = \frac{1}{2}C(C_{[6]}, [6]) + \frac{1}{4}(z_{2}^{3} + z_{1}^{2}z_{2}^{2}).

For a group G acting on X we have

C(G, X) := \frac{1}{|G|} ∑_{g∈G} z_{1}^{a_{1}(ḡ)}z_{2}^{a_{2}(ḡ)} ⋯ z_{|X|}^{a_{|X|}(ḡ)}.

It follows that

C(D_{n}, [n]) = \frac{1}{|D_{n}|}( ∑_{π∈C_{n}} ∏_{i} z_{i}^{a_{i}(π)} + ∑_{π∉C_{n}} ∏_{i} z_{i}^{a_{i}(π)}).

For the special instances n = 5, 6 we have the additional permutations π ∉ C_{n}, coming from the reflections. If n = 5, we have the additional permutations

(1 5)(2 4)(3), (1 4)(2 3)(5), (1 3)(2)(4 5), (1 3)(3 5)(4), (1)(2 5)(3 4),

leading to five additional terms z_{1}z_{2}^{2}, so

C(D_{5}, [5]) = \frac{1}{2}C(C_{5}, [5]) + \frac{5}{|D_{5}|}z_{1}z_{2}^{2} = \frac{1}{2}C(C_{5}, [5]) + \frac{1}{2}z_{1}z_{2}^{2}.

If n = 6, we have the additional permutations

(1 6)(2 5)(3 4), (1 5)(2 4)(3)(6), (1 4)(2 3)(5 6),
(1 3)(2)(5)(4 6), (1 2)(3 6)(4 5), (1)(2 6)(3 5)(4),

leading to three additional terms z_{2}^{3} and three additional terms z_{1}^{2}z_{2}^{2}, so

C(D_{6}, [6]) = \frac{1}{2}C(C_{6}, [6]) + \frac{1}{4}(z_{2}^{3} + z_{1}^{2}z_{2}^{2}).

Exercise 4 Prove

C(A_{3}, [3]) = C(S_{3}, [3]) + C(S_{3}, [3]; z_{1}, −z_{2}, …),
C(A_{4}, [4]) = C(S_{4}, [4]) + C(S_{4}, [4]; z_{1}, −z_{2}, …).

We have

S_{3} = {(1)(2)(3), (1)(2 3), (1 2)(3), (1 3)(2), (1 2 3), (1 3 2)},
A_{3} = {(1)(2)(3), (1 2 3), (1 3 2)},

therefore

C(S_{3}, [3]) = \frac{1}{6}(3z_{1}z_{2} + 2z_{1} + z_{1}^{3})
C(S_{3}, [3]; z_{1}, −z_{2}, z_{3}) = \frac{1}{6}(−3z_{1}z_{2} + 2z_{1} + z_{1}^{3})
C(A_{3}, [3]) = \frac{1}{3}(2z_{1} + z_{1}^{3}).

Fits. For n = 4, we have

A_{4} = {(1)(2)(3)(4), (1 2 3), (1 2)(3 4), (1 3 2), (1 2 4), (1 4 2), (2 3 4), (2 4 3),
(2 3)(1 4), (1 4 3), (1 3 4), (1 3)(2 4)},

therefore

C(A_{4}, [4]) = \frac{1}{12}(z_{1}^{4} + 3z_{2}^{2} + 8z_{1}z_{3}).

On the other hand, we have

C(S_{4}, [4]) = \frac{1}{4!}(\frac{z_{1}^{4}}{4!} + \frac{z_{1}^{2}z_{2}}{2^{1}2!} + \frac{z_{2}^{2}}{2^{2}2!} + \frac{z_{1}z_{3}}{3} + \frac{z_{4}}{4} )
= \frac{1}{24}(z_{1}^{4} + 6z_{1}^{2}z_{2} + 3z_{2}^{2} + 8z_{1}z_{3} + 6z_{4}),

so

C(S_{4}, [4]) + C(S_{4}, [4]; z_{1}, −z_{2}, z_{3}, −z_{4}) = \frac{1}{24}(2z_{1}^{4} + 6z_{2}^{2} + 16z_{1}z_{3}).

Fits also.

Exercise 5 Find the number of patterns of coloring the 12 edges of a cube with at most three colors. What is the number of cubes with two green, two red, and eight blue colors?

What is the symmetry group?

symmetry  cycle type  number
all fixed  (12, 0, …, 0)  1
faces fixed, 180^{∘}  (0, 6, 0, …, 0)  3
faces fixed, 90^{∘}, 270^{∘} (0, 0, 0, 3, 0, …)  6
edges fixed  (2, 5, 0, …)  6
corners fixed  (0, 0, 4, 0, …)  8

This gives the cycle polynomial

C(G, [12]) = \frac{1}{24}(z_{1}^{12} + 3z_{2}^{6} + 6z_{4}^{3} + 6z_{1}^{2}z_{2}^{5} + 8z_{3}^{4}).

We have

C(G, [12]; r + g + b) = ⋯ + 135b^{8}r^{2}g^{2} + ⋯

Therefore, there are 135 ways to color the edges of a cube such that 8 edges are blue, 2 are red and 2 are green. The sum of all coefficients, 22815, is the number of ways to color the edges of a cube by at most three colors.

Exercise 6 Find the number of patterns of coloring the six faces of a cube with at most four colors. What is this number, if there should be one green, one red, and two blue faces?

Here the symmetry group is given by the following permuations

symmetry  cycle type  number
all fixed  (6, 0, 0, 0, 0, 0)  1
faces fixed, 180^{∘}  (2, 2, 0, 0, 0, 0)  3
faces fixed, 90^{∘}, 270^{∘} (2, 0, 0, 1, 0, 0)  6
edges fixed  (0, 3, 0, 0, 0, 0)  6
corners fixed  (0, 0, 2, 0, 0, 0)  8

The cycle polynomial therefore is

C(G, [6]) = \frac{1}{24}(z_{1}^{6} + 3z_{1}^{2}z_{2}^{2} + 6z_{1}^{2}z_{4} + 6z_{2}^{3} + 8z_{3}^{2}).

We have

C(G, [6]; r + b + g + d) = ⋯ + 8g^{1}r^{1}b^{2}d^{2} + ⋯,

so there are eight colorings with one green, one red, and two blue faces.

Altogether, there are 240 colorings of the faces of a cube by at most four colors.

Exercise 7 A boolean function of n variables is defined by the assignment of a value either 0 or 1 to each of the 2^{n} n-digit binary numbers. Two boolean functions are considered to be equivalent if one can be obtained from the other by permutation and or complementation of the independent variable(s). How many distinct boolean functions are there of two variables? … of three variables?

The exercise is not clearly stated. We understand that f ∼ g if f(a_{1}, …, a_{n}) = g(a_{π(1)}, …, a_{π(n)}) or f(a_{1}, …, a_{n}) = g(ā_{π(1)}, …, ā_{π(n)}). Let

X = {0, 1} × {0, 1} = {a = (0, 0), b = (0, 1), c = (1, 0), d = (1, 1)}

and let G := ⟨(a d), (b c)⟩ ≤ S_{X} act on X as usual. Consider the induced Polya action of G on {0, 1}^{X}. The cycle polynomial is

C(G, X) = \frac{1}{4}(z_{1}^{4} + 2z_{1}^{2}z_{2} + z_{2}^{2}),

because G = {(a)(b)(c)(d), (a d)(b)(d), (a)(b c)(d), (a d)(b c)}. Consequently

C(G, X; p + q) = p^{4} + 2p^{3}q + 3p^{2}q^{2} + 2pq^{3} + q^{4}.

The sum of the coefficients of this polynomial gives the desired number. The number is 9. Next, for n = 3 let

X = {0, 1}^{3} = {a_{0} = (0, 0, 0), a_{1} = (0, 0, 1), …, a_{7} = (1, 1, 1)}

We have the following elements of the group acting on X.

arg. perm. flip?  permutation  # monomial
(1)(2)(3)  no  (000)(001)… (111)  1  z_{1}^{8}
yes  (000,111)(001,110)… (011,100)  1  z_{2}^{4}
(1 2)  no (000)(100,010)(001)(011,101)(110)(111) 3  z_{1}^{4}z_{2}^{2}
yes (000,111)(001,110)(010,011)(100,101) 3  z_{2}^{4}
(1 2 3)  no  (000)(100,010,001)(110,011,101)(111) 2  z_{1}^{2}z_{3}^{2}
yes  (000,111)(001,011,010,110,100,101)  2  z_{2}z_{6}

Taking into account the the necessary multiplicities, we get the cycle polynomial

C(G, X) = \frac{1}{12}(z_{1}^{8} + 4z_{2}^{4} + 3z_{1}^{4}z_{2}^{2} + 2z_{1}^{2}z_{3}^{2} + 2z_{2}z_{6}).

Therefore,

C(G, X; p + q) = q^{8} + p^{8} + 2p^{7}q + 6p^{6}q^{2} + 8p^{5}q^{3} + 12p^{4}q^{4} + 8p^{3}q^{5} + 6p^{2}q^{6} + 2pq^{7}.

The sum of the coefficients is 46, as confirmed by a brute force count with Mathematica.

Exercise 8 Find the inventory of the chemical compounds that can be obtained by substituting the chlorine atoms for the hydrogen atoms in the benzene ring. Note that the group of permutations that transform the compound onto itself consits of all rotations and reflections.

We have

C(D_{6}, [6]) = \frac{1}{12}(z_{1}^{6} + 4z_{2}^{3} + 2z_{3}^{2} + 2z_{6}^{2} + 3z_{1}^{2}z_{2}^{2})

by table lookup. This gives

C(D_{6}, [6]; 1 + c) = 1 + c + 3c^{2} + 3c^{3} + 3c^{4} + c^{5} + c^{6}.

Sum of coefficients, 13, gives the number of molecules.

Exercise 9 Find the number of circular necklaces that can be formed with 12 beads, of which one is blue, five are green, five are red, and the remaining one is yellow. Would your method work for the compositions: 2 blue, 4 green, 4 red, and 2 yellow? For any other partition of 12?

The cycle polynomial is

C(C_{12}, [12]) = \frac{1}{12}(z_{1}^{12} + z_{2}^{6} + 2z_{3}^{4} + 2z_{4}^{3} + 2z_{6}^{2} + 4z_{12}).

By

C(C_{12}, [12], r + b + g + y) = ⋯ + 2772bg^{5}r^{5}y + ⋯ + 17340b^{2}g^{4}r^{4}y^{2} + ⋯

we obtain the numbers for the requested colorings.