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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A045655 Number of 2n-bead 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^(n-1) sequences (starting by a 0) and the 2^(n-1) starting with a 1 by inversion. There is also an internal correspondance by order inversion. - Olivier Gérard, Jan 01 2011

The number of k-circulant 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) 1446-1454.

FORMULA

For n >= 1, a(n) = Sum_{d|n} A045664(d) = Sum_{d|n} d*A027375(d) = Sum_{d|n} 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 3-bit 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

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 November 23 20:23 EST 2017. Contains 295141 sequences.