|
|
A045655
|
|
Number of 2n-bead balanced binary strings, rotationally equivalent to reversed complement.
|
|
11
|
|
|
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 with 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
|
|
|
FORMULA
|
|
|
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 *)
|
|
PROG
|
(PARI) c(n)={sumdiv(n, d, moebius(d)*d)} \\ A023900
a(n)={if(n<1, n==0, sumdiv(n, d, c(n/d)*d*2^d))} \\ Andrew Howroyd, Sep 15 2019
|
|
CROSSREFS
|
Cf. A000031 counts the string classes.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|