cp's OEIS Frontend

A032253 "DHK" (bracelet, identity, unlabeled) transform of 3,3,3,3,...

%I A032253 #87 Apr 25 2024 09:15:06
%S A032253 1,3,6,13,27,78,278,1011,3753,13843,50934,187629,692891,2568882,
%T A032253 9562074,35742329,134117829,505093740,1908474674,7232842785,
%U A032253 27486193251,104712247296,399816026490,1529742725403,5864036504705,22517947805343,86607583200294,333599771067256
%N A032253 "DHK" (bracelet, identity, unlabeled) transform of 3,3,3,3,...
%C A032253 From _Petros Hadjicostas_, Jun 17 2019: (Start)
%C A032253 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.
%C A032253 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).
%C A032253 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.)
%C A032253 A symmetric (achiral) cyclic composition of n >= 1 is also a symmetric (achiral) dihedral composition of n > = 1 (and vice versa).
%C A032253 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.
%C A032253 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).
%C A032253 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).
%C A032253 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).
%C A032253 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.
%C A032253 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).
%C A032253 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).
%C A032253 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.
%C A032253 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)).
%C A032253 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).
%C A032253 (End)
%H A032253 Andrew Howroyd, <a href="/A032253/b032253.txt">Table of n, a(n) for n = 0..500</a>
%H A032253 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H A032253 Arnold Knopfmacher and Neville Robbins, <a href="https://www.researchgate.net/publication/260006088_Some_Properties_of_Dihedral_Compositions">Some properties of dihedral compositions</a>, Util. Math. 92 (2013), 207-220.
%H A032253 Jean-Christophe Novelli and Jean-Yves Thibon, <a href="http://arxiv.org/abs/0806.3682">Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions</a>, arXiv:0806.3682 [math.CO], 2008. See Eqs. (94) and (95).
%H A032253 Jean-Christophe Novelli and Jean-Yves Thibon, <a href="https://doi.org/10.1016/j.disc.2010.09.008">Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions</a>, Discrete Math. 310 (2010), no. 24, 3584-3606. See Eqs. (99) and (100).
%F A032253 From _Petros Hadjicostas_, Jun 18 2019: (Start)
%F A032253 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.
%F A032253 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).
%F A032253 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)
%e A032253 From _Petros Hadjicostas_, Jun 17 2019: (Start)
%e A032253 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.
%e A032253 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)}.
%e A032253 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)}.
%e A032253 (End)
%t A032253 A001651[n_] := n - 1 + Ceiling[n/2];
%t A032253 A185172[n_] := If[n==1, 3, Sum[MoebiusMu[d] 4^(n/d), {d, Divisors[n]}]/n];
%t A032253 A038199[n_] := Sum[((2^d-1) MoebiusMu[n/d]), {d, Divisors[n]}];
%t A032253 a[n_] := Switch[n, 0, 1, 1, 3, _, 3 A001651[n] + (1/2)(A185172[n] - 3 * A038199[n])];
%t A032253 a /@ Range[0, 30] (* _Jean-François Alcover_, Sep 17 2019 *)
%o A032253 (PARI)
%o A032253 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}
%o A032253 seq(n)={Vec(1 + DHK(3*x/(1-x) + O(x*x^n), n))} \\ _Andrew Howroyd_, Sep 21 2018
%Y A032253 Cf. A001651, A032102, A032239, A032240, A032241, A032242, A032244, A032245, A032251, A032252, A032254, A032256, A032257, A032258, A032259, A038199, A185172.
%K A032253 nonn
%O A032253 0,2
%A A032253 _Christian G. Bower_
%E A032253 a(0)=1 prepended and terms a(24) and beyond from _Andrew Howroyd_, Sep 21 2018