A045653 -id:A045653 - cp's OEIS frontend

A045654 Number of 2n-bead balanced binary strings, rotationally equivalent to complement.

1, 2, 6, 8, 22, 32, 72, 128, 278, 512, 1056, 2048, 4168, 8192, 16512, 32768, 65814, 131072, 262656, 524288, 1049632, 2097152, 4196352, 8388608, 16781384, 33554432, 67117056, 134217728, 268451968, 536870912, 1073774592, 2147483648, 4295033110, 8589934592

Offset: 0

David W. Wilson

			From _Andrew Howroyd_, Jul 06 2025: (Start)
The a(1) = 2 length 2 balanced binary strings are: 01, 10.
The a(2) = 6 strings are: 0101, 1010, 0011, 0110, 1100, 1001.
The a(3) = 8 strings are: 010101, 101010, 000111, 001110, 011100, 111000, 110001, 100011. (End)

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Tilman Piesk, Row sums of triangle derived from A385665
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A000984, A045653, A045655, A045656, A045663, A127804, A385665.

a:= proc(n) option remember;
      2^n+`if`(n::even and n>0, a(n/2), 0)
    end:
seq(a(n), n=0..33);  # Alois P. Heinz, Jul 01 2025

a(n)={if(n==0, 1, my(s=0); while(n%2==0, s+=2^n; n/=2); s + 2^n)} \\ Andrew Howroyd, Sep 22 2019

def A045654(n): return sum(1<<(n>>k) for k in range((~n & n-1).bit_length()+1)) if n else 1 # Chai Wah Wu, Jul 22 2024

a(0)=1, a(2n) = a(n)+2^(2n), a(2n+1) = 2^(2n+1). - Ralf Stephan, Jun 07 2003
G.f.: 1/(1-x) + sum(k>=0, t(1+2t-2t^2)/(1-t^2)/(1-2t), t=x^2^k). - Ralf Stephan, Aug 30 2003
For n >= 1, a(n) = Sum_{k=0..A007814(n)} 2^(n/2^k). - David W. Wilson, Jan 01 2012
Inverse Moebius transform of A045663. - Andrew Howroyd, Sep 15 2019
a(n) = 2*A127804(n-1) for n > 0. - Tilman Piesk, Jul 05 2025
a(n) = Sum_{k=1..n} 2 * n * A385665(n,k) / k. - Tilman Piesk, Jul 07 2025

A045655 Number of 2n-bead balanced binary strings, rotationally equivalent to reversed complement.

Original entry on oeis.org

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

Offset: 0

David W. Wilson

nonn

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

			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.

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.

Cf. A000031 counts the string classes.

Cf. A000984, A023900, A045664, A045653, A045654, A045656.

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 *)

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

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

a(n) = Sum_{d|n} A023900(n/d)*d*2^d. - Andrew Howroyd, Sep 15 2019

A045656 Number of 2n-bead balanced binary strings, rotationally equivalent to reverse, complement and reversed complement.

Original entry on oeis.org

1, 2, 6, 8, 22, 32, 48, 100, 150, 260, 336, 684, 784, 1640, 1868, 3728, 4246, 8672, 9372, 19420, 20752, 42736, 45700, 94164, 98832, 204632, 214584, 441764, 460524, 950216, 985968, 2031556, 2101398, 4323888, 4465056, 9174400, 9444988

Offset: 0

David W. Wilson

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A000984, A023900, A045665, A045653, A045654, A045655, A045674.

b[n_] := Module[{t = 0, r = n}, If[n == 0, 1,  While[Mod[r, 2] == 0, r = r/2; t += 2^(r - 1)]; t + 2^Quotient[r, 2]]];
c[n_] := Sum[MoebiusMu[d]*d, {d, Divisors[n]}];
a[n_] := If[n == 0, 1, 2*Sum[c[n/d]*d*b[d], {d, Divisors[n]}]];
a /@ Range[0, 36] (* Jean-François Alcover, Sep 23 2019, from PARI *)

\\ here b(n) is A045674,  c(n) is A023900.
b(n) = if(n<1, n==0, my(t=0, r=n); while(r%2==0, r=r/2; t+=2^(r-1)); t + 2^(r\2));
c(n) = {sumdiv(n,d, moebius(d)*d)}
a(n) = if(n<1, n==0, 2*sumdiv(n, d, c(n/d)*d*b(d))); \\ Andrew Howroyd, Sep 15 2019

From Andrew Howroyd, Sep 15 2019: (Start)
Inverse Moebius transform of A045665.
a(n) = 2*Sum_{d|n} A023900(n/d)*d*A045674(d) for n > 0. (End)

A045657 Number of 2n-bead balanced binary strings, rotationally inequivalent to reverse, complement and reversed complement.

Original entry on oeis.org

0, 0, 0, 0, 0, 80, 384, 2352, 9856, 42840, 169360, 676720, 2631072, 10265216, 39779600, 154498280, 599565952, 2330826752, 9068429544, 35332969392, 137817174800, 538204065336, 2103971573264, 8233197139552, 32247054724768

Offset: 0

David W. Wilson

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A000984, A045653, A045654, A045655, A045656, A045666.

From Andrew Howroyd, Sep 15 2019: (Start)
Inverse Moebius transform of A045666.
a(n) = A000984(n) - A045653(n) - A045654(n) - A045655(n) + 2*A045656(n). (End)

A045658 Number of 2n-bead balanced binary strings, rotationally equivalent to reverse, inequivalent to complement and reversed complement.

Original entry on oeis.org

0, 0, 0, 0, 16, 20, 168, 168, 912, 972, 4620, 4840, 21064, 22360, 93912, 99080, 406416, 428876, 1739220, 1828104, 7364236, 7716408, 30987704, 32355664, 129676104, 135002920, 540592520, 561188088, 2245972472, 2325812528

Offset: 0

David W. Wilson

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A045653, A045656, A045667.

From Andrew Howroyd, Sep 15 2019: (Start)
Inverse Moebius transform of A045667.
a(n) = A045653(n) - A045656(n). (End)

cp's OEIS Frontend

A045654 Number of 2n-bead balanced binary strings, rotationally equivalent to complement.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Python

Formula

A045655 Number of 2n-bead balanced binary strings, rotationally equivalent to reversed complement.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A045656 Number of 2n-bead balanced binary strings, rotationally equivalent to reverse, complement and reversed complement.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A045657 Number of 2n-bead balanced binary strings, rotationally inequivalent to reverse, complement and reversed complement.

Views

Author

Keywords

Links

Crossrefs

Formula

A045658 Number of 2n-bead balanced binary strings, rotationally equivalent to reverse, inequivalent to complement and reversed complement.

Views

Author

Keywords

Links

Crossrefs

Formula