login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000358 Number of binary necklaces of length n with no subsequence 00. 8
1, 2, 2, 3, 3, 5, 5, 8, 10, 15, 19, 31, 41, 64, 94, 143, 211, 329, 493, 766, 1170, 1811, 2787, 4341, 6713, 10462, 16274, 25415, 39651, 62075, 97109, 152288, 238838, 375167, 589527, 927555, 1459961, 2300348, 3626242, 5721045, 9030451, 14264309, 22542397, 35646312, 56393862, 89264835, 141358275 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

a(n) is also the number of inequivalent compositions of n into parts 1 and 2 where two compositions are considered to be equivalent if one is a cyclic rotation of the other.  a(6)=5 because we have: 2+2+2, 2+2+1+1, 2+1+2+1, 2+1+1+1+1, 1+1+1+1+1+1. - Geoffrey Critzer, Feb 01 2014

REFERENCES

T. Helleseth and A. Kholosha, Bent functions and their connections to combinatorics, in Surveys in Combinatorics 2013, edited by Simon R. Blackburn, Stefanie Gerke, Mark Wildon, Camb. Univ. Press, 2013.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..1000

A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, et al., Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings, 2014.

M. Assis, J. L. Jacobsen, I. Jensen, J.-M. Maillard and B. M. McCoy, Integrability vs non-integrability: Hard hexagons and hard squares compared, arXiv preprint 1406.5566 [math-ph], 2014.

P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 119

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Index entries for sequences related to necklaces

FORMULA

a(n) = (1/n) * sum_{ d divides n } totient(n/d) [ Fib(d-1)+Fib(d+1) ].

G.f. = sum(k>=1, phi(k)/k * log( 1/(1-B(x^k)) ) ) where B(x)=x*(1+x). - Joerg Arndt, Aug 06 2012

a(n) ~ ((1+sqrt(5))/2)^n / n. - Vaclav Kotesovec, Sep 12 2014

MAPLE

A000358 := proc(n) local sum; sum := 0; for d in divisors(n) do sum := sum + phi(n/d)*(fibonacci(d+1)+fibonacci(d-1)) od; RETURN(sum/n); end;

with(combstruct); spec := {A=Union(zero, Cycle(one), Cycle(Prod(zero, Sequence(one, card>0)))), one=Atom, zero=Atom}; seq(count([A, spec, unlabeled], size=i), i=1..30);

MATHEMATICA

nn=48; Drop[Map[Total, Transpose[Map[PadRight[#, nn]&, Table[ CoefficientList[ Series[CycleIndex[CyclicGroup[n], s]/.Table[s[i]->x^i+x^(2i), {i, 1, n}], {x, 0, nn}], x], {n, 0, nn}]]]], 1] (* Geoffrey Critzer, Feb 01 2014 *)

max = 50; B[x_] := x*(1+x); A = Sum[EulerPhi[k]/k*Log[1/(1-B[x^k])], {k, 1, max}]/x + O[x]^max; CoefficientList[A, x] (* Jean-Fran├žois Alcover, Feb 08 2016, after Joerg Arndt *)

Table[1/n * Sum[EulerPhi[n/d] Total@ Map[Fibonacci, d + # & /@ {-1, 1}], {d, Divisors@ n}], {n, 47}] (* Michael De Vlieger, Dec 28 2016 *)

PROG

(PARI)

N=66;  x='x+O('x^N);

B(x)=x*(1+x);

A=sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k))));

Vec(A)

/* Joerg Arndt, Aug 06 2012 */

CROSSREFS

Sequence in context: A232697 A129526 A246998 * A032244 A166588 A277321

Adjacent sequences:  A000355 A000356 A000357 * A000359 A000360 A000361

KEYWORD

nonn,easy

AUTHOR

Frank Ruskey

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 27 11:25 EDT 2017. Contains 288788 sequences.