OFFSET
0,2
COMMENTS
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)
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..500
C. G. Bower, Transforms (2)
Arnold Knopfmacher and Neville Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207-220.
Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions, arXiv:0806.3682 [math.CO], 2008. See Eqs. (94) and (95).
Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions, Discrete Math. 310 (2010), no. 24, 3584-3606. See Eqs. (99) and (100).
FORMULA
From Petros Hadjicostas, Jun 18 2019: (Start)
a(n) = 3*A001651(n) + (1/2)*(A185172(n) - 3*A038199(n)) for n >= 1. Here, A001651(n) = floor((3*n - 1)/2) and A038199(n) = Sum_{d|n} mu(d)*(2^(n/d) - 1) for n >= 1. Also, A185172(1) = 3 and A185172(n) = (1/n)*Sum_{d|n} mu(d) * 4^(n/d) for n >= 2.
G.f.: 1 - (1/2)*Sum_{d >= 1} (mu(d)/d)*log(1 - 3*x^d/(1 - x^d)) - (1/2)*Sum_{d >= 1} mu(d)*3*x^d/((1 - 2*x^d)*(1 - x^d)) + 3*x*(1 + x + x^2)/((1 + x)*(1 - x)^2).
G.f.: 1 - x/2 - (1/2)*Sum_{d >= 1} (mu(d)/d)*log(1 - 4*x^d) - (1/2)*Sum_{d >= 1} mu(d)*3*x^d/((1 - 2*x^d)*(1 - x^d)) + 3*x*(1 + x + x^2)/((1 + x)*(1 - x)^2). (End)
EXAMPLE
From Petros Hadjicostas, Jun 17 2019: (Start)
For n = 3, the Bower's extra 3*A001651(3) = 12 aperiodic dihedral compositions of 3 (using three colors) with one or two parts are as follows: 3_A, 3_B, 3_C, 1_A + 2_A, 1_B + 2_B, 1_C + 2_C, 1_A + 2_B, 1_A + 2_C, 1_B + 2_A, 1_B + 2_C, 1_C + 2_A, 1_C + 2_B. Since a(3) - 3*A001651(3) = 13 - 12 = 1, we have only one aperiodic chiral dihedral composition of 3 (with more than two parts): 1_A + 1_B + 1_C.
For n = 4, the Bower's extra 3*A001651(4) = 15 aperiodic dihedral compositions of n = 4 (using three colors) with one or two parts are as follows: 4_X, where X \in {A, B, C}; 2_X + 2_Y, where (X,Y) \in {(A, B), (B, C), (C, A)}; and 1_X + 3_Y, where (X, Y) \in {(A, A), (A, B), (A, C), (B, A), (B, B), (B, C), (C, A), (C, B), (C, C)}.
The remaining (i.e., the genuine) a(4) - 15 = 27 - 15 = 12 aperiodic chiral dihedral compositions of n = 4 of 3 colors are as follows: 1_X + 2_X + 1_Y, where (X, Y) \in {(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)}; 1_X + 2_Y + 1_Z and 1_X + 1_X + 1_Y + 1_Z, where (X, Y, Z) \in \{(A, B, C), (B, C, A), (C, A, B)}.
(End)
MATHEMATICA
A001651[n_] := n - 1 + Ceiling[n/2];
A185172[n_] := If[n==1, 3, Sum[MoebiusMu[d] 4^(n/d), {d, Divisors[n]}]/n];
A038199[n_] := Sum[((2^d-1) MoebiusMu[n/d]), {d, Divisors[n]}];
a /@ Range[0, 30] (* Jean-François Alcover, Sep 17 2019 *)
PROG
(PARI)
DHK(p, n)={my(q=((1+p)^2/(1-subst(p, x, x^2))-1)/2); p + (p^2-subst(p, x, x^2))/2 + sum(d=1, n, moebius(d)*(log(subst(1/(1+O(x*x^(n\d))-p), x, x^d))/d - subst(q + O(x*x^(n\d)), x, x^d)))/2}
seq(n)={Vec(1 + DHK(3*x/(1-x) + O(x*x^n), n))} \\ Andrew Howroyd, Sep 21 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
a(0)=1 prepended and terms a(24) and beyond from Andrew Howroyd, Sep 21 2018
STATUS
approved