A056278 -id:A056278 - cp's OEIS frontend

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

1, 1, 3, 6, 15, 27, 63, 120, 252, 495, 1023, 2010, 4095, 8127, 16365, 32640, 65535, 130788, 262143, 523770, 1048509, 2096127, 4194303, 8386440, 16777200, 33550335, 67108608, 134209530, 268435455, 536854005, 1073741823, 2147450880

Offset: 1

N. J. A. Sloane

Also number of compositions of n into relatively prime parts (that is, the gcd of all the parts is 1). Also number of subsets of {1,2,..,n} containing n and consisting of relatively prime numbers. - Vladeta Jovovic, Aug 13 2003
Also number of perfect parity patterns that have exactly n columns (see A118141). - Don Knuth, May 11 2006
a(n) is odd if and only if n is squarefree (Tim Keller). - Emeric Deutsch, Apr 27 2007
a(n) is a multiple of 3 for all n>=3 (see Problem 11161 link). - Emeric Deutsch, Aug 13 2008
Row sums of triangle A143424. - Gary W. Adamson, Aug 14 2008
a(n) is the number of monic irreducible polynomials with nonzero constant coefficient in GF(2)[x] of degree n. - Michel Marcus, Oct 30 2016
a(n) is the number of aperiodic compositions of n, the number of compositions of n with relatively prime parts, and the number of compositions of n with relatively prime run-lengths. - Gus Wiseman, Dec 21 2017

			For n=4, there are 6 compositions of n into coprime parts: <3,1>, <2,1,1>, <1,3>, <1,2,1>, <1,1,2>, and <1,1,1,1>.
From _Gus Wiseman_, Dec 19 2017: (Start)
The a(6) = 27 aperiodic compositions are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1221), (1311), (2112), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
The a(6) = 27 compositions into relatively prime parts are:
  (111111),
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1212), (1221), (1311), (2112), (2121), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (51).
The a(6) = 27 compositions with relatively prime run-lengths are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1131), (1212), (1221), (1311), (2112), (2121), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
(End)

H. O. Peitgen and P. H. Richter, The Beauty of Fractals, Springer-Verlag; contribution by A. Douady, p. 165.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 1..3322 (terms 1..300 from T. D. Noe)
Hunki Baek, Sejeong Bang, Dongseok Kim, and Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014. See Table 2.
Donald Knuth, Robin Chapman and Reiner Martin, Problem 11243, Perfect Parity Patterns, Am. Math. Monthly 115 (7) (2008) p 668, function c(n).
Emeric Deutsch and Lafayette College Problem Group, Problem 11161: Compositions without Common Factors, American Mathematical Monthly, vol. 114, No. 4, 2007, p. 363.
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
J. E. Iglesias, A formula for the number of closest packings of equal spheres having a given repeat period, Z. Krist. 155 (1981) 121-127, Table 2.
Wolfdieter Lang, Cantor's List of Real Algebraic Numbers of Heights 1 to 7, arXiv:2307.10645 [math.NT], 2023.
Nicolae Mihalache and Francois Vigneron, Factorization of the quadratic Misiurewicz-Thurston polynomials, arXiv:2506.17662 [math.DS], 2025. See p. 8.
Robert Munafo, Enumeration of Period-N Mu-Atoms
Jeffrey Shallit and N. J. A. Sloane, Correspondence 1974-1975
François Vigneron and Nicolae Mihalache, How to split a tera-polynomial, arXiv:2402.06083 [math.NA], 2024.
Index entries for sequences related to Lyndon words

Cf. A000837, A003239, A008683, A008965, A022553, A034738, A035928, A038199, A051168, A054525, A056267, A059966, A143424, A167606, A178472, A216954, A228369, A294859, A296302.
Equals A027375/2.
See A056278 for a variant.
First differences of A085945.
Column k=2 of A143325.
Row sums of A101391.

with(numtheory): a[1]:=1: a[2]:=1: for n from 3 to 32 do div:=divisors(n): a[n]:=2^(n-1)-sum(a[n/div[j]],j=2..tau(n)) od: seq(a[n],n=1..32); # Emeric Deutsch, Apr 27 2007
with(numtheory); A000740:=n-> add(mobius(n/d)*2^(d-1), d in divisors(n)); # N. J. A. Sloane, Oct 18 2012

a[n_] := Sum[ MoebiusMu[n/d]*2^(d - 1), {d, Divisors[n]}]; Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Feb 03 2012, after PARI *)

