A000048 -id:A000048 - cp's OEIS frontend

A056303 Number of primitive (period n) n-bead necklace structures using exactly two different colored beads.

0, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, 2048, 3855, 7280, 13797, 26214, 49929, 95325, 182361, 349520, 671088, 1290555, 2485504, 4793490, 9256395, 17895679, 34636833, 67108864, 130150493, 252645135, 490853403, 954437120, 1857283155

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.
Identical to A000048 for n>1.
Number of binary Lyndon words of length n with an odd number of zeros. - Joerg Arndt, Oct 26 2015

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Column 2 of A107424.

Cf. A000007, A000048, A001037, A056295.

vector(100, n, sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d)))/(2*n)-!(n-1)) \\ Altug Alkan, Oct 26 2015

from sympy import divisors, mobius
def a000048(n): return 1 if n<1 else sum([mobius(d)*2**(n/d) for d in divisors(n) if d%2 == 1])/(2*n)
def a(n): return a000048(n) - 0**(n - 1) # Indranil Ghosh, Apr 28 2017

a(n) = Sum mu(d)*A056295(n/d) where d divides n.

a(n) = A000048(n) - A000007(n-1).

A115118 Number of imprimitive (periodic) n-bead binary necklaces with beads of 2 colors where the colors may be swapped but turning over is not allowed.

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 3, 1, 4, 2, 5, 1, 10, 1, 11, 5, 20, 1, 36, 1, 58, 11, 95, 1, 196, 4, 317, 30, 598, 1, 1153, 1, 2068, 95, 3857, 13, 7488, 1, 13799, 317, 26288, 1, 50531, 1, 95422, 1124, 182363, 1, 351764, 10, 671144, 3857, 1290874, 1, 2492820, 97, 4794104, 13799, 9256397, 1, 17923218, 1, 34636835, 49968, 67110932, 319

Offset: 0

Valery A. Liskovets, Jan 17 2006

a(p) = 1 for prime p. Presumably a(n) = A115121(n) = A066656(n)/2 for odd n.

Antti Karttunen, Table of n, a(n) for n = 0..1024

Cf. A000013, A000048, A385665.

Cf. A115121, A066656.

a[n_] := If[n == 0, 0, Sum[EulerPhi[2d] 2^(n/d) - Boole[OddQ[d]] MoebiusMu[d] 2^(n/d), {d, Divisors[n]}]/(2n)];
Array[a, 66, 0] (* Jean-François Alcover, Aug 29 2019 *)

a(n) = if (n==0, 0, (sumdiv(n, d, eulerphi(2*d) * 2^(n/d)) - sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d))))/(2*n)); \\ Michel Marcus, Oct 21 2017

a(n) = A000013(n) - A000048(n).

a(n) = Sum_{k=2..n} A385665(n,k). - Tilman Piesk, Aug 03 2025

More terms from Antti Karttunen, Oct 21 2017

A187767 Number of bicolored cyclic patterns n X n.

Original entry on oeis.org

0, 2, 3, 10, 15, 35, 63, 138, 255, 527, 1023, 2083, 4095, 8255, 16383, 32906, 65535, 131327, 262143, 524815, 1048575, 2098175, 4194303, 8390691, 16777215, 33558527, 67108863, 134225983, 268435455, 536887295, 1073741823, 2147516554, 4294967295, 8590000127, 17179869183

Offset: 1

Giovanni Resta, Jan 04 2013

nonn

A bicolored cyclic pattern is a 0-1 n x n matrix where the j-th row is equal to the first row rotated to the left by (j-1)*k places, with 1 <= k <= n a parameter. For example, with first row = 0110 we have
.
. (k=1) 0 1 1 0  (k=2) 0 1 1 0  (k=3) 0 1 1 0  (k=4) 0 1 1 0
.       1 1 0 0        1 0 0 1        0 0 1 1        0 1 1 0
.       1 0 0 1        0 1 1 0        1 0 0 1        0 1 1 0
.       0 0 1 1        1 0 0 1        1 1 0 0        0 1 1 0
The (2^n-2)*n matrices so obtained are reduced considering equivalent those obtained exchanging 0's and 1's and those which produce the same pattern, apart translation.

			a(4)=10 is represented below. See Links for more examples.
