%I M2548 N1008 #81 Jan 12 2022 10:58:52
%S 1,3,6,11,24,51,130,315,834,2195,5934,16107,44368,122643,341802,
%T 956635,2690844,7596483,21524542,61171659,174342216,498112275,
%U 1426419858,4093181691,11767920118,33891544419,97764131646,282429537947,817028472960,2366564736723
%N Number of n-bead necklaces with 3 colors.
%C From _Richard L. Ollerton_, May 07 2021: (Start)
%C Here, as in A000031, turning over is not allowed.
%C (1/n) * Dirichlet convolution of phi(n) and 3^n, n>0. (End)
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 162.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).
%H T. D. Noe, <a href="/A001867/b001867.txt">Table of n, a(n) for n = 0..200</a>
%H E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.
%H V. E. Hoggatt, <a href="https://www.fq.math.ca/Problems/ElemProSolnAugust2021.pdf">The Fifth Oldie from the Vault. Problem B-415</a>, Elementary Problems and Solutions, Fibonacci Quart. 59 (2021), no. 3, pp. 274-275.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=3">Encyclopedia of Combinatorial Structures 3</a>
%H Juhani Karhumäki, S. Puzynina, M. Rao, and M. A. Whiteland, <a href="https://arxiv.org/abs/1605.03319">On cardinalities of k-abelian equivalence classes</a>, arXiv preprint arXiv:1605.03319 [math.CO], 2016.
%H J. Riordan, <a href="/A001867/a001867.pdf">Letter to N. J. A. Sloane, Jul. 1978</a>
%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F a(n) = (1/n)*Sum_{d|n} phi(d)*3^(n/d), n>0.
%F G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 3*x^n)/n). - _Herbert Kociemba_, Nov 01 2016
%F a(n) ~ 3^n/n. - _Vaclav Kotesovec_, Nov 01 2016
%F a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 3^gcd(n,k). - _Ilya Gutkovskiy_, Apr 16 2021
%F a(0) = 1; a(n) = (1/n)*Sum_{k=1..n} 3^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - _Richard L. Ollerton_, May 07 2021
%p with(numtheory): A001867:= n-> `if` (n=0, 1, add (phi(d)* 3^(n/d), d=divisors(n))/n): seq (A001867(n), n=0..40);
%p spec := [N, {N=Cycle(bead), bead=Union(R,G,B), R=Atom, B=Atom, G=Atom}]; [seq(combstruct[count](spec, size=n), n=1..40)];
%t Prepend[Table[CyclicGroupIndex[n,t]/.Table[t[i]->3,{i,1,n}],{n,1,28}],1] (* _Geoffrey Critzer_, Sep 16 2011 *)
%t mx=40;CoefficientList[Series[1-Sum[EulerPhi[i] Log[1-3*x^i]/i,{i,1,mx}],{x,0,mx}],x] (* _Herbert Kociemba_, Nov 01 2016 *)
%t k=3; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/n, {n, 1, 30}], 1] (* _Robert A. Russell_, Sep 21 2018 *)
%o (PARI) a(n)=if (n==0, 1, 1/n * sumdiv(n, d, eulerphi(d)*3^(n/d) )); /* _Joerg Arndt_, Jul 04 2011 */
%Y Column 3 of A075195.
%Y Cf. A054610.
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_