cp's OEIS Frontend

A001867 Number of n-bead necklaces with 3 colors.

%I A001867 M2548 N1008 #90 Jan 05 2025 19:51:32
%S A001867 1,3,6,11,24,51,130,315,834,2195,5934,16107,44368,122643,341802,
%T A001867 956635,2690844,7596483,21524542,61171659,174342216,498112275,
%U A001867 1426419858,4093181691,11767920118,33891544419,97764131646,282429537947,817028472960,2366564736723
%N A001867 Number of n-bead necklaces with 3 colors.
%C A001867 From _Richard L. Ollerton_, May 07 2021: (Start)
%C A001867 Here, as in A000031, turning over is not allowed.
%C A001867 (1/n) * Dirichlet convolution of phi(n) and 3^n, n>0. (End)
%D A001867 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 162.
%D A001867 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001867 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A001867 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).
%H A001867 T. D. Noe, <a href="/A001867/b001867.txt">Table of n, a(n) for n = 0..200</a>
%H A001867 Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, <a href="https://arxiv.org/abs/2412.19670">Conjugation, loop and closure invariants of the iterated-integrals signature</a>, arXiv:2412.19670 [math.RA], 2024. See pp. 6, 20.
%H A001867 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 A001867 V. E. Hoggatt, <a href="https://web.archive.org/web/2024*/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 A001867 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=3">Encyclopedia of Combinatorial Structures 3</a>
%H A001867 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 A001867 J. Riordan, <a href="/A001867/a001867.pdf">Letter to N. J. A. Sloane, Jul. 1978</a>
%H A001867 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A001867 a(n) = (1/n)*Sum_{d|n} phi(d)*3^(n/d), n>0.
%F A001867 G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 3*x^n)/n. - _Herbert Kociemba_, Nov 01 2016
%F A001867 a(n) ~ 3^n/n. - _Vaclav Kotesovec_, Nov 01 2016
%F A001867 a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 3^gcd(n,k). - _Ilya Gutkovskiy_, Apr 16 2021
%F A001867 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 A001867 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 A001867 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 A001867 Prepend[Table[CyclicGroupIndex[n,t]/.Table[t[i]->3,{i,1,n}],{n,1,28}],1]  (* _Geoffrey Critzer_, Sep 16 2011 *)
%t A001867 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 A001867 k=3; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/n, {n, 1, 30}], 1] (* _Robert A. Russell_, Sep 21 2018 *)
%o A001867 (PARI) a(n)=if (n==0, 1, 1/n * sumdiv(n, d, eulerphi(d)*3^(n/d) )); /* _Joerg Arndt_, Jul 04 2011 */
%Y A001867 Column 3 of A075195.
%Y A001867 Cf. A054610.
%K A001867 nonn,easy,nice
%O A001867 0,2
%A A001867 _N. J. A. Sloane_