%I #30 Apr 17 2021 09:08:01
%S 1,9,45,249,1665,11817,88725,683289,5381685,43046889,348684381,
%T 2852823609,23535840225,195528140649,1634056945605,13726075481049,
%U 115813764494505,981010688215689,8338590871415805,71097458824894329,607883273127192897
%N Number of n-bead necklaces with 9 colors.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Necklace.html">Necklace.</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)*9^(n/d), n > 0.
%F G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 9*x^n)/n. - _Herbert Kociemba_, Nov 02 2016 [corrected by _Ilya Gutkovskiy_, Apr 17 2021]
%F a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 9^gcd(n,k). - _Ilya Gutkovskiy_, Apr 17 2021
%e G.f. = 1 + 9*x + 45*x^2 + 249*x^3 + 1665*x^4 + 11817*x^5 + 88725*x^6 + ...
%p with(combstruct):A:=[N,{N=Cycle(Union(Z$9))},unlabeled]: seq(count(A,size=n),n=0..20); # _Zerinvary Lajos_, Dec 05 2007
%t mx=40; CoefficientList[Series[1-Sum[EulerPhi[i] Log[1-9*x^i]/i, {i, 1, mx}], {x, 0, mx}], x] (* _Herbert Kociemba_, Nov 02 2016 *)
%t k=9; 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)*9^(n/d))); \\ _Altug Alkan_, Sep 21 2018
%Y Column 9 of A075195.
%Y Cf. A054616.
%K nonn
%O 0,2
%A _N. J. A. Sloane_, Apr 16 2000
%E Edited by _Christian G. Bower_, Sep 07 2002
%E a(0) corrected by _Herbert Kociemba_, Nov 02 2016
|