This site is supported by donations to The OEIS Foundation.

 Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS". Other ways to donate

 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: A058514 A182094 A001979 * A211392 A128516 A022569 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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.