



0, 0, 1, 4, 10, 24, 50, 108, 220, 452, 916, 1860, 3744, 7560, 15202, 30576, 61420, 123360, 247542, 496692, 996088, 1997272, 4003558, 8023884, 16077964, 32212248, 64527436, 129246660, 258847876, 518358120, 1037949256, 2078209980, 4160747500, 8329633416, 16674575056, 33378031536
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

a(n) is also the number of 2divided binary words of length n (see A210109 for definition, see A209919 for further details).
This is a special case of a more general result: Let A={0,1,...,s1} be an alphabet of size s. Let A* = set of words over A. Let < denote lexicographic order on A*. Let f be the morphism on A* defined by i > si for i in A.
Theorem: Let d(n) be the number of 2divided words in A* of length n, and let b(n) be the number of rotationally inequivalent necklaces with n beads each in A. Then d(n)+b(n)=s^n.
Proof: Let w in A* have length n. If w is <= all of its cyclic shifts then w contributes to the b(n) count. Otherwise w = uv with vu < uv. But then f(w)=f(u)f(v) with f(u)f(v) < f(v)f(u) is 2divided, and w contributes to the count in d(n). QED
Cor.: A000031(n) + A209970(n) = 2^n, A001867(n) + A210323(n) = 3^n, A001868(n) + A210424(n) = 4^n.


LINKS

Table of n, a(n) for n=0..35.


CROSSREFS

Cf. A000031, A210109, A209919.
Sequence in context: A182094 A291949 A001979 * A211392 A309777 A128516
Adjacent sequences: A209967 A209968 A209969 * A209971 A209972 A209973


KEYWORD

nonn


AUTHOR

David Applegate and N. J. A. Sloane, Mar 17 2012


STATUS

approved



