A185700 -id:A185700 - cp's OEIS frontend

A059966 a(n) = (1/n) * Sum_{ d divides n } mu(n/d) * (2^d - 1).

1, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858, 190557, 364722, 698870, 1342176, 2580795, 4971008, 9586395, 18512790, 35790267, 69273666, 134215680, 260300986, 505286415, 981706806

Offset: 1

Roland Bacher, Mar 05 2001

Dimensions of the homogeneous parts of the free Lie algebra with one generator in 1,2,3, etc. (Lie analog of the partition numbers).
This sequence is the Lie analog of the partition sequence (which gives the dimensions of the homogeneous polynomials with one generator in each degree) or similarly, of the partitions into distinct (or odd numbers) (which gives the dimensions of the homogeneous parts of the exterior algebra with one generator in each dimension).
The number of cycles of length n of rectangle shapes in the process of repeatedly cutting a square off the end of the rectangle. For example, the one cycle of length 1 is the golden rectangle. - David Pasino (davepasino(AT)yahoo.com), Jan 29 2009
In music, the number of distinct rhythms, at a given tempo, produced by a continuous repetition of measures with identical patterns of 1's and 0's (where 0 means no beat, and 1 means one beat), where each measure allows for n possible beats of uniform character, and when counted under these two conditions: (i) the starting and ending times for the measure are unknown or irrelevant and (ii) identical rhythms that can be produced by using a measure with fewer than n possible beats are excluded from the count. - Richard R. Forberg, Apr 22 2013
Richard R. Forberg's comment does not hold for n=1 because a(1)=1 but there are the two possible rhythms: "0" and "1". - Herbert Kociemba, Oct 24 2016
The comment does hold for n=1 as the rhythm "0" can be produced by using a measure of 0 beats and so is properly excluded from a(1)=1 by condition (ii) of the comment. - Travis Scott, May 28 2022
a(n) is also the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n. - Gus Wiseman, Dec 19 2017
Mobius transform of A008965. - Jianing Song, Nov 13 2021
a(n) is the number of cycles of length n for the map x->1 - abs(2*x-1) applied on rationals 0Michel Marcus, Jul 16 2025

			a(4)=3: the 3 elements [a,c], [a[a,b]] and d form a basis of all homogeneous elements of degree 4 in the free Lie algebra with generators a of degree 1, b of degree 2, c of degree 3 and d of degree 4.
From _Gus Wiseman_, Dec 19 2017: (Start)
The sequence of Lyndon compositions organized by sum begins:
  (1),
  (2),
  (3),(12),
  (4),(13),(112),
  (5),(14),(23),(113),(122),(1112),
  (6),(15),(24),(114),(132),(123),(1113),(1122),(11112),
  (7),(16),(25),(115),(34),(142),(124),(1114),(133),(223),(1213),(1132),(1123),(11113),(1222),(11212),(11122),(111112). (End)

C. Reutenauer, Free Lie algebras, Clarendon press, Oxford (1993).

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See p. 17.
S. V. Duzhin and D. V. Pasechnik, Groups acting on necklaces and sandpile groups, Journal of Mathematical Sciences, August 2014, Volume 200, Issue 6, pp 690-697. See page 85. - N. J. A. Sloane, Jun 30 2014
Seok-Jin Kang and Myung-Hwan Kim, Free Lie Algebras, Generalized Witt Formula and the Denominator Identity, Journal of Algebra 183, 560-594 (1996).
Michael J. Mossinghoff and Timothy S. Trudgian, A tale of two omegas, arXiv:1906.02847 [math.NT], 2019.
G. Niklasch, Some number theoretical constants: 1000-digit values [Cached copy]
Jakob Oesinghaus, Quasi-symmetric functions and the Chow ring of the stack of expanded pairs, arXiv:1806.10700 [math.AG], 2018.
Robert Schneider, Andrew V. Sills, and Hunter Waldron, On the q-factorization of power series, arXiv:2501.18744 [math.CO], 2025. See p. 6.

Apart from initial terms, same as A001037.

Cf. A000225, A000740, A008683, A008965, A011782, A060223, A185700, A228369, A269134 A281013, A296302, A296373.

