A001867 Number of n-bead necklaces with 3 colors.
1, 3, 6, 11, 24, 51, 130, 315, 834, 2195, 5934, 16107, 44368, 122643, 341802, 956635, 2690844, 7596483, 21524542, 61171659, 174342216, 498112275, 1426419858, 4093181691, 11767920118, 33891544419, 97764131646, 282429537947, 817028472960, 2366564736723
Offset: 0
References
- J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 162.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).
Links
- T. D. Noe, Table of n, a(n) for n = 0..200
- Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, Conjugation, loop and closure invariants of the iterated-integrals signature, arXiv:2412.19670 [math.RA], 2024. See pp. 6, 20.
- E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
- V. E. Hoggatt, The Fifth Oldie from the Vault. Problem B-415, Elementary Problems and Solutions, Fibonacci Quart. 59 (2021), no. 3, pp. 274-275.
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 3
- Juhani Karhumäki, S. Puzynina, M. Rao, and M. A. Whiteland, On cardinalities of k-abelian equivalence classes, arXiv preprint arXiv:1605.03319 [math.CO], 2016.
- J. Riordan, Letter to N. J. A. Sloane, Jul. 1978
- Index entries for sequences related to necklaces
Programs
-
Maple
with(numtheory): A001867:= n-> `if` (n=0, 1, add (phi(d)* 3^(n/d), d=divisors(n))/n): seq (A001867(n), n=0..40); 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)];
-
Mathematica
Prepend[Table[CyclicGroupIndex[n,t]/.Table[t[i]->3,{i,1,n}],{n,1,28}],1] (* Geoffrey Critzer, Sep 16 2011 *) 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 *) k=3; 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)*3^(n/d) )); /* Joerg Arndt, Jul 04 2011 */
Formula
a(n) = (1/n)*Sum_{d|n} phi(d)*3^(n/d), n>0.
G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 3*x^n)/n. - Herbert Kociemba, Nov 01 2016
a(n) ~ 3^n/n. - Vaclav Kotesovec, Nov 01 2016
a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 3^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021
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
Comments