

A045655


Number of 2nbead balanced binary strings, rotationally equivalent to reversed complement.


6



1, 2, 6, 20, 54, 152, 348, 884, 1974, 4556, 10056, 22508, 48636, 106472, 228444, 491120, 1046454, 2228192, 4713252, 9961436, 20960904, 44038280, 92252100, 192937940, 402599676, 838860152, 1744723896, 3623869388, 7515962172
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

a(n) is the number of ordered pairs (a,b) of length n binary sequences such that a and b are equivalent by rotational symmetry.  Geoffrey Critzer, Dec 31 2011
a(n) is the weighted sum of binary strings of length n by their number of distinct images by rotation. There is a natural correspondence between the first 2^(n1) sequences (starting by a 0) and the 2^(n1) starting with a 1 by inversion. There is also an internal correspondance by order inversion.  Olivier Gérard, Jan 01 2011
The number of kcirculant n X n (0,1) matrices, which means the number of n X n binary matrices where rows from the 2nd row on are obtained from the preceding row by a cyclic shift by k columns for some 0 <= k < n.  R. J. Mathar, Mar 11 2017


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Chuan Guo, J. Shallit, A. M. Shur, On the Combinatorics of Palindromes and Antipalindromes, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
V. V. Strok, Circulant matrices and the spectra of de Bruijn graphs, Ukr. Math. J. 44 (11) (1992) 14461454.


FORMULA

For n >= 1, a(n) = Sum_{dn} A045664(d) = Sum_{dn} d*A027375(d) = Sum_{dn} d^2*A001037(d).


EXAMPLE

a(2)= 6 because there are 6 such ordered pairs of length 2 binary sequences: (00,00),(11,11),(01,01),(10,10),(01,10),(10,01).
a(3)= 20 because the classes of 3bit strings are 1*(000), 3*(001,010,100), 3*(011,110,101), 1*(111) = 1 + 9 + 9 + 1.


MATHEMATICA

f[n_] := 2*Plus @@ Table[ Length[ Union[ NestList[ RotateLeft, IntegerDigits[b, 2, n], n  1]]], {b, 0, 2^(n  1)  1}]; f[0] = 1; Array[f, 21, 0] (* Olivier Gérard, Jan 01 2012 *)


CROSSREFS

Cf. A000031 counts the string classes.
Sequence in context: A027558 A066397 A060344 * A110295 A027294 A231538
Adjacent sequences: A045652 A045653 A045654 * A045656 A045657 A045658


KEYWORD

nonn


AUTHOR

David W. Wilson


STATUS

approved



