The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A209970 a(n) = 2^n - A000031(n). 5
 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 2-divided 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,...,s-1} 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 -> s-i for i in A. Theorem: Let d(n) be the number of 2-divided 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 2-divided, 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 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

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

Last modified October 5 14:56 EDT 2022. Contains 357259 sequences. (Running on oeis4.)