a059966 n = sum (map (\x -> a008683 (n `div` x) * a000225 x)
                     [d | d <- [1..n], mod n d == 0]) `div` n
-- Reinhard Zumkeller, Nov 18 2011

Table[1/n Apply[Plus, Map[(MoebiusMu[n/# ](2^# - 1)) &, Divisors[n]]], {n, 20}]
(* Second program: *)
Table[(1/n) DivisorSum[n, MoebiusMu[n/#] (2^# - 1) &], {n, 35}] (* Michael De Vlieger, Jul 22 2019 *)

from sympy import mobius, divisors
def A059966(n): return sum(mobius(n//d)*(2**d-1) for d in divisors(n,generator=True))//n # Chai Wah Wu, Feb 03 2022

G.f.: Product_{n>0} (1-q^n)^a(n) = 1-q-q^2-q^3-q^4-... = 2-1/(1-q).
Inverse Euler transform of A011782. - Alois P. Heinz, Jun 23 2018
G.f.: Sum_{k>=1} mu(k)*log((1 - x^k)/(1 - 2*x^k))/k. - Ilya Gutkovskiy, May 19 2019
a(n) ~ 2^n / n. - Vaclav Kotesovec, Aug 10 2019
Dirichlet g.f.: f(s+1)/zeta(s+1) - 1, where f(s) = Sum_{n>=1} 2^n/n^s. - Jianing Song, Nov 13 2021

Explicit formula from Paul D. Hanna, Apr 15 2002

Description corrected by Axel Kleinschmidt, Sep 15 2002

A296372 Triangle read by rows: T(n,k) is the number of normal sequences of length n whose standard factorization into Lyndon words (aperiodic necklaces) has k factors.

Original entry on oeis.org

1, 1, 2, 4, 5, 4, 18, 31, 18, 8, 108, 208, 153, 56, 16, 778, 1700, 1397, 616, 160, 32, 6756, 15980, 14668, 7197, 2196, 432, 64, 68220, 172326, 171976, 93293, 31564, 7208, 1120, 128

Offset: 1

Gus Wiseman, Dec 11 2017

A finite sequence is normal if its union is an initial interval of positive integers.

			The T(3,2) = 5 normal sequences are {2,1,2}, {1,2,1}, {2,1,3}, {2,3,1}, {3,1,2}.
Triangle begins:
     1;
     1,     2;
     4,     5,     4;
    18,    31,    18,     8;
   108,   208,   153,    56,    16;
   778,  1700,  1397,   616,   160,    32;
  6756, 15980, 14668,  7197,  2196,   432,    64;

Andrew Howroyd, Rows n = 1..50 of triangle, flattened
Wikipedia, Lyndon word: Standard factorization

Row sums are A000670.
First column is A060223.
Cf. A000740, A001045, A008965, A019536, A059966, A074650, A185700, A228369, A232472, A277427, A281013, A296373.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
aperQ[q_]:=UnsameQ@@Table[RotateRight[q,k],{k,Length[q]}];
qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],neckQ[Take[q,#]]&&aperQ[Take[q,#]]&]];
allnorm[n_]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Length[Select[Join@@Permutations/@allnorm[n],Length[qit[#]]===k&]],{n,5},{k,n}]

\\ here U(n,k) is A074650(n,k).
EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
U(n,k)={sumdiv(n, d, moebius(n/d) * k^d)/n}
A(n)={[Vecrev(p/y) | p<-sum(k=1, n, EulerMT(vector(n, n, y*U(n,k)))*sum(j=k, n, (-1)^(k-j)*binomial(j,k)))]}
{ my(T=A(10)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 08 2018

Example and program corrected by Gus Wiseman, Dec 08 2018

A254040 Number T(n,k) of primitive (= aperiodic) n-bead necklaces with colored beads of exactly k different colors; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 9, 6, 0, 0, 6, 30, 48, 24, 0, 0, 9, 89, 260, 300, 120, 0, 0, 18, 258, 1200, 2400, 2160, 720, 0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040, 0, 0, 56, 2016, 20720, 92680, 211680, 258720, 161280, 40320

Offset: 0

Alois P. Heinz, Jan 23 2015

Turning over the necklaces is not allowed.

With other words: T(n,k) is the number of normal Lyndon words of length n and maximum k, where a finite sequence is normal if it spans an initial interval of positive integers. - Gus Wiseman, Dec 22 2017

			Triangle T(n,k) begins:
  1;
  0, 1;
  0, 0,  1;
  0, 0,  2,   2;
  0, 0,  3,   9,    6;
  0, 0,  6,  30,   48,    24;
  0, 0,  9,  89,  260,   300,   120;
  0, 0, 18, 258, 1200,  2400,  2160,   720;
  0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040;
  ...
The T(4,3) = 9 normal Lyndon words of length 4 with maximum 3 are: 1233, 1323, 1332, 1223, 1232, 1322, 1123, 1132, 1213. - _Gus Wiseman_, Dec 22 2017

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000007, A063524, A001037 (for n>1), A056288, A056289, A056290, A056291, A254079, A254080, A254081, A254082.
Row sums give A060223.
Main diagonal and lower diagonal give: A000142, A074143.
T(2n,n) gives A254083.
Cf. A074650, A087854.
Cf. A000670, A000740, A008683, A019536, A059966, A185700, A296372, A296373, A296657.

with(numtheory):
b:= proc(n, k) option remember; `if`(n=0, 1,
      add(mobius(n/d)*k^d, d=divisors(n))/n)
    end:
T:= (n, k)-> add(b(n, k-j)*binomial(k,j)*(-1)^j, j=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[MoebiusMu[n/d]*k^d, {d, Divisors[n]}]/n]; T[n_, k_] := Sum[b[n, k-j]*Binomial[k, j]*(-1)^j, {j, 0, k}]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)
LyndonQ[q_]:=q==={}||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
allnorm[n_,k_]:=If[k===0,If[n===0,{{}}, {}],Join@@Permutations/@Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Select[Subsets[Range[n-1]+1],Length[#]===k-1&]];
Table[Length[Select[allnorm[n,k],LyndonQ]],{n,0,7},{k,0,n}] (* Gus Wiseman, Dec 22 2017 *)

T(n,k) = Sum_{j=0..k} (-1)^j * C(k,j) * A074650(n,k-j).

T(n,k) = Sum_{d|n} mu(d) * A087854(n/d, k) for n >= 1 and 1 <= k <= n. - Petros Hadjicostas, Aug 20 2019

A226062 a(n) = Bulgarian solitaire operation applied to the partition encoded in the runlengths of binary expansion of n.

Original entry on oeis.org

0, 1, 3, 2, 13, 7, 6, 6, 11, 29, 15, 58, 9, 14, 4, 14, 19, 27, 61, 54, 245, 31, 122, 52, 27, 25, 30, 50, 25, 12, 12, 30, 35, 23, 59, 46, 237, 125, 118, 44, 235, 501, 63, 1002, 233, 250, 116, 40, 51, 19, 57, 38, 229, 62, 114, 36, 59, 17, 28, 34, 57, 8, 28, 62

Offset: 0

Antti Karttunen, Jul 06 2013

For this sequence the partitions are encoded in the binary expansion of n in the same way as in A129594.
In "Bulgarian solitaire" a deck of cards or another finite set of objects is divided into one or more piles, and the "Bulgarian operation" is performed by taking one card from each pile, and making a new pile of them. The question originally posed was: on what condition the resulting partitions will eventually reach a fixed point, that is, a collection of piles that will be unchanged by the operation. See Martin Gardner reference and the Wikipedia-page.
A037481 gives the fixed points of this sequence, which are numbers that encode triangular partitions: 1 + 2 + 3 + ... + n.
A227752(n) tells how many times n occurs in this sequence, and A227753 gives the terms that do not occur here.
Of further interest: among each A000041(n) numbers j_i: j1, j2, ..., jk for which A227183(j_i)=n, how many cycles occur and what is the size of the largest one? (Both are 1 when n is in A000217, as then the fixed points are the only cycles.) Cf. A185700, A188160.
Also, A123975 answers how many Garden of Eden partitions there are for the deck of size n in Bulgarian Solitaire, corresponding to values that do not occur as the terms of this sequence.

			5 has binary expansion "101", whose runlengths are [1,1,1], which are converted to nonordered partition {1+1+1}.
6 has binary expansion "110", whose runlengths are [1,2] (we scan the runs of bits from right to left), which are converted to nonordered partition {1+2}.
7 has binary expansion "111", whose list of runlengths is [3], which is converted to partition {3}.
In "Bulgarian Operation" we subtract one from each part (with 1-parts vanishing), and then add a new part of the same size as there originally were parts, so that the total sum stays same.
Thus starting from a partition encoded by 5, {1,1,1} the operation works as 1-1, 1-1, 1-1 (all three 1's vanish) but appends part 3 as there originally were three parts, thus we get a new partition {3}. Thus a(5)=7.
From the partition {3} -> 3-1 and 1, which gives a new partition {1,2}, so a(7)=6.
For partition {1+2} -> 1-1 and 2-1, thus the first part vanishes, and the second is now 1, to which we add the new part 2, as there were two parts originally, thus {1+2} stays as {1+2}, and we have reached a fixed point, a(6)=6.

Martin Gardner, Colossal Book of Mathematics, Chapter 34, Bulgarian Solitaire and Other Seemingly Endless Tasks, pp. 455-467, W. W. Norton & Company, 2001.

Antti Karttunen, Table of n, a(n) for n = 0..8191
Ethan Akin and Morton Davis, "Bulgarian solitaire", American Mathematical Monthly 92 (4): 237-250. (1985).
Antti Karttunen, Python-program for computing this and related sequences.
Wikipedia, Bulgarian solitaire

Cf. A227147, A227183, A227452.
Cf. A037481 (gives the fixed points).
Cf. A227752 (how many times n occurs here).
Cf. A227753 (numbers that do not occur here).
Cf. A129594 (conjugates the partitions encoded with the same system).
Cf. also A123975, A074909, A185700, A071762, A075157, A075158, A243353, A243354, A242424, A243051.

Other identities:
A227183(a(n)) = A227183(n). [This operation doesn't change the total sum of the partition.]
a(n) = A243354(A242424(A243353(n))).
a(n) = A075158(A243051(1+A075157(n))-1).

A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 5, 3, 1, 1, 9, 12, 6, 3, 1, 1, 18, 21, 14, 6, 3, 1, 1, 30, 45, 27, 15, 6, 3, 1, 1, 56, 84, 61, 29, 15, 6, 3, 1, 1, 99, 170, 120, 67, 30, 15, 6, 3, 1, 1, 186, 323, 254, 136, 69, 30, 15, 6, 3, 1, 1, 335, 640, 510, 295, 142, 70, 30, 15, 6, 3, 1, 1

Offset: 1

Gus Wiseman, Dec 11 2017

			Triangle begins:
    1;
    1,   1;
    2,   1,   1;
    3,   3,   1,   1;
    6,   5,   3,   1,   1;
    9,  12,   6,   3,   1,   1;
   18,  21,  14,   6,   3,   1,   1;
   30,  45,  27,  15,   6,   3,   1,   1;
   56,  84,  61,  29,  15,   6,   3,   1,   1;
   99, 170, 120,  67,  30,  15,   6,   3,   1,   1;
  186, 323, 254, 136,  69,  30,  15,   6,   3,   1,   1;
  335, 640, 510, 295, 142,  70,  30,  15,   6,   3,   1,   1;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Wikipedia, Lyndon word: Standard factorization

Cf. A000740, A001045, A008965, A019536, A059966, A060223, A185700, A228369, A232472, A277427, A281013, A296302, A296372.

neckQ[q_]:=Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
aperQ[q_]:=UnsameQ@@Table[RotateRight[q,k],{k,Length[q]}];
qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],neckQ[Take[q,#]]&&aperQ[Take[q,#]]&]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[qit[#]]===k&]],{n,12},{k,n}]

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
A(n)=[Vecrev(p/y) | p<-EulerMT(y*vector(n, n, sumdiv(n, d, moebius(n/d) * (2^d-1))/n))]
{ my(T=A(12)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 01 2018

First column is A059966.

A294859 Triangle whose n-th row is the concatenated sequence of all Lyndon compositions of n in lexicographic order.

Original entry on oeis.org

1, 2, 1, 2, 3, 1, 1, 2, 1, 3, 4, 1, 1, 1, 2, 1, 1, 3, 1, 2, 2, 1, 4, 2, 3, 5, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 4, 1, 2, 3, 1, 3, 2, 1, 5, 2, 4, 6, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 1, 4, 1, 1, 2, 1, 2, 1, 1, 2, 3, 1, 1, 3, 2, 1

Offset: 1

Gus Wiseman, Dec 18 2017

			Triangle of Lyndon compositions begins:
(1),
(2),
(12),(3),
(112),(13),(4),
(1112),(113),(122),(14),(23),(5),
(11112),(1113),(1122),(114),(123),(132),(15),(24),(6),
(111112),(11113),(11122),(1114),(11212),(1123),(1132),(115),(1213),(1222),(124),(133),(142),(16),(223),(25),(34),(7).

Cf. A000740, A001037, A001045, A008965, A059966, A060223, A066099, A101211, A102659, A124734, A185700, A228369, A281013, A296302, A296373, A296656.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Sort[Select[Join@@Permutations/@IntegerPartitions[n],LyndonQ],OrderedQ[PadRight[{#1,#2}]]&],{n,7}]

Row n is a concatenation of A059966(n) Lyndon words with total length A000740(n).

A323866 Number of aperiodic toroidal necklaces of positive integers summing to n.

Original entry on oeis.org

1, 1, 1, 3, 5, 12, 18, 42, 72, 145, 262, 522, 960, 1879, 3531, 6831, 13013, 25148, 48177, 93186, 179507, 347509, 671955, 1303257, 2527162, 4910681, 9545176, 18579471, 36183505, 70540861, 137603801, 268655547, 524842088, 1026067205, 2007118657, 3928564113

Offset: 0

Gus Wiseman, Feb 04 2019

nonn

The 1-dimensional (Lyndon word) case is A059966.

We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

			Inequivalent representatives of the a(6) = 18 toroidal necklaces:
  [6] [1 5] [2 4] [1 1 4] [1 2 3] [1 3 2] [1 1 1 3] [1 1 2 2] [1 1 1 1 2]
.
  [1] [2] [1 1]
  [5] [4] [1 3]
.
  [1] [1] [1]
  [1] [2] [3]
  [4] [3] [2]
.
  [1] [1]
  [1] [1]
  [1] [2]
  [3] [2]
.
  [1]
  [1]
  [1]
  [1]
  [2]

Andrew Howroyd, Table of n, a(n) for n = 0..200
S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.

Cf. A000031, A000670, A000740, A001037, A008965, A059966, A060223, A185700.

Cf. A323858, A323861, A323865, A323871.

List([0..30], A323866); # See A323861 for code; Andrew Howroyd, Aug 21 2019

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
ptnmats[n_]:=Union@@Permutations/@Select[Union@@(Tuples[Permutations/@#]&/@Map[primeMS,facs[n],{2}]),SameQ@@Length/@#&];
apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
Table[If[n==0,1,Length[Union@@Table[Select[ptnmats[k],And[apermatQ[#],neckmatQ[#]]&],{k,Times@@Prime/@#&/@IntegerPartitions[n]}]]],{n,0,10}]

Terms a(16) and beyond from Andrew Howroyd, Aug 21 2019

A296975 Number of aperiodic normal sequences of length n.

Original entry on oeis.org

1, 2, 12, 72, 540, 4668, 47292, 545760, 7087248, 102247020, 1622632572, 28091562840, 526858348380, 10641342923148, 230283190977300, 5315654681435520, 130370767029135900, 3385534663249753392, 92801587319328411132, 2677687796244281955480, 81124824998504073834516

Offset: 1

Gus Wiseman, Dec 22 2017

nonn

A finite sequence is normal if it spans an initial interval of positive integers. It is aperiodic if every cyclic rotation is different.

			The a(3) = 12 aperiodic normal sequences are 112, 121, 122, 123, 132, 211, 212, 213, 221, 231, 312, 321.
The 15 non-aperiodic normal sequences of length 6 are: 111111, 112112, 121121, 121212, 122122, 123123, 132132, 211211, 212121, 212212, 213213, 221221, 231231, 312312, 321321.

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

Cf. A000670, A000740, A001037, A019536, A027375, A060223, A095684, A185700, A296976, A296977, A296978.

Table[DivisorSum[n,MoebiusMu[n/#]*Sum[k!*StirlingS2[#,k],{k,#}]&],{n,25}]

\\ here b(n) is A000670.
b(n)={polcoef(serlaplace(1/(2-exp(x+O(x*x^n)))),n)}
a(n)={sumdiv(n, d, moebius(d)*b(n/d))} \\ Andrew Howroyd, Aug 29 2018

a(n) = n * A060223(n) = Sum_{d|n} mu(d) * A000670(n/d).

A296656 Triangle whose n-th row is the concatenated sequence of all Lyndon compositions of n in reverse-lexicographic order.

Original entry on oeis.org

1, 2, 3, 1, 2, 4, 1, 3, 1, 1, 2, 5, 2, 3, 1, 4, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 6, 2, 4, 1, 5, 1, 3, 2, 1, 2, 3, 1, 1, 4, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 1, 1, 2, 7, 3, 4, 2, 5, 2, 2, 3, 1, 6, 1, 4, 2, 1, 3, 3, 1, 2, 4, 1, 2, 2, 2, 1, 2, 1, 3, 1, 1, 5, 1, 1, 3, 2

Offset: 1

Gus Wiseman, Dec 18 2017

			Triangle of Lyndon compositions begins:
(1),
(2),
(3),(12),
(4),(13),(112),
(5),(23),(14),(122),(113),(1112),
(6),(24),(15),(132),(123),(114),(1122),(1113),(11112),
(7),(34),(25),(223),(16),(142),(133),(124),(1222),(1213),(115),(1132),(1123),(11212),(1114),(11122),(11113),(111112).

Cf. A000740, A001037, A001045, A008965, A059966, A060223, A066099, A101211, A102659, A124734, A185700, A228369, A281013, A294859, A296302, A296373.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Sort[Select[Join@@Permutations/@IntegerPartitions[n],LyndonQ],OrderedQ[PadRight[{#2,#1}]]&],{n,7}]

Row n is a concatenation of A059966(n) Lyndon words with total length A000740(n).

A298971 Number of compositions of n that are proper powers of Lyndon words.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 16, 1, 20, 9, 35, 1, 69, 1, 110, 21, 188, 1, 381, 7, 632, 59, 1184, 1, 2300, 1, 4115, 189, 7712, 25, 14939, 1, 27596, 633, 52517, 1, 101050, 1, 190748, 2247, 364724, 1, 703331, 19, 1342283, 7713, 2581430, 1, 4985609, 193

Offset: 1

Gus Wiseman, Jan 30 2018

nonn

a(n) is the number of compositions of n that are not Lyndon words but are of the form p * p * ... * p where * is concatenation and p is a Lyndon word.

			The a(12) = 16 compositions: 111111111111, 1111211112, 11131113, 112112112, 11221122, 114114, 12121212, 123123, 131313, 132132, 1515, 222222, 2424, 3333, 444, 66.

Cf. A000005, A000031, A000740, A000961, A001045, A008965, A019536, A034691, A051953, A052823, A059966, A060223, A178472, A185700, A296302, A296373.

Table[Sum[DivisorSum[d,MoebiusMu[d/#]*(2^#-1)&]/d,{d,Most@Divisors[n]}],{n,100}]

a(n) = sumdiv(n, d, (2^d-1)*(eulerphi(n/d)-moebius(n/d))/n); \\ Michel Marcus, Jan 31 2018

a(n) = Sum_{d|n} (2^d-1)*(phi(n/d)-mu(n/d))/n.

a(n) = A008965(n) - A059966(n).

cp's OEIS Frontend

A059966 a(n) = (1/n) * Sum_{ d divides n } mu(n/d) * (2^d - 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

Extensions

A296372 Triangle read by rows: T(n,k) is the number of normal sequences of length n whose standard factorization into Lyndon words (aperiodic necklaces) has k factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A254040 Number T(n,k) of primitive (= aperiodic) n-bead necklaces with colored beads of exactly k different colors; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A226062 a(n) = Bulgarian solitaire operation applied to the partition encoded in the runlengths of binary expansion of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A294859 Triangle whose n-th row is the concatenated sequence of all Lyndon compositions of n in lexicographic order.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A323866 Number of aperiodic toroidal necklaces of positive integers summing to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP