A045654 -id:A045654 - cp's OEIS frontend

A045674 Number of 2n-bead balanced binary necklaces which are equivalent to their reverse, complement and reversed complement.

1, 1, 2, 2, 4, 4, 6, 8, 12, 16, 20, 32, 38, 64, 72, 128, 140, 256, 272, 512, 532, 1024, 1056, 2048, 2086, 4096, 4160, 8192, 8264, 16384, 16512, 32768, 32908, 65536, 65792, 131072, 131344, 262144, 262656, 524288, 524820, 1048576, 1049600

Offset: 0

David W. Wilson

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Index entries for sequences related to necklaces

Cf. A045654.

a[0] = 1; a[n_] := a[n] = If[EvenQ[n], 2^(n/2-1) + a[n/2], 2^((n-1)/2)]; Table[a[n], {n, 0, 42}] (* Jean-François Alcover, Sep 30 2017 *)

a(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)); \\ Andrew Howroyd, Sep 29 2017

a(2n) = a(n) + 2^(n-1), a(2n+1) = 2^n. - Ralf Stephan, Nov 01 2003

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)

A127804 a(2n) = 2^(2n), a(2n+1) = 2^(2n+1) + a(n).

Original entry on oeis.org

1, 3, 4, 11, 16, 36, 64, 139, 256, 528, 1024, 2084, 4096, 8256, 16384, 32907, 65536, 131328, 262144, 524816, 1048576, 2098176, 4194304, 8390692, 16777216, 33558528, 67108864, 134225984, 268435456, 536887296, 1073741824, 2147516555, 4294967296, 8590000128

Offset: 0

Paul Barry, Jan 29 2007

From Tilman Piesk, Jun 30 2025: (Start)
The binary expansion of a(n), with bits least to most significant, is row n of A115361.
Number of 1's in binary expansion of a(n) is A001511(n+1).
Row sums of triangle A128807.
Row sums of triangle A127803.(End)

Tilman Piesk, Table of n, a(n) for n = 0..1023 (terms 0..61 from R. J. Mathar)
Tilman Piesk, Illustrated triangles with 32 rows:
related to necklaces (similar to A385665),
binary (A115361),
signed (A127803)
Tilman Piesk, Serration of Boolean functions (Wikiversity)

Cf. A045654, A128807, A127803, A115361, A187767, A001511.

A127804 := proc(n)
    add( A127803(n,k),k=0..n) ;
end proc: # R. J. Mathar, Feb 12 2024
# second Maple program:
a:= proc(n) option remember;
      2^n+`if`(n::odd, a((n-1)/2), 0)
    end:
seq(a(n), n=0..33);  # Alois P. Heinz, Jul 01 2025

rows = 30;
A[n_, k_] := If[k <= n, If[n <= 2 k, 1/(2*2^n - 1), 0], 0];
T = Table[A[n, k], {n, 0, rows-1}, {k, 0, rows-1}] // Inverse;
a[n_] := T[[n+1]] // Total;
Table[a[n], {n, 0, rows-1}] (* Jean-François Alcover, Jul 03 2018 *)

Conjecture: a(n) = 1 + A187767(n+1). - Andrew Howroyd, Jun 02 2017
From Tilman Piesk, Jun 30 2025: (Start)
a(n) = Sum_{i=0..A001511(n+1)-1} 2^((n+1) / 2^i - 1)
     = Sum_{i=0..A001511(n+1)-1} 2^floor(n / 2^i).
a(n) = A045654(n+1) / 2. (End)

Name changed by Tilman Piesk, Jun 30 2025

A385665 Triangle read by rows: T(n,k) is the number of 2n-bead balanced bicolor necklaces that can be rotated into their complements in k different ways.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 2, 1, 0, 1, 3, 0, 0, 0, 1, 5, 1, 1, 0, 0, 1, 9, 0, 0, 0, 0, 0, 1, 16, 2, 0, 1, 0, 0, 0, 1, 28, 0, 1, 0, 0, 0, 0, 0, 1, 51, 3, 0, 0, 1, 0, 0, 0, 0, 1, 93, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 170, 5, 2, 1, 0, 1, 0, 0, 0, 0, 0, 1, 315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Tilman Piesk, Jul 06 2025

