cp's OEIS Frontend

A001868 Number of n-bead necklaces with 4 colors.

%I A001868 M3390 N1370 #87 Jan 03 2025 12:29:53
%S A001868 1,4,10,24,70,208,700,2344,8230,29144,104968,381304,1398500,5162224,
%T A001868 19175140,71582944,268439590,1010580544,3817763740,14467258264,
%U A001868 54975633976,209430787824,799645010860,3059510616424,11728124734500,45035996273872,173215372864600,667199944815064
%N A001868 Number of n-bead necklaces with 4 colors.
%C A001868 From _Richard L. Ollerton_, May 07 2021: (Start)
%C A001868 Here, as in A000031, turning over is not allowed.
%C A001868 (1/n) * Dirichlet convolution of phi(n) and 4^n, n>0. (End)
%D A001868 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 162.
%D A001868 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001868 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A001868 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).
%H A001868 T. D. Noe, <a href="/A001868/b001868.txt">Table of n, a(n) for n=0..200</a>
%H A001868 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 p. 21.
%H A001868 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 A001868 Yi Hu, <a href="https://hdl.handle.net/10161/23828">Numerical Transfer Matrix Method of Next-nearest-neighbor Ising Models</a>, Master's Thesis, Duke Univ. (2021).
%H A001868 Yi Hu and Patrick Charbonneau, <a href="https://arxiv.org/abs/2106.08442">Numerical transfer matrix study of frustrated next-nearest-neighbor Ising models on square lattices</a>, arXiv:2106.08442 [cond-mat.stat-mech], 2021.
%H A001868 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=4">Encyclopedia of Combinatorial Structures 4</a>
%H A001868 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 A001868 J. Riordan, <a href="/A001867/a001867.pdf">Letter to N. J. A. Sloane, Jul. 1978</a>
%H A001868 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A001868 a(n) = (1/n)*Sum_{d|n} phi(d)*4^(n/d) = A054611(n)/n, n>0.
%F A001868 G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 4*x^n)/n. - _Herbert Kociemba_, Nov 01 2016
%F A001868 a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 4^gcd(n,k). - _Ilya Gutkovskiy_, Apr 17 2021
%F A001868 a(0) = 1; a(n) = (1/n)*Sum_{k=1..n} 4^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - _Richard L. Ollerton_, May 07 2021
%p A001868 A001868 := proc(n) local d,s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+phi(d)*4^(n/d); od; RETURN(s/n); fi; end;
%t A001868 a[n_] := (1/n)*Total[ EulerPhi[#]*4^(n/#) &  /@ Divisors[n]]; a[0] = 1; Table[a[n], {n, 0, 24}] (* _Jean-François Alcover_, Oct 21 2011 *)
%t A001868 mx=40;CoefficientList[Series[1-Sum[EulerPhi[i] Log[1-4*x^i]/i,{i,1,mx}],{x,0,mx}],x] (* _Herbert Kociemba_, Nov 01 2016 *)
%t A001868 k=4; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/n, {n, 1, 30}], 1] (* _Robert A. Russell_, Sep 21 2018 *)
%o A001868 (PARI) a(n) = if (n, sumdiv(n, d, eulerphi(d)*4^(n/d))/n, 1); \\ _Michel Marcus_, Nov 01 2016
%Y A001868 Column 4 of A075195.
%Y A001868 Cf. A054611.
%K A001868 nonn,nice,easy
%O A001868 0,2
%A A001868 _N. J. A. Sloane_