A209970 a(n) = 2^n - A000031(n).

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

Offset: 0

Author

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

Keywords

• nonn

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.

Crossrefs

Cf. A000031, A210109, A209919.