Let X = A003239, Y = A000013, Z = A000048.
Rotations producing the complementary and the same necklace: CR and SR
There are X(n) balanced bicolor necklaces (BBN) of length 2n. (Central numbers of A047996.)
Y(n) among them are self-complementary (SCBBN). (They can be rotated so that all beads change color.)
Z(n) among those are primitive (not periodic). Each has a unique CR and SR. (SR is trivial rotation.)
The other Y(n)-Z(n) = A115118(n) SCBBN have multiple CR and SR.
T(n,k) SCBBN have k different CR and SR.
Column 1 is Z. The other columns have the same positive entries, each preceded by k-1 zeros.
One could add a column 0 to this triangle, whose entries would be X(n)-Y(n) = 2*A386388(n).
Triangle A385666 does the same for SR of all BBN.

			Triangle begins:
      k    1  2  3  4  5  6  7  8  9 10 11 12 12 14 15 16     A000013(n)
  n
  1        1  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .             1
  2        1  1  .  .  .  .  .  .  .  .  .  .  .  .  .  .             2
  3        1  .  1  .  .  .  .  .  .  .  .  .  .  .  .  .             2
  4        2  1  .  1  .  .  .  .  .  .  .  .  .  .  .  .             4
  5        3  .  .  .  1  .  .  .  .  .  .  .  .  .  .  .             4
  6        5  1  1  .  .  1  .  .  .  .  .  .  .  .  .  .             8
  7        9  .  .  .  .  .  1  .  .  .  .  .  .  .  .  .            10
  8       16  2  .  1  .  .  .  1  .  .  .  .  .  .  .  .            20
  9       28  .  1  .  .  .  .  .  1  .  .  .  .  .  .  .            30
 10       51  3  .  .  1  .  .  .  .  1  .  .  .  .  .  .            56
 11       93  .  .  .  .  .  .  .  .  .  1  .  .  .  .  .            94
 12      170  5  2  1  .  1  .  .  .  .  .  1  .  .  .  .           180
 13      315  .  .  .  .  .  .  .  .  .  .  .  1  .  .  .           316
 14      585  9  .  .  .  .  1  .  .  .  .  .  .  1  .  .           596
 15     1091  .  3  .  1  .  .  .  .  .  .  .  .  .  1  .          1096
 16     2048 16  .  2  .  .  .  1  .  .  .  .  .  .  .  1          2068
Examples for n=4 with necklaces of length 8:
T(4, 1) = 2 necklaces can be rotated into their complements in k=1 way:
 00001111 can be turned into 11110000 by rotating 4 places to the right.
 00101101 can be turned into 11010010 by rotating 4 places to the right.
T(4, 2) = 1 necklace can be rotated into its complement in k=2 ways:
 00110011 can be turned into 11001100 by rotating 2 or 6 places to the right.
T(4, 4) = 1 necklace can be rotated into its complement in k=4 ways:
 01010101 can be turned into 10101010 by rotating 1, 3, 5 or 7 places to the right.

Tilman Piesk, Rows 1..32, flattened
Tilman Piesk, Triangle T(n,k)*2*n/k with row sums A045654(n)

Cf. A003239, A000013, A000048, A385666, A386388, A045654, A115118.

T(n,k) = A000048(n/k) iff n divisible by k, otherwise 0.

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

A082392 Expansion of (1/x) * Sum_{k>=0} x^2^k / (1 - 2*x^2^(k+1)).

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 8, 1, 16, 4, 32, 2, 64, 8, 128, 1, 256, 16, 512, 4, 1024, 32, 2048, 2, 4096, 64, 8192, 8, 16384, 128, 32768, 1, 65536, 256, 131072, 16, 262144, 512, 524288, 4, 1048576, 1024, 2097152, 32, 4194304, 2048, 8388608, 2, 16777216

Offset: 0

Ralf Stephan, Jun 07 2003

Seiichi Manyama, Table of n, a(n) for n = 0..5000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A045654, A220466.

