cp's OEIS Frontend

A vertex-coloring of a graph G is called distinguishing if it is only preserved by the identity automorphism of G. This notion is considered in the subject of symmetry breaking of simple (finite or infinite) graphs. Two vertex-colorings of a graph are called equivalent if there is an automorphism of the graph which preserves the colors of the vertices. Given a graph G, we use the notation Phi_k(G) to denote the number of non-equivalent distinguishing colorings of G with at most k colors. The sequence here, displays A(n,k)=Phi_k(C_n), i.e., the number of non-equivalent distinguishing colorings of the cycle C_n on n vertices with at most k colors.

From Petros Hadjicostas, Jun 17 2019: (Start)

An unmarked cyclic composition of n >= 1 is an equivalence of ordered partitions of n such that two ordered partitions are equivalent iff one can be obtained from the other by rotation.

A dihedral composition of n >= 1 is an equivalence class of ordered partitions of n such that two such ordered partitions are equivalent iff one can be obtained from the other by rotation or reflection. See, for example, Knopfmacher and Robbins (2013).

A cyclic composition (ordered partition) of n >= 1 is called achiral iff it has a reflection symmetry, and it is called chiral otherwise. (This terminology comes from Chemistry in the study of molecules.)

A symmetric (achiral) cyclic composition of n >= 1 is also a symmetric (achiral) dihedral composition of n > = 1 (and vice versa).

Many mathematicians consider a cyclic composition of n >= 1 with one part or with two parts as achiral by default because the axis of symmetry may pass through the parts. When he defines the DHK transform, Bowers (in the link below) does not accept this convention except possibly for a cyclic composition with two identical (in value and color) parts.

Given n >= 1, a(n) here is the number of aperiodic chiral dihedral compositions of n such that the parts may be colored by any one of three colors (say, A, B, C).

Notice that a(1) = 3 because 1_A, 1_B, 1_C are the three colored aperiodic dihedral compositions of n = 1 that (according to Bowers) are considered chiral (= with no reflection symmetry).

In addition, a(2) = 6 because 2_A, 2_B, 2_C, 1_A + 1_B, 1_B + 1_C, 1_C + 1_A are the six colored aperiodic dihedral compositions of n = 2 that (according to Bowers) are considered chiral (= with no reflection symmetry).

In general, for n >= 1, if one disagrees with Bower's conventions about colored aperiodic dihedral compositions with one or two parts, then a(n) - 3*A001651(n) = a(n) - 3 * floor((3*n - 1 )/2) is the actual number of aperiodic chiral dihedral compositions of n such that the parts may be colored by any one of three colors.

Let c = (c(n): n >= 1) be the input sequence and b = (b(n): n >= 1) be the output sequence under Bower's DHK transform; i.e., b = (DHK c). Let C(x) = Sum_{n >= 1} c(n)*x^n; i.e., C(x) is the g.f. of c. Then the g.f. of b is Sum_{n >= 1} b(n)*x^n = -(1/2) * Sum_{d >= 1} (mu(d)/d) * log(1 - C(x^d)) - (1/2) * Sum_{d >= 1} mu(d) * ((C(x^d) + 1)^2/(2 * (1 - C(x^(2*d))) - (1/2)) + C(x) + (1/2) * (C(x)^2 - C(x^2)). Here, c(n) = 3 for all n >= 1 and C(x) = 3*x/(1 - x).

The part of the g.f. that gives the extra aperiodic dihedral compositions due to Bower is C(x) + (1/2) * (C(x)^2 - C(x^2)) = 3*x*(1 + x + x^2)/((1 + x)*(1 - x)^2). This is the g.f. of (3*A001651(n): n >= 1).

Here, D(x) = (C(x) + 1)^2/(2*(1 - C(x^2))) - (1/2) = 3*x/((1 - 2*x)*(1 - x)) = 3*(x + 3*x^2 + 7*x^3 + 15*x^4 + ...) is the g.f. of (3*A000225(n): n >= 1) = (3*(2^n - 1): n >= 1), which counts the symmetric (= achiral) unmarked cyclic compositions of n where up to 3 colors can be used.

Thus, the sequence (3*A038199(n): n >= 1) = (3*Sum_{d|n} mu(d)*A000225(n/d): n >= 1) = (3*Sum_{d|n} mu(d)*(2^(n/d) - 1): n >= 1) counts the aperiodic symmetric (unmarked) cyclic compositions of n where up to three colors can be used (without Bower's conventions for compositions with one or two parts). This latter sequence has g.f. Sum_{d >= 1} mu(d)*D(x^d) = Sum_{d >= 1} mu(d) * ((C(x^d) + 1)^2/(2 * (1 - C(x^(2*d))) - (1/2)).

Finally, -Sum_{d >= 1} (mu(d)/d)*log(1 - C(x^d)), where C(x) = 3*x/(1 - x), is the g.f. of sequence (A185172(n): n >= 1), which counts the aperiodic (unmarked) cyclic compositions of n where up to three colors can be used. See Eqs. (94) and (95) in Novelli and Thibon (2008) or Eqs. (99) and (100) in Novelli and Thibon (2010).

(End)