|
Search: id:A000358
|
|
|
| A000358 |
|
Number of binary necklaces of length n with no subsequence 00. |
|
+0
6
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 119
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Index entries for sequences related to necklaces
|
|
FORMULA
|
1/n sum_{ d divides n } totient(n/d) [ Fib(d-1)+Fib(d+1) ].
|
|
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);
|
|
CROSSREFS
|
Sequence in context: A090492 A103609 A129526 this_sequence A032244 A063988 A097450
Adjacent sequences: A000355 A000356 A000357 this_sequence A000359 A000360 A000361
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Frank Ruskey (fruskey(AT)cs.uvic.ca)
|
|
|
Search completed in 0.002 seconds
|