. 1000 0100 0010 0001 0101 1010 1001 0110 1100 0011
. 0100 0001 0100 0001 0101 0101 1100 1100 0011 0011
. 0010 0100 1000 0001 0101 1010 0110 1001 1100 0011
. 0001 0001 0001 0001 0101 0101 0011 0011 0011 0011

Andrew Howroyd, Table of n, a(n) for n = 1..200
Giovanni Resta, Picture explaining sequence definition.
Giovanni Resta, Pictures for a(2)-a(7).
Giovanni Resta, Pictures for a(8) and a(9).

The number of patterns made of vertical stripes only is A056295(n).

Cf. A000048, A056303, A127804.

cyPatt[n_]:=Block[{b,c},c[v_,q_:1]:=Table[RotateLeft[v,i q],{i,n}]; b=Union[(First@Union[c@#,c[1-#]])& /@ IntegerDigits[Range[2^n/2-1], 2,n]]; Union@Flatten[Table[c[e,j],{j,n},{e,b}],1]];
(*count*) a[n_] := Length@cyPatt@n; Print["Seq = ",a/@Range[12]];
(*show*) showP[p_] := GraphicsGrid@Partition[ArrayPlot/@p,8,8,1,Null];
showP[cyPatt[6]]

b(n)=sumdiv(n,d,(d%2)*(moebius(d)*2^(n/d)))/(2*n);
a(n)=sumdiv(n,d,d*b(d)) - 1; \\ Andrew Howroyd, Jun 02 2017

a(1) = 0; a(n) = 2^(n-1)-1 if n is odd, 2^(n-1)+a(n/2) if n is even (conjectured).

a(n) = -1 + Sum_{d|n} d*A000048(d). - Andrew Howroyd, Jun 02 2017

a(22)-a(35) from Andrew Howroyd, Jun 02 2017

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.

A054650 Nearest integer to 2^(n-1)/n.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 171, 315, 585, 1092, 2048, 3855, 7282, 13797, 26214, 49932, 95325, 182361, 349525, 671089, 1290555, 2485513, 4793490, 9256395, 17895697, 34636833, 67108864, 130150524, 252645135, 490853405, 954437177, 1857283155, 3616814565

Offset: 1

N. J. A. Sloane, Apr 17 2000

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A006788, A000048.

[Floor(2^(n-1)/n + 1/2): n in [1..45]]; // Vincenzo Librandi, Jul 21 2011

Table[Floor[2^(n-1)/n + 1/2], {n,40}] (* Harvey P. Dale, Jul 20 2011 *)

a(n) = round(hypergeometric([-n/2+1/2, -n/2+1], [3/2], 1)). - Peter Luschny, Sep 18 2014

A054662 Number of monic irreducible polynomials over GF(5) with fixed nonzero trace.

Original entry on oeis.org

1, 2, 8, 30, 125, 516, 2232, 9750, 43400, 195250, 887784, 4068740, 18780048, 87191964, 406901000, 1907343750, 8975758272, 42385503300, 200773540296, 953674218750, 4541306267856, 21674415838068, 103660251783288

Offset: 1

N. J. A. Sloane, Apr 18 2000

Also number of 5-ary Lyndon words with trace 1 mod 5; trace 2 mod 5; trace 3 mod 5; trace 4 mod 5; also number of 5-ary Lyndon words of trace 1 over GF(5), trace 2 over GF(5); trace 3 over GF(5); trace 4 over GF(5).

Frank Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
Frank Ruskey, Number of q-ary Lyndon words with given trace mod q
Frank Ruskey, Number of Lyndon words over GF(q) with given trace

Column 5 of A110540.

Cf. A000048, A051841, A046211, A046209, A054661, etc.

a(n) = sumdiv(n, d, (gcd(d, 5)==1)*(moebius(d)*5^(n/d)))/(5*n); \\ Seiichi Manyama, May 29 2024

a(n) = 1/(5*n) * Sum_{d|n, gcd(d,5)=1} mu(d) * 5^(n/d). - Seiichi Manyama, May 29 2024

More terms from James Sellers, Apr 19 2000

A179781 a(n) = AP(n) is the total number of aperiodic k-palindromes of n, 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 7, 12, 14, 27, 31, 54, 63, 119, 123, 240, 255, 490, 511, 990, 1015, 2015, 2047, 4020, 4092, 8127, 8176, 16254, 16383, 32607, 32767, 65280, 65503, 130815, 131061, 261576, 262143, 523775, 524223, 1047540, 1048575, 2096003, 2097151, 4192254

Offset: 1

John P. McSorley, Jul 26 2010

nonn

A k-composition of n is an ordered collection of k positive integers (parts) which sum to n.
A k-composition is aperiodic (primitive) if its period is k, or if it is not the concatenation of a smaller composition.
A k-palindrome of n is a k-composition of n which is a palindrome.
This sequence is AP(n), the total number of aperiodic k-palindromes of n, 1 <= k <= n.
For example AP(6)=5 because the number n=6
has 1 aperiodic 1-palindrome, namely 6 itself;
has 1 aperiodic 3-palindrome, namely 141;
has 2 aperiodic 4-palindromes, namely 2112 and 1221;
has 1 aperiodic 5-palindrome, namely 11211.
This gives a total of 1+1+2+1=5 aperiodic palindromes of 6.
Number of achiral set partitions of a primitive cycle of n elements having up to two different elements. - Robert A. Russell, Jun 19 2019

			For a(7)=7, the achiral set partitions are 0000001, 0000011, 0000101, 0000111, 0001001, 0010011, and 0010101. - _Robert A. Russell_, Jun 19 2019

John P. McSorley, Counting k-compositions of n with palindromic and related structures. Preprint, 2010.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Hunki Baek, Sejeong Bang, Dongseok Kim, Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014.

Row sums of A179519.

A000048 (oriented), A000046 (unoriented), A308706 (chiral), A016116 (not primitive). - Robert A. Russell, Jun 19 2019

a[n_] := DivisorSum[n, MoebiusMu[n/#] * 2^Floor[#/2]&];
Array[a, 44] (* Jean-François Alcover, Nov 04 2017 *)

a(n) = sumdiv(n, d, moebius(n/d) * 2^(d\2)); \\ Michel Marcus, Dec 09 2014

a(n) = Sum_{d | n} moebius(n/d)*2^(floor(d/2)) (see Baek et al. page 9). - Michel Marcus, Dec 09 2014
a(n) = 2*A000046(n) - A000048(n) = A000048(n) - 2*A308706(n) = A000046(n) - A308706(n). - Robert A. Russell, Jun 19 2019
A016116(n) =  Sum_{d|n} a(d). - Robert A. Russell, Jun 19 2019
G.f.: Sum_{k>=1} mu(k)*x^k*(1 + 2*x^k)/(1 - x^(2*k)). - Andrew Howroyd, Sep 27 2019

More terms from Michel Marcus, Dec 09 2014

A006788 a(n) = floor(2^(n-1)/n).

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1092, 2048, 3855, 7281, 13797, 26214, 49932, 95325, 182361, 349525, 671088, 1290555, 2485513, 4793490, 9256395, 17895697, 34636833, 67108864, 130150524, 252645135, 490853405, 954437176, 1857283155, 3616814565

Offset: 1

N. J. A. Sloane

nonn

Very close to A000048. [Fisher, 1989]

This is the number of nested polygons needed to produce a graph that is always concave, see the MathWorld article. - Jon Perry, Sep 15 2002

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
H. L. Fisher, Letter to N. J. A. Sloane, Mar 16 1989
Simon Michalowsky, Bahman Gharesifard and Christian Ebenbauer, A Lie bracket approximation approach to distributed optimization over directed graphs, arXiv:1711.05486 [math.OC], 2017.
Eric Weisstein's World of Mathematics, Happy End Problem

Cf. A054650, A000048.

[Floor(2^(n-1)/n) : n in [1..40]]; // Vincenzo Librandi, Sep 24 2011

Table[Quotient[2^n, 2*n], {n, 1, 60}] (* Vladimir Joseph Stephan Orlovsky, May 07 2011 *)

print([2**(n-1)//n for n in range(1, 40)]) # Gennady Eremin, Feb 04 2022

A006788 = lambda n: (1<A006788(n) for n in (1..38)] # Peter Luschny, Sep 18 2014

A056304 Number of primitive (period n) n-bead necklace structures using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 2, 5, 17, 43, 124, 338, 941, 2591, 7234, 20125, 56407, 158349, 446492, 1262225, 3580330, 10181479, 29031306, 82968799, 237642659, 682014587, 1960974220, 5647919640, 16292741605, 47069104274, 136166647110, 394418199725, 1143821887473, 3320790074371

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Column 3 of A107424.

Cf. A000048, A002075, A008683, A056288, A056296.

a(n) = Sum_{d|n} mu(d)*A056296(n/d), where mu = A008683 is the Möbius function.

a(n) = A002075(n) - A000048(n).

a(28)-a(31) from Pontus von Brömssen, Aug 04 2024

A110540 Invertible triangle: T(n,k) = number of k-ary Lyndon words of length n-k+1 with trace 1 modulo k.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 3, 2, 1, 0, 3, 6, 5, 2, 1, 0, 5, 16, 16, 8, 3, 1, 0, 9, 39, 51, 30, 12, 3, 1, 0, 16, 104, 170, 125, 54, 16, 4, 1, 0, 28, 270, 585, 516, 259, 84, 21, 4, 1, 0, 51, 729, 2048, 2232, 1296, 480, 128, 27, 5, 1, 0, 93, 1960, 7280, 9750, 6665, 2792, 819, 180, 33, 5, 1

Offset: 1

Paul Barry, Jul 25 2005

An invertible number triangle related to Lyndon words of trace 1.

			Rows begin
  1;
  0,  1;
  0,  1,   1;
  0,  1,   1,    1;
  0,  2,   3,    2,    1;
  0,  3,   6,    5,    2,    1;
  0,  5,  16,   16,    8,    3,   1;
  0,  9,  39,   51,   30,   12,   3,   1;
  0, 16, 104,  170,  125,   54,  16,   4,  1;
  0, 28, 270,  585,  516,  259,  84,  21,  4, 1;
  0, 51, 729, 2048, 2232, 1296, 480, 128, 27, 5, 1;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Frank Ruskey, Number of q-ary Lyndon words with given trace mod q
Frank Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
Frank Ruskey, Number of Lyndon words over GF(q) with given trace

Columns include A000048, A046211, A054660, A054662, A054666, A373277, A300674, A300675.

T[n_, k_]:=Sum[Boole[GCD[d, k] == 1]  MoebiusMu[d] k^((n - k + 1)/d), {d, Divisors[n - k + 1]}] /(k(n - k + 1)); Flatten[Table[T[n, k], {n, 12}, {k, n}]] (* Indranil Ghosh, Mar 27 2017 *)

for(n=1, 11, for(k=1, n, print1( sum(d=1,n-k+1, if(Mod(n-k+1, d)==0 && gcd(d, k)==1, moebius(d)*k^((n-k+1)/d), 0)/(k*(n-k+1)) ),", ");); print();) \\ Andrew Howroyd, Mar 26 2017

T(n, k) = (Sum_{d | n-k+1, gcd(d, k)=1} mu(d)*k^((n-k+1)/d))/(k*(n-k+1)).

Name clarified by Andrew Howroyd, Mar 26 2017

cp's OEIS Frontend

A056303 Number of primitive (period n) n-bead necklace structures using exactly two different colored beads.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

PARI

Python

Formula

A115118 Number of imprimitive (periodic) n-bead binary necklaces with beads of 2 colors where the colors may be swapped but turning over is not allowed.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A187767 Number of bicolored cyclic patterns n X n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

A054650 Nearest integer to 2^(n-1)/n.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A054662 Number of monic irreducible polynomials over GF(5) with fixed nonzero trace.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A179781 a(n) = AP(n) is the total number of aperiodic k-palindromes of n, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula