login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

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

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

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.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 29 16:53 EDT 2017. Contains 287252 sequences.