A209970 - 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