Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #18 Mar 30 2012 17:22:10
%S 0,0,1,4,10,24,50,108,220,452,916,1860,3744,7560,15202,30576,61420,
%T 123360,247542,496692,996088,1997272,4003558,8023884,16077964,
%U 32212248,64527436,129246660,258847876,518358120,1037949256,2078209980,4160747500,8329633416,16674575056,33378031536
%N a(n) = 2^n - A000031(n).
%C a(n) is also the number of 2-divided binary words of length n (see A210109 for definition, see A209919 for further details).
%C 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.
%C 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.
%C 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
%C Cor.: A000031(n) + A209970(n) = 2^n, A001867(n) + A210323(n) = 3^n, A001868(n) + A210424(n) = 4^n.
%Y Cf. A000031, A210109, A209919.
%K nonn
%O 0,4
%A _David Applegate_ and _N. J. A. Sloane_, Mar 17 2012