nmax := 48: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 0 to ceil(nmax/(p+2))+1 do a((2*n+1)*2^p-1) := 2^n od: od: seq(a(n), n=0..nmax); # Johannes W. Meijer, Feb 11 2013
A082392 := proc(n)
    2^A025480(n) ;
end proc:
seq(A082392(n),n=0..100) ; # R. J. Mathar, Jul 16 2020

a[n_] := 2^(((n+1)/2^IntegerExponent[n+1, 2]+1)/2-1);
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Sep 15 2023 *)

for(n=0, 50, l=ceil(log(n+1)/log(2)); t=polcoeff(sum(k=0, l, (x^2^k)/(1-2*x^2^(k+1)))/x + O(x^(n+1)), n); print1(t", ");) ;

a(0) = 1, a(2*n) = 2^n, a(2*n+1) = a(n).
a(n) = 2^A025480(n) = 2^(A003602(n)-1).
a((2*n+1)*2^p-1) = 2^n, p >= 0 and n >= 0. - Johannes W. Meijer, Feb 11 2013

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)

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 24, 28, 128, 252, 720, 1364, 3384, 6552, 14644, 29040, 61568, 122400, 253284, 504868, 1028880, 2054416, 4150652, 8294444, 16682552, 33349800, 66902472, 133775964, 267991444, 535920696, 1072788624, 2145452092

Offset: 0

David W. Wilson

nonn

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

Cf. A045654, A045656, A045668.

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

A374770 a(n) is the number of subsets x of Z_n such that #x * #y = n and x + y = Z_n for some subset y of Z_n.

Original entry on oeis.org

1, 3, 4, 11, 6, 24, 8, 59, 40, 68, 12, 284, 14, 192, 384, 795, 18, 1590, 20, 2876, 2552, 2192, 24, 17972, 3156, 8388, 20560, 35620, 30, 116474, 32, 144091, 178512, 131396, 94968, 1118426, 38, 524688, 1596560, 2569884, 42, 7280934, 44

Offset: 1

Rémy Sigrist, Jul 19 2024

			For n = 8: the principal subsets x (unique up to translation) alongside an appropriate subset y and the number of distinct translations are:
  x                  y                  #
  -----------------  -----------------  -
  {0}                {0,1,2,3,4,5,6,7}  8
  {0,1}              {0,2,4,6}          8
  {0,2}              {0,1,4,5}          8
  {0,3}              {0,2,4,6}          8
  {0,4}              {0,1,2,3}          4
  {0,1,2,3}          {0,4}              8
  {0,2,3,5}          {0,4}              8
  {0,1,4,5}          {0,2}              4
  {0,2,4,6}          {0,1}              2
  {0,1,2,3,4,5,6,7}  {0}                1
So a(8) = 8 + 8 + 8 + 8 + 4 + 8 + 8 + 4 + 2 + 1 = 59.

Rémy Sigrist, C++ program

Cf. A045654, A056045, A374712.

from itertools import combinations
from sympy import divisors, isprime
def A374770(n):
    if isprime(n): return n+1
    s = {}
    for d in divisors(n,generator=True):
        t = {}
        for a in combinations(range(n),d):
            for i in range(1,n):
                if (w:=tuple((i+b)%n for b in a)) in t:
                    t[w]+=1
                    break
            else:
                t[a] = 1
        s[d] = t
    c = 0
    for d in divisors(n,generator=True):
        for a in s[d]:
            for b in s[n//d]:
                if len({(x+y)%n for x in a for y in b})==n:
                    c += s[d][a]
                    break
    return c # Chai Wah Wu, Jul 22 2024

a(p) = p + 1 for any prime number p.

a(n) <= A056045(n).

cp's OEIS Frontend

A045674 Number of 2n-bead balanced binary necklaces which are equivalent to their reverse, complement and reversed complement.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

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

A127804 a(2n) = 2^(2n), a(2n+1) = 2^(2n+1) + a(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A385665 Triangle read by rows: T(n,k) is the number of 2n-bead balanced bicolor necklaces that can be rotated into their complements in k different ways.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A082392 Expansion of (1/x) * Sum_{k>=0} x^2^k / (1 - 2*x^2^(k+1)).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links