A054628 Number of n-bead necklaces with 9 colors.
1, 9, 45, 249, 1665, 11817, 88725, 683289, 5381685, 43046889, 348684381, 2852823609, 23535840225, 195528140649, 1634056945605, 13726075481049, 115813764494505, 981010688215689, 8338590871415805, 71097458824894329, 607883273127192897
Offset: 0
Keywords
Examples
G.f. = 1 + 9*x + 45*x^2 + 249*x^3 + 1665*x^4 + 11817*x^5 + 88725*x^6 + ...
Links
- Eric Weisstein's World of Mathematics, Necklace.
- Index entries for sequences related to necklaces
Programs
-
Maple
with(combstruct):A:=[N,{N=Cycle(Union(Z$9))},unlabeled]: seq(count(A,size=n),n=0..20); # Zerinvary Lajos, Dec 05 2007 -
Mathematica
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 *) k=9; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/n, {n, 1, 30}], 1] (* Robert A. Russell, Sep 21 2018 *) -
PARI
a(n)=if(n==0, 1, 1/n*sumdiv(n, d, eulerphi(d)*9^(n/d))); \\ Altug Alkan, Sep 21 2018
Formula
a(n) = (1/n)*Sum_{d|n} phi(d)*9^(n/d), n > 0.
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]
a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 9^gcd(n,k). - Ilya Gutkovskiy, Apr 17 2021
Extensions
Edited by Christian G. Bower, Sep 07 2002
a(0) corrected by Herbert Kociemba, Nov 02 2016