|
|
A317586
|
|
Number of circular binary words of length n having the maximum possible number of distinct blocks of length floor(log_2 n) and floor(log_2 n)+1.
|
|
3
|
|
|
2, 1, 2, 1, 2, 3, 4, 2, 4, 3, 6, 13, 12, 20, 32, 16, 32, 36, 68, 141, 242, 407, 600, 898, 1440, 1812, 2000, 2480, 2176, 2816, 4096, 2048, 4096, 3840, 7040, 13744, 28272, 54196, 88608, 160082, 295624, 553395, 940878, 1457197, 2234864, 3302752, 4975168, 7459376
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
A circular binary word (a.k.a. "necklace") can be viewed as a representative of the equivalence class under cyclic shift.
The words counted by this sequence have 2^i distinct blocks of length i = floor(log_2 n) and n distinct blocks of length i+1.
This sequence counts a certain natural generalization of de Bruijn words, which are cyclic words of length 2^n containing all n-bit blocks as subwords.
|
|
LINKS
|
|
|
EXAMPLE
|
For n = 6 the 3 possibilities are {000111, 001011, 001101}. Each contains all 4 blocks of length 2, and 6 distinct blocks of length 3 (when considered circularly).
|
|
CROSSREFS
|
Cf. A016031, which gives the value of this sequence evaluated at powers of 2.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Terms a(33)-a(48) provided by Štěpán Holub
|
|
STATUS
|
approved
|
|
|
|