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.

The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.

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 exactly k colors. The sequence here, displays T(n,k)=phi_k(C_n), i.e., the number of non-equivalent distinguishing colorings of the cycle C_n on n vertices with exactly k colors.

From Andrew Howroyd, Aug 15 2019: (Start)

First differs from A305541 at n = 6.

Also the number of n-bead asymmetric bracelets with exactly k different colored beads. More precisely the number of chiral pairs of primitive (aperiodic) color loops of length n with exactly k different colors. For example, for n=4 and k = 3, there are 3 achiral loops (1213, 1232, 1323) and 3 pairs of chiral loops (1123/1132, 1223/1322, 1233/1332).

(End)

Equivalently, the dihedral group of order n acts on the set of length n binary sequences. T(n,k) is the number of orbits that contain k elements.

By "n-bead necklaces (turning over is allowed)" the author means "bracelets". By saying that the classes of these n-bead bracelets (turnover necklaces) "contain k necklaces" the author means that the classes "contain k marked necklaces". - Petros Hadjicostas, Jun 06 2019

Asymmetric bracelets are those primitive (period n) bracelets that when turned over are different from themselves.

Asymmetric bracelets are those primitive (period n) bracelets that when turned over are different from themselves.

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)

For k = 1, 4, or a prime, the columns of this triangular array are exactly the same as the corresponding columns for the triangular array A180472. In other words, all chiral bracelets with n beads, k of which are white and n - k are black, are aperiodic if k = 1, 4, or a prime.

Note that, T(n, k) is also the number of aperiodic dihedral compositions of n with k parts and no reflection symmetry. Since T(n, k) = T(n, n - k), T(n, k) is also the number of aperiodic dihedral compositions of n with n - k parts and no reflection symmetry.

The distinguishing number of the n-cycle graph is 3 for n = 3, 4, 5 and 2 for n >= 6.