A001868 Number of n-bead necklaces with 4 colors.
1, 4, 10, 24, 70, 208, 700, 2344, 8230, 29144, 104968, 381304, 1398500, 5162224, 19175140, 71582944, 268439590, 1010580544, 3817763740, 14467258264, 54975633976, 209430787824, 799645010860, 3059510616424, 11728124734500, 45035996273872, 173215372864600, 667199944815064
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 p. 21.
- E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
- Yi Hu, Numerical Transfer Matrix Method of Next-nearest-neighbor Ising Models, Master's Thesis, Duke Univ. (2021).
- Yi Hu and Patrick Charbonneau, Numerical transfer matrix study of frustrated next-nearest-neighbor Ising models on square lattices, arXiv:2106.08442 [cond-mat.stat-mech], 2021.
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 4
- 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
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;
-
Mathematica
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 *) 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 *) k=4; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/n, {n, 1, 30}], 1] (* Robert A. Russell, Sep 21 2018 *) -
PARI
a(n) = if (n, sumdiv(n, d, eulerphi(d)*4^(n/d))/n, 1); \\ Michel Marcus, Nov 01 2016
Formula
a(n) = (1/n)*Sum_{d|n} phi(d)*4^(n/d) = A054611(n)/n, n>0.
G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 4*x^n)/n. - Herbert Kociemba, Nov 01 2016
a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 4^gcd(n,k). - Ilya Gutkovskiy, Apr 17 2021
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
Comments