|
%I #50 Sep 17 2019 03:49:31
%S 1,3,6,13,24,51,97,207,428,946,2088,4831,11209,26717,64058,155725,
%T 380400,936575,2314105,5744700,14300416,35708268,89359536,224121973,
%U 563126689,1417378191,3572884062,9019324297,22797540648
%N "DIK" (bracelet, indistinct, unlabeled) transform of 1,2,3,4,...
%C From _Petros Hadjicostas_, Jun 21 2019: (Start)
%C Under Bower's transforms, the input sequence c = (c(m): m >= 1) describes how each part of size m in a composition is colored. In a composition (ordered partition) of n >= 1, a part of size m is assumed to be colored with one of c(m) colors.
%C Under the DIK transform, we are dealing with "dihedral compositions" of n >= 1. These are equivalence classes of ordered partitions of n such that two such ordered partitions are equivalent if one can be obtained from the other by rotation or reflection.
%C If the input sequence is c = (c(m): m >= 1), denote the output sequence under the DIK transform by b = (b(n): n >= 1); i.e., b(n) = (DIK c)(n) for n >= 1. If C(x) = Sum_{m >= 1} c(m)*x^m is the g.f. of the input sequence c, then the g.f. of b = DIK c is Sum_{n >= 1} b(n)*x^n = -(1/2) * Sum_{d >= 1} (phi(d)/d) * log(1 - C(x^d)) + (1 + C(x))^2/(4 * (1 - C(x^2))) - (1/4).
%C For the current sequence (a(n): n >= 1), the input sequence is c(m) = m for all m >= 1. That is, we are dealing with the so-called "m-color dihedral compositions". Here, a(n) is the number of dihedral compositions of n where each part of size m may be colored with one of m colors. For the linear and cyclic versions of such m-color compositions, see Agarwal (2000), Gibson (2017), and Gibson et al. (2018).
%C Since C(x) = x/(1 - x)^2, we have Sum_{n >= 1} a(n) * x^n = (1/2) * Sum_{d >= 1} (phi(d)/d) * log((1 - x^d)^2 / (1 - 3*x^d + x^(2*d))) + (1/2) * x * (1 + x - 2*x^2 + x^3 + x^4)/((1 - x)^2 * (1 + x - x^2) * (1 - x - x^2)), which is the g.f. given by _Andrew Howroyd_ in the PARI program below.
%C Note that -Sum_{d >= 1} (phi(d)/d) * log (1 - C(x^d)) = Sum_{d >= 1} (phi(d)/d) * log((1 - x^d)^2 / (1 - 3*x^d + x^(2*d))) is the g.f. of the "m-color cyclic compositions" that appear in Gibson (2017) and Gibson et al. (2018). See sequence A032198, which is the CIK transform of sequence (c(m): m >= 1) = (m: m >= 1).
%C (End)
%H Andrew Howroyd, <a href="/A032287/b032287.txt">Table of n, a(n) for n = 1..200</a>
%H A. K. Agarwal, <a href="https://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005b15_1421.pdf">n-colour compositions</a>, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>.
%H Meghann Moriah Gibson, <a href="https://digitalcommons.georgiasouthern.edu/etd/1583/">Combinatorics of compositions</a>, Master of Science, Georgia Southern University, 2017.
%H Meghann Moriah Gibson, Daniel Gray, and Hua Wang, <a href="https://doi.org/10.1016/j.disc.2018.08.001">Combinatorics of n-color compositions</a>, Discrete Mathematics 341 (2018), 3209-3226.
%H 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 <a href="/index/Br#bracelets">Index entries for sequences related to bracelets</a>
%F From _Petros Hadjicostas_, Jun 21 2019: (Start)
%F a(n) = ( F(n+4) + (-1)^n * F(n-4) - 2 * (n + 1) + (1/n) * Sum_{d|n} phi(n/d) * L(2*d) )/2 for n >= 4, where F(n) = A000045(n) and L(n) = A000032(n) are the usual n-th Fibonacci and n-th Lucas numbers, respectively.
%F a(n) = (A032198(n) + A308747(n))/2 for n >= 1.
%F G.f.: (1/2) * Sum_{d >= 1} (phi(d)/d) * log((1 - x^d)^2 / (1 - 3*x^d + x^(2*d))) + (1/2) * x * (1 + x - 2*x^2 + x^3 + x^4)/((1 - x)^2 * (1 + x - x^2) * (1 - x - x^2)).
%F (End)
%t seq[n_] := x(1 + x - 2 x^2 + x^3 + x^4)/((1 - x)^2 (1 - x - x^2)(1 + x - x^2)) + Sum[EulerPhi[d]/d Log[(1 - x^d)^2/(1 - 3 x^d + x^(2d)) + O[x]^(n+1)], {d, 1, n}] // CoefficientList[#, x]& // Rest // #/2&;
%t seq[30] (* _Jean-François Alcover_, Sep 17 2019, from PARI *)
%o (PARI) seq(n)={Vec(x*(1 + x - 2*x^2 + x^3 + x^4)/((1 - x)^2*(1 - x - x^2)*(1 + x - x^2)) + sum(d=1, n, eulerphi(d)/d*log((1 - x^d)^2/(1 - 3*x^d + x^(2*d)) + O(x*x^n))))/2} \\ _Andrew Howroyd_, Jun 20 2018
%Y Cf. A000032, A000045, A001906, A005594, A032198, A088305, A308747.
%K nonn
%O 1,2
%A _Christian G. Bower_
| 