a(n) = sumdiv(n,d,moebius(n/d)*2^(d-1))

from sympy import mobius, divisors
def a(n): return sum([mobius(n // d) * 2**(d - 1) for d in divisors(n)])
[a(n) for n in range(1, 101)]  # Indranil Ghosh, Jun 28 2017

a(n) = Sum_{d|n} mu(n/d)*2^(d-1), Mobius transform of A011782. Furthermore, Sum_{d|n} a(d) = 2^(n-1).
a(n) = A027375(n)/2 = A038199(n)/2.
a(n) = Sum_{k=0..n} A051168(n,k)*k. - Max Alekseyev, Apr 09 2013
Recurrence relation: a(n) = 2^(n-1) - Sum_{d|n,d>1} a(n/d). (Lafayette College Problem Group; see the Maple program and Iglesias eq (6)). - Emeric Deutsch, Apr 27 2007
G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Oct 24 2018
G.f. satisfies Sum_{n>=1} A( (x/(1 + 2*x))^n ) = x. - Paul D. Hanna, Apr 02 2025

Connection with Mandelbrot set discovered by Warren D. Smith and proved by Robert Munafo, Feb 06 2000

Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012

A137651 Triangle read by rows: T(n,k) is the number of primitive (aperiodic) word structures of length n using exactly k different symbols.

Original entry on oeis.org

1, 0, 1, 0, 3, 1, 0, 6, 6, 1, 0, 15, 25, 10, 1, 0, 27, 89, 65, 15, 1, 0, 63, 301, 350, 140, 21, 1, 0, 120, 960, 1700, 1050, 266, 28, 1, 0, 252, 3024, 7770, 6951, 2646, 462, 36, 1, 0, 495, 9305, 34095, 42524, 22827, 5880, 750, 45, 1, 0, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55, 1

Offset: 1

Gary W. Adamson, Feb 01 2008

Row sums = A082951: (1, 1, 4, 13, 51, 197, ...).

			First few rows of the triangle are:
  1;
  0,   1;
  0,   3,   1;
  0,   6,   6,    1;
  0,  15,  25,   10,    1;
  0,  27,  89,   65,   15,   1;
  0,  63, 301,  350,  140,  21,  1;
  0, 120, 960, 1700, 1050, 266, 28, 1;
  ...
From _Andrew Howroyd_, Apr 03 2017: (Start)
Primitive word structures are:
n=1: a => 1
n=2: ab => 1
n=3: aab, aba, abb; abc => 3 + 1
n=4: aaab, aaba, aabb, abaa, abba, abbb => 6 (k=2)
     aabc, abac, abbc, abca, abcb, abcc => 6 (k=3)
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Columns 2-6 are A056278 (or A000740), A056279, A056280, A056281, A056282.
Row sums are A082951.
Cf. A054525, A008277, A327029.

rows = 10; t[n_, k_] := If[Divisible[n, k], MoebiusMu[n/k], 0]; A054525 = Array[t, {rows, rows}]; A008277 = Array[StirlingS2, {rows, rows}]; T = A054525 . A008277; Table[T[[n, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 07 2017 *)

T(n,k)={sumdiv(n, d, moebius(n/d)*stirling(d, k, 2))} \\ Andrew Howroyd, Aug 09 2018

# uses[DivisorTriangle from A327029]
# Computes an additional column (1,0,0,...)
# at the left hand side of the triangle.
DivisorTriangle(moebius, stirling_number2, 10) # Peter Luschny, Aug 24 2019

A054525 * A008277 as infinite lower triangular matrices. A054525 = Mobius transform, A008277 = Stirling2 triangle.

T(n,k) = Sum{d|n} mu(n/d) * Stirling2(d, k). - Andrew Howroyd, Aug 09 2018

Name changed and a(46)-a(66) from Andrew Howroyd, Aug 09 2018

A082951 Number of primitive (aperiodic) word structures of length n using an infinite alphabet.

Original entry on oeis.org

1, 1, 1, 4, 13, 51, 197, 876, 4125, 21142, 115922, 678569, 4213381, 27644436, 190898444, 1382958489, 10480138007, 82864869803, 682076784814, 5832742205056, 51724158119384, 474869816155870, 4506715737768752, 44152005855084345, 445958869290587567

Offset: 0

Vadim Ponomarenko (vadim123(AT)gmail.com), May 26 2003

Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same structure.

Row sums of triangle A137651. - Gary W. Adamson, Feb 01 2008

			There are A000110(3)=5 word structures of length 3: aaa, aab, aba, abb, abc. The first consists of 3 copies of a word of length 1; the other 4 are primitive. So a(3)=4.

Alois P. Heinz, Table of n, a(n) for n = 0..500

Cf. A000110, A056277, A056272, A056275, A056274, A056278.

Cf. A137651.

with(combinat,bell): with(numtheory): newb := proc(n) local s,i; s := 0; for i in divisors(n) do s := s+bell(i)*mobius(n/i): end do: end proc;
# second Maple program:
with(combinat): with(numtheory):
a:= proc(n) option remember;
      bell(n)-add(a(d), d=divisors(n) minus {n})
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 23 2015

a[n_] := DivisorSum[n, BellB[#] MoebiusMu[n/#]&]; a[0]=1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 23 2017 *)

a(n) = sum mu(c)*A000110(d) over all cd=n; equivalently, A000110(n) = sum a(k), where the sum is over all k|n.

1 + Sum_{n>=1} a(n)*x^n/(1 - x^n) is the g.f. of A000110. - Ilya Gutkovskiy, Mar 05 2018

More terms from Alois P. Heinz, Jan 23 2015

A179968 'AT(n,k)' triangle read by rows. AT(n,k) is the number of aperiodic k-compositions of n.

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 4, 6, 4, 0, 1, 4, 9, 8, 5, 0, 1, 6, 15, 20, 15, 6, 0, 1, 6, 21, 32, 35, 18, 7, 0, 1, 8, 27, 56, 70, 54, 28, 8, 0, 1, 8, 36, 80, 125, 120, 84, 32, 9, 0, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 0

Offset: 1

John P. McSorley, Aug 03 2010

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 at least two smaller compositions.
Let AT(n,k) denote the number of aperiodic k-compositions of n.
This sequence is the 'AT(n,k)' triangle read by rows.
If we form the row sum sequence of the 'AT(n, k)' triangle above we get sequence A056278, except for the first term.
If we form the triangle which counts the aperiodic k-compositions of n up to cyclic equivalence, ATE(n, k), and place an extra 0 at the end of each row of the 'ATE(n, k)' triangle, we get sequence A051168 (Lyndon words).

			The triangle begins
  1
  1, 0
  1, 2,  0
  1, 2,  3,  0
  1, 4,  6,  4,   0
  1, 4,  9,  8,   5,   0
  1, 6, 15, 20,  15,   6,  0
  1, 6, 21, 32,  35,  18,  7,  0
  1, 8, 27, 56,  70,  54, 28,  8, 0
  1, 8, 36, 80, 125, 120, 84, 32, 9, 0
For example, row 8 is 1, 6, 21, 32, 35, 18, 7, 0.
We have AT(8,2)=6 because there are 6 aperiodic 2-compositions of 8, namely: 17, 71, 26, 62, 35, 53. The remaining 2-composition of 8 is 44, it is not aperiodic.
We have AT(8,3)=21 because all 21 3-compositions of 8 are aperiodic.

John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010. [Apparently unpublished as of Mar 27 2017]

Andrew Howroyd, Table of n, a(n) for n = 1..1275
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

Cf. A051168, A056278.

T[n_, k_]:=(k/n) * Sum[MoebiusMu[d] Binomial[n/d, k/d], {d, Divisors[GCD[n, k]]}]; Flatten[Table[T[n, k], {n, 11}, {k, n}]] (* Indranil Ghosh, Mar 27 2017, after the formula by Andrew Howroyd *)

T(n,k) = k * A051168(n,k). - Andrew Howroyd, Mar 26 2017
T(n,k) = (k/n) * Sum_{d | gcd(n,k)} mu(d) * binomial(n/d,k/d). - Andrew Howroyd, Mar 26 2017
G.f.: Sum_{k>=1}mu(k)y^k A(x^k)/(1 - y^k A(x^k)) where mu(k) is the Moebius Mu function and A(x) = x/(1-x). - Geoffrey Critzer, Aug 05 2022

a(56)-a(66) from Andrew Howroyd, Mar 26 2017

cp's OEIS Frontend

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A137651 Triangle read by rows: T(n,k) is the number of primitive (aperiodic) word structures of length n using exactly k different symbols.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

Extensions

A082951 Number of primitive (aperiodic) word structures of length n using an infinite alphabet.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A179968 'AT(n,k)' triangle read by rows. AT(n,k) is the number of aperiodic k-compositions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions