A045655 -id:A045655 - 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

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)

A045653 Number of 2n-bead balanced binary strings, rotationally equivalent to reverse.

Original entry on oeis.org

1, 2, 6, 8, 38, 52, 216, 268, 1062, 1232, 4956, 5524, 21848, 24000, 95780, 102808, 410662, 437548, 1748592, 1847524, 7384988, 7759144, 31033404, 32449828, 129774936, 135207552, 540807104, 561629852, 2246432996, 2326762744, 9306937416, 9617286180, 38468731942

Offset: 0

David W. Wilson

nonn

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

Cf. A000984, A023900, A045662, A045654, A045655, A045656.

c(n)={sumdiv(n,d, moebius(d)*d)} \\ A023900
a(n)={if(n<1, n==0, 2*sumdiv(n, d, c(n/d) * d * binomial(d-d%2, d\2)))} \\ Andrew Howroyd, Sep 15 2019

Inverse Moebius transform of A045662. - Andrew Howroyd, Sep 15 2019

Terms a(30) and beyond from Andrew Howroyd, Sep 15 2019

A283795 Triangle T(n,k) read by rows: the number of q-circulant n X n {0,1}-matrices where each row sum and each column sum equals k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 6, 6, 1, 1, 8, 14, 8, 1, 1, 20, 40, 40, 20, 1, 1, 12, 42, 44, 42, 12, 1, 1, 42, 126, 210, 210, 126, 42, 1, 1, 32, 136, 224, 350, 224, 136, 32, 1, 1, 54, 216, 546, 756, 756, 546, 216, 54, 1, 1, 40, 260, 480, 1200, 1032, 1200, 480, 260, 40, 1, 1, 110, 550, 1650, 3300, 4620, 4620, 3300, 1650, 550, 110, 1, 1, 48, 324, 992, 2538, 3168

Offset: 0

R. J. Mathar, Mar 16 2017

q-circulant matrices are constructed by fixing the first row and obtaining the remaining n-1 rows by circularly shifting values by q columns, any q from 0 to n-1.
The triangle is symmetric in each row because flipping 1's and 0's in a matrix gives also a circulant matrix with n-k ones in each row and column.
The number of 1-circulant matrices with k zeros in each row and each column is apparently given by Pascal's Triangle.
Is the column k=1 given by A002618?

			The triangle starts in row n=0 and column k=0 as:
1 rsum= 1
1 1 rsum= 2
1 2 1 rsum= 4
1 6 6 1 rsum= 14
1 8 14 8 1 rsum= 32
1 20 40 40 20 1 rsum= 122
1 12 42 44 42 12 1 rsum= 154
1 42 126 210 210 126 42 1 rsum= 758
1 32 136 224 350 224 136 32 1 rsum= 1136
1 54 216 546 756 756 546 216 54 1 rsum= 3146

P. Zellini, On some properties of circulant matrices, Lin. Alg. Applic. 26 (1979) 31-43

Cf. A045655.

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)

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

Original entry on oeis.org

0, 0, 0, 12, 32, 120, 300, 784, 1824, 4296, 9720, 21824, 47852, 104832, 226576, 487392, 1042208, 2219520, 4703880, 9942016, 20940152, 43995544, 92206400, 192843776, 402500844, 838655520, 1744509312, 3623427624, 7515501648

Offset: 0

David W. Wilson

nonn

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

Cf. A045655, A045656, A045669.

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

A245582 Number of binary strings of length n having a cyclic shift that is a palindrome.

Original entry on oeis.org

1, 2, 2, 8, 6, 32, 20, 100, 54, 260, 152, 684, 348, 1640, 884, 3728, 1974, 8672, 4556, 19420, 10056, 42736, 22508, 94164, 48636, 204632, 106472, 441764, 228444, 950216, 491120, 2031556, 1046454, 4323888, 2228192, 9174400, 4713252, 19398584

Offset: 0

Jeffrey Shallit, Jul 26 2014

nonn

Alternatively (Luke Schaeffer), those binary strings of length n that can be written as the concatenation of two palindromes, one of which has even length. - Jeffrey Shallit, Jan 28 2016

Apparently A045655 is a bisection. - R. J. Mathar, Mar 11 2017

			For n = 4 the function counts the strings 0000, 0011, 0110 and their bitwise complements.

Lars Blomberg, C# program for generating the sequence.

palQ[lst_] := lst==Reverse[lst]; a[n_] := (For[k=0; cnt=0, k<2^n, k++, bb = PadLeft[IntegerDigits[k, 2], n]; If[MatchQ[bb, {a___ /; palQ[{a}], b___ /; palQ[{b}]} /; EvenQ[Length[{a}]] || EvenQ[Length[{b}]]], cnt++]]; cnt); Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 25}] (* Jean-François Alcover, Jan 28 2016 *)

a(25)-a(37) from Lars Blomberg, Oct 20 2014

A283796 Triangle T(n,k) read by rows: the number of symmetric q-circulant n X n {0,1}-matrices where each row and each column sum equals k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 6, 6, 6, 1, 1, 6, 12, 12, 6, 1, 1, 8, 18, 22, 18, 8, 1, 1, 8, 24, 38, 38, 24, 8, 1, 1, 16, 38, 80, 86, 80, 38, 16, 1, 1, 10, 40, 88, 132, 132, 88, 40, 10, 1, 1, 12, 50, 128, 220, 262, 220, 128, 50, 12, 1, 1, 12, 60, 170, 340, 472, 472, 340, 170, 60, 12, 1

Offset: 0

R. J. Mathar, Mar 16 2017

Obtained by selecting matrices in A283795 which are symmetric, which means where the transpose of the binary matrix equals the matrix.

Is column k=1 the same as A235384?

			The matrix stars in rows n=0 and columns 0<=k<n as
1 rsum= 1
1 1 rsum= 2
1 2 1 rsum= 4
1 4 4 1 rsum= 10
1 6 6 6 1 rsum= 20
1 6 12 12 6 1 rsum= 38
1 8 18 22 18 8 1 rsum= 76
1 8 24 38 38 24 8 1 rsum= 142
1 16 38 80 86 80 38 16 1 rsum= 356
1 10 40 88 132 132 88 40 10 1 rsum= 542
1 12 50 128 220 262 220 128 50 12 1 rsum= 1084
1 12 60 170 340 472 472 340 170 60 12 1 rsum= 2110
1 24 92 282 586 936 1050 936 586 282 92 24 1 rsum= 4892
1 14 84 292 730 1302 1736 1736 1302 730 292 84 14 1 rsum= 8318

Cf. A235384, A045655.

A283797 Triangle T(n,k) read by rows: The number of q-circulant n X n {0,1}-matrices where each column sum, each row sum and the trace equal k.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 3, 3, 1, 1, 0, 8, 0, 1, 1, 15, 30, 30, 15, 1, 1, 0, 15, 0, 15, 0, 1, 1, 35, 105, 175, 175, 105, 35, 1, 1, 0, 64, 0, 192, 0, 64, 0, 1, 1, 27, 108, 390, 378, 378, 390, 108, 27, 1, 1, 0, 135, 0, 570, 0, 570, 0, 135, 0, 1, 1, 99, 495, 1485, 2970, 4158, 4158, 2970, 1485, 495, 99, 1, 1, 0, 72, 0

Offset: 0

R. J. Mathar, Mar 16 2017

Obtained from A283795 by selecting the circulant binary matrices where the trace also equals the row and column sum. These match Ryser's criterion for square binary matrices with equal sums in A283627, but do not need to obey A^2=J.

Apparently T(n,k) =0 for odd k if n is even.

			The triangle starts in row n=0 with columns 0<=k<=n as
1 rsum= 1
1 1 rsum= 2
1 0 1 rsum= 2
1 3 3 1 rsum= 8
1 0 8 0 1 rsum= 10
1 15 30 30 15 1 rsum= 92
1 0 15 0 15 0 1 rsum= 32
1 35 105 175 175 105 35 1 rsum= 632
1 0 64 0 192 0 64 0 1 rsum= 322
1 27 108 390 378 378 390 108 27 1 rsum= 1808
1 0 135 0 570 0 570 0 135 0 1 rsum= 1412
1 99 495 1485 2970 4158 4158 2970 1485 495 99 1 rsum= 18416
1 0 72 0 762 0 1616 0 762 0 72 0 1 rsum= 3286
1 143 858 3146 7865 14157 18876 18876 14157 7865 3146 858 143 1 rsum= 90092

Cf. A283795, A045655.

A283798 Triangle T(n,k) read by rows: the number of symmetric q-circulant n X n {0,1}-matrices where each column sum, each row sum and the trace equal k.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 3, 3, 1, 1, 0, 4, 0, 1, 1, 5, 10, 10, 5, 1, 1, 0, 9, 0, 9, 0, 1, 1, 7, 21, 35, 35, 21, 7, 1, 1, 0, 16, 0, 44, 0, 16, 0, 1, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 1, 0, 25, 0, 100, 0, 100, 0, 25, 0, 1, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1, 1, 0, 36

Offset: 0

R. J. Mathar, Mar 16 2017

			The triangle stars in row n=0 with columns 0<=k<=n as
1 rsum= 1
1  1 rsum= 2
1  0   1 rsum= 2
1  3   3   1 rsum= 8
1  0   4   0    1 rsum= 6
1  5  10  10    5    1 rsum= 32
1  0   9   0    9    0     1 rsum= 20
1  7  21  35   35   21     7     1 rsum= 128
1  0  16   0   44    0    16     0     1 rsum= 78
1  9  36  84  126  126    84    36     9     1 rsum= 512
1  0  25   0  100    0   100     0    25     0     1 rsum= 252
1 11  55 165  330  462   462   330   165    55    11     1 rsum= 2048
1  0  36   0  246    0   420     0   246     0    36     0 1 rsum= 986
1 13  78 286  715 1287  1716  1716  1287   715   286    78 13 1 rsum= 8192
1  0  49   0  441    0  1225     0  1225     0   441     0 49 0 1 rsum= 3432
1 15 105 475 1365 3045  5095  6435  6435  5095  3045  1365 475 105 15 1 rsum= 33072
1  0  64   0  880    0  3136     0  5292     0  3136     0 880 0 64 0 1 rsum= 13454
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 rsum= 131072

Cf. A045655, A283795.

Conjecture: T(n,k) = binomial(n,k) for odd n.

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

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

A045653 Number of 2n-bead balanced binary strings, rotationally equivalent to reverse.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A283795 Triangle T(n,k) read by rows: the number of q-circulant n X n {0,1}-matrices where each row sum and each column sum equals k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

A245582 Number of binary strings of length n having a cyclic shift that is a palindrome.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Extensions

A283796 Triangle T(n,k) read by rows: the number of symmetric q-circulant n X n {0,1}-matrices where each row and each column sum equals k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A283797 Triangle T(n,k) read by rows: The number of q-circulant n X n {0,1}-matrices where each column sum, each row sum and the trace equal k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A283798 Triangle T(n,k) read by rows: the number of symmetric q-circulant n X n {0,1}-matrices where each column sum, each row sum and the trace equal k.