|
%I M0563 N0202 #154 May 06 2021 08:14:46
%S 1,2,3,4,6,8,13,18,30,46,78,126,224,380,687,1224,2250,4112,7685,14310,
%T 27012,50964,96909,184410,352698,675188,1296858,2493726,4806078,
%U 9272780,17920860,34669602,67159050,130216124,252745368,490984488
%N Number of necklaces with n beads of 2 colors, allowing turning over (these are also called bracelets).
%C "Necklaces with turning over allowed" are usually called bracelets. - _Joerg Arndt_, Jun 10 2016
%D J. L. Fisher, Application-Oriented Algebra (1977), ISBN 0-7002-2504-8, circa p. 215.
%D Martin Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pages 245-246.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.
%H N. J. A. Sloane, <a href="/A000029/b000029.txt">Table of n, a(n) for n = 0..300</a>
%H Hoda Abbasizanjani and Oliver Kullmann, <a href="https://arxiv.org/abs/2003.03639">Classification of minimally unsatisfiable 2-CNFs</a>, arXiv:2003.03639 [cs.DM], 2020.
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 151
%H H. Bottomley, <a href="/A000029/a000029.gif">Illustration of initial terms</a>
%H Emanuele Brugnoli, <a href="https://dx.doi.org/10.1002/jcd.21558">Enumerating the Walecki-Type Hamiltonian Cycle Systems</a>, Journal of Combinatorial Designs, Volume 25, Issue 11, November 2017, pp. 481-493.
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H S. N. Ethier and J. Lee, <a href="http://arxiv.org/abs/1202.2609">Parrondo games with spatial dependence</a>, arXiv preprint arXiv:1202.2609 [math.PR], 2012. - From _N. J. A. Sloane_, Jun 10 2012
%H S. N. Ethier and J. Lee, <a href="https://doi.org/10.1142/S0219477512500307">Parrondo games with spatial dependence II</a>, Fluctuation and Noise Letters 11 (4) (2012), 1250030.
%H S. N. Ethier, <a href="http://arxiv.org/abs/1301.2352">Counting toroidal binary arrays</a>, arXiv preprint arXiv:1301.2352 [math.CO], 2013.
%H S. N. Ethier, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Ethier/ethier2.html">Counting toroidal binary arrays</a>, Journal of Integer Sequences 16 (2013), Article 13.4.7.
%H N. J. Fine, <a href="http://projecteuclid.org/euclid.ijm/1255381350">Classes of periodic sequences</a>, Illinois J. Math., 2 (1958), 285-302.
%H 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 Jurij Kovič, <a href="https://doi.org/10.26493/1855-3974.997.7ef">Regular polygonal systems</a>, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 157-171.
%H Jia Liu, L. Lalouat, E. Drouard, and R. Orobtchouk, <a href="https://doi.org/10.1364/OE.24.001133">Binary coded patterns for photon control using necklace problem concept</a>, Optics Express Vol. 24, Issue 2, pp. 1133-1142 (2016).
%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H Zhe Sun, T. Suenaga, P. Sarkar, S. Sato, M. Kotani, and H. Isobe, <a href="https://doi.org/10.1073/pnas.1606530113">Stereoisomerism, crystal structures, and dynamics of belt-shaped cyclonaphthylenes</a>, Proc. Nat. Acad. Sci. USA, vol. 113 no. 29, pp. 8109-8114, doi: 10.1073/pnas.1606530113.
%H A. M. Uludag, A. Zeytin and M. Durmus, <a href="http://math.gsu.edu.tr/uludag/CHARKSANDDESSINS.pdf">Binary Quadratic Forms as Dessins</a>, 2012. - From _N. J. A. Sloane_, Dec 31 2012
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Necklace.html">Necklace</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/e.html">e</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Br#bracelets">Index entries for sequences related to bracelets</a>
%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F a(n) = Sum_{d divides n} phi(d)*2^(n/d)/(2*n) + either 2^((n - 1)/2) if n odd or 2^(n/2 - 1) + 2^(n/2 - 2) if n even.
%F G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n + (1 + x)^2/(1 - 2*x^2))/2. - _Herbert Kociemba_, Nov 02 2016
%F Equals (A000031 + A164090) / 2 = A000031 - A059076 = A059076 + A164090. - _Robert A. Russell_, Sep 24 2018
%F From _Richard L. Ollerton_, May 04 2021: (Start)
%F a(0) = 1; a(n) = Sum_{k=1..n} 2^gcd(n,k)/(2*n) + either 2^((n - 1)/2) if n odd or 2^(n/2 - 1) + 2^(n/2 - 2) if n even.
%F a(0) = 1; a(n) = A000031(n)/2 + (2^floor((n+1)/2) + 2^ceiling((n+1)/2))/4. See A051137. (End)
%e For n=2, the three bracelets are AA, AB, and BB. For n=3, the four bracelets are AAA, AAB, ABB, and BBB. - _Robert A. Russell_, Sep 24 2018
%p with(numtheory): A000029 := proc(n) local d,s; if n = 0 then return 1 else if n mod 2 = 1 then s := 2^((n-1)/2) else s := 2^(n/2-2)+2^(n/2-1) fi; for d in divisors(n) do s := s+phi(d)*2^(n/d)/(2*n) od; return s; fi end:
%t a[0] := 1; a[n_] := Fold[ # 1 + EulerPhi[ # 2]2^(n/ # 2)/(2n) &, If[OddQ[n], 2^((n - 1)/2), 2^(n/2 - 1) + 2^(n/2 - 2)], Divisors[n]]
%t mx=40;CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-2*x^n]/n,{n,mx}]+(1+x)^2/(1-2*x^2))/2,{x,0,mx}],x] (* _Herbert Kociemba_, Nov 02 2016 *)
%t a[0] = 1; a[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#)&]/(2*n); Array[a, 36, 0] (* _Jean-François Alcover_, Nov 05 2017 *)
%o (PARI) a(n)=if(n<1,!n,(n%2+3)/4*2^(n\2)+sumdiv(n,d,eulerphi(n/d)*2^d)/2/n)
%o (Python)
%o from sympy import divisors, totient
%o def a(n):
%o return 1 if n<1 else ((2**(n//2+1) if n%2 else 3*2**(n//2-1)) + sum(totient(n//d)*2**d for d in divisors(n))//n)//2
%o print([a(n) for n in range(51)]) # _Indranil Ghosh_, Apr 23 2017
%Y Row sums of triangle in A052307, second column of A081720, column 2 of A051137.
%Y Cf. A000011, A000013, A000031 (turning over not allowed), A001371 (primitive necklaces), A059076, A164090.
%Y Cf. A000031, A051137.
%K nonn,easy,nice,core
%O 0,2
%A _N. J. A. Sloane_
%E More terms from _Christian G. Bower_
|
