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

A102659 List of Lyndon words on {1,2} sorted first by length and then lexicographically.

Original entry on oeis.org

1, 2, 12, 112, 122, 1112, 1122, 1222, 11112, 11122, 11212, 11222, 12122, 12222, 111112, 111122, 111212, 111222, 112122, 112212, 112222, 121222, 122222, 1111112, 1111122, 1111212, 1111222, 1112112, 1112122, 1112212, 1112222, 1121122

Offset: 1

N. J. A. Sloane, Feb 03 2005

A Lyndon word is primitive (not a power of another word) and is earlier in lexicographic order than any of its cyclic shifts.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
F. Bassino, J. Clement and C. Nicaud, The standard factorization of Lyndon words: an average point of view, Discrete Math. 290 (2005), 1-25.
Émilie Charlier, Manon Philibert, Manon Stipulanti, Nyldon words, arXiv:1804.09735 [math.CO], 2018. See Table 1.
A. M. Uludag, A. Zeytin and M. Durmus, Binary Quadratic Forms as Dessins, 2012. - From _N. J. A. Sloane_, Dec 31 2012
Wikipedia, Lyndon word
Reinhard Zumkeller, Haskell programs for some sequences concerning Lyndon words
Index entries for sequences related to Lyndon words

Cf. A001037, A074650, A102660, A210584, A210585.
The "co" version is A329318.
A triangular version is A296657.
A sequence listing all Lyndon compositions is A294859.
Numbers whose binary expansion is Lyndon are A328596.
Length of the Lyndon factorization of the binary expansion is A211100.
Cf. A059966, A060223, A275692, A281013, A296373, A329131, A329313.

Haskell
```
cf. link.
```

lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
Join@@Table[FromDigits/@Select[Tuples[{1,2},n],lynQ],{n,5}] (* Gus Wiseman, Nov 14 2019 *)

is_A102659(n)={ vecsort(d=digits(n))!=d&&for(i=1,#d-1, n>[1,10^(#d-i)]*divrem(n,10^i)&&return); fordiv(#d,L,L<#d && d==concat(Col(vector(#d/L,i,1)~*vecextract(d,2^L-1))~)&&return); !setminus(Set(d),[1,2])} \\ The last check is the least expensive one, but not useful if we test only numbers with digits {1,2}.
for(n=1,6,p=vector(n,i,10^(n-i))~;forvec(d=vector(n,i,[1,2]),is_A102659(m=d*p)&&print1(m","))) \\ One could use is_A102660 instead of is_A102659 here. - M. F. Hasler, Mar 08 2014

A102659 = A102660 intersect A007931 = A213969 intersect A239016. - M. F. Hasler, Mar 10 2014

More terms from Franklin T. Adams-Watters, Dec 14 2006

Definition improved by Reinhard Zumkeller, Mar 23 2012

A185700 The number of periods in a reshuffling operation for compositions of n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 3, 5, 5, 3, 1, 0, 1, 3, 7, 8, 7, 3, 1, 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 0, 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1

Offset: 1

Paul Weisenhorn, Feb 10 2011

n has 2^(n-1) compositions. For each composition remove the largest part and redistribute it by adding 1 to subsequently smaller parts (creating 1's if needed) to get a new composition of n. (This is reversing the operation in A188160.) Repeat. Eventually this sequence of compositions will cycle. We are interested in the length of the period.
Let the indices k and j be uniquely associated with n using the triangular numbers T=A000217: T(k-1) < n <= T(k) and n = T(k-1) + j with 0 < j <= k.
a(n) with T(k-1) < n <= T(k) is the number of periods with length k for 1 < k.
If k is prime then all periods of the numbers T(k-1) < n < T(k) have length k.
If k is not prime, then the length of the periods is k or a divisor of k.
n = T(k-1) + j has binomial(k,j) partitions in its periods with 0 < j < k.
n = T(k-1) + j has c(n) = Sum_{d|gcd(k,j)} (phi(d)*binomial(k/d,j/d))/k periods of length k or a divisor of k as tabulated in A047996; phi is Euler's totient function. If k is prime then a(n)=c(n) gives the number of periods with length k. If k is not prime, subtract all periods of length < k from c(n).
Obtained from A092964 by adding an initial column of 1's and appending a 1 and 0 to each row. Obtained from A051168 by reading the array downwards along antidiagonals. - R. J. Mathar, Apr 14 2011
As a regular triangle, T(n,k) is the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and length k. Row sums are A059966. - Gus Wiseman, Dec 19 2017

			For k=5: T(4)=10 < n < T(5)=15 and all periods are of length 5:
a(11)=1 period: [(4+3+2+1+1), (4+3+2+2), (4+3+3+1), (4+4+2+1), (5+3+2+1)];
a(12)=2 periods: [(4+3+2+2+1), (4+3+3+2), (4+4+3+1), (5+4+2+1), (5+3+2+1+1)]; and [(4+4+2+2), (5+3+3+1), (4+4+2+1+1), (5+3+2+2), (4+3+3+1+1)];
a(13)=2 periods: [(4+4+2+2+1), (5+3+3+2), (4+4+3+1+1), (5+4+2+2), (5+3+3+1+1)]; and [(5+4+3+1), (5+4+2+1+1), (5+3+2+2+1), (4+3+3+2+1), (4+4+3+2)];
a(14)=1 period: [(5+4+3+2), (5+4+3+1+1), (5+4+2+2+1), (5+3+3+2+1), (4+4+3+2+1)].
For k=16; j=8; n=T(k-1)+j=128; 1<q|(16,8) --> {2,4,8} a(128) = c(128) - a(T(7)+4) - a(T(3)+2) - a(T(1)+1) =  810 - 8 - 1 - 1 = 800.
  (binomial(16,8)-8*a(T(7)+4)-4*a(T(3)+2)-2*a(T(1)+1))/16 = (12870-64-4-2)/16 = 800 = a(128).
Triangular view, with a(n) distributed in rows k=1,2,3.. according to T(k-1)< n <= T(k):
1;     k=1, n=1
1, 0;    k=2, n=2..3
1, 1,  0;    k=3, n=4..6
1, 1,  1,  0;    k=4, n=7..10
1, 2,  2,  1,   0;    k=5, n=11..15
1, 2,  3,  2,   1,   0;    k=6, n=16..21
1, 3,  5,  5,   3,   1,   0;
1, 3,  7,  8,   7,   3,   1,   0;
1, 4,  9, 14,  14,   9,   4,   1,   0;
1, 4, 12, 20,  25,  20,  12,   4,   1,  0;
1, 5, 15, 30,  42,  42,  30,  15,   5,  1,  0;
1, 5, 18, 40,  66,  75,  66,  40,  18,  5,  1, 0;
1, 6, 22, 55,  99, 132, 132,  99,  55, 22,  6, 1, 0;
1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1, 0;

R. Baumann, Computer-Knobelei, LOGIN (1987), 483-486 (in German).

Ethan Akin, Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985) 237-250
J. Brandt, Cycles of partitions, Proc. Am. Math. Soc. 85 (3) (1982) 483-486

Cf. A000740, A001037, A008965, A051168, A059966, A060223, A245558, A294859, A296302, A296373, A092964, A245559, A245558.

A000217 := proc(n) n*(n+1)/2 ; end proc:
A185700 := proc(n) local k,j,a,q; k := ceil( (-1+sqrt(1+8*n))/2 ) ; j := n-A000217(k-1) ; if n = 1 then return 1; elif j = k then return 0 ; end if; a := binomial(k,j) ; if not isprime(k) then for q in numtheory[divisors]( igcd(k,j)) minus {1} do a := a- procname(j/q+A000217(k/q-1))*k/q ; end do: end if; a/k ; end proc:
seq(A185700(n),n=1..80) ; # R. J. Mathar, Jun 11 2011

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length@Select[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]===k&],LyndonQ],{n,10},{k,n}] (* Gus Wiseman, Dec 19 2017 *)

a(T(k))=0 with k > 1. a(1)=1.
If k is a prime number and n = T(k-1) + j with 0 < j < k, then a(n) = binomial(k,j)/k.
If k is not prime, subtract the sum of partitions in all periods of n with length < k from the term binomial(k,j). The difference divided by k gives the number of periods for n=T(k-1)+j: a(n)=( binomial(k,j) -sum {a(T(k/q-1)+j/q) *k/q })/k summed over all 1 < q|gcd(k,j).
If k is not prime, subtract the sum of all periods of n with length < k from the term c(n) = sum{ phi(d)*binomial(k/d,j/d) }/k summed over d|gcd(k,j), namely
  a(n) = c(n)-sum{a(T(k/q-1)+j))} summed over all 1 < q|gcd(k,j).

I have added a comment and deleted a Jun 11 2011 question from R. J. Mathar. - Paul Weisenhorn, Jan 08 2017

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

A281013 Tetrangle T(n,k,i) = i-th part of k-th prime composition of n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Jan 12 2017

The *-product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling them together. Every finite positive integer sequence has a unique *-factorization using prime compositions P = {(1), (2), (21), (3), (211), ...}. See A060223 and A228369 for details.

These are co-Lyndon compositions, ordered first by sum and then lexicographically. - Gus Wiseman, Nov 15 2019

			The prime factorization of (1, 1, 4, 2, 3, 1, 5, 5) is: (11423155) = (1)*(1)*(5)*(5)*(4231). The prime factorizations of the initial terms of A000002 are:
             (1) = (1)
            (12) = (1)*(2)
           (122) = (1)*(2)*(2)
          (1221) = (1)*(221)
         (12211) = (1)*(2211)
        (122112) = (1)*(2)*(2211)
       (1221121) = (1)*(221121)
      (12211212) = (1)*(2)*(221121)
     (122112122) = (1)*(2)*(2)*(221121)
    (1221121221) = (1)*(221)*(221121)
   (12211212212) = (1)*(2)*(221)*(221121)
  (122112122122) = (1)*(2)*(2)*(221)*(221121).
Read as a sequence:
(1), (2), (21), (3), (211), (31), (4), (2111), (221), (311), (32), (41), (5).
Read as a triangle:
(1)
(2)
(21), (3)
(211), (31), (4)
(2111), (221), (311), (32), (41), (5).
Read as a sequence of triangles:
1    2    2 1    2 1 1    2 1 1 1    2 1 1 1 1    2 1 1 1 1 1
          3      3 1      2 2 1      2 2 1 1      2 1 2 1 1
                 4        3 1 1      3 1 1 1      2 2 1 1 1
                          3 2        3 1 2        2 2 2 1
                          4 1        3 2 1        3 1 1 1 1
                          5          4 1 1        3 1 1 2
                                     4 2          3 1 2 1
                                     5 1          3 2 1 1
                                     6            3 2 2
                                                  3 3 1
                                                  4 1 1 1
                                                  4 1 2
                                                  4 2 1
                                                  4 3
                                                  5 1 1
                                                  5 2
                                                  6 1
                                                  7.

Cf. A000740, A215474, A228369, A277427.
The binary version is A329318.
The binary non-"co" version is A102659.
A sequence listing all Lyndon compositions is A294859.
Numbers whose binary expansion is co-Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Binary Lyndon words are A001037.
Lyndon compositions are A059966.
Normal Lyndon words are A060223.
Cf. A211097, A211100, A296372, A296373, A298941, A329131, A329312, A329313, A329314, A329324, A329326.

colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
Table[Sort[Select[Join@@Permutations/@IntegerPartitions[n],colynQ],lexsort],{n,5}] (* Gus Wiseman, Nov 15 2019 *)

Row lengths are A059966(n) = number of prime compositions of n.

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).

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).

A299023 Number of compositions of n whose standard factorization into Lyndon words has all strict compositions as factors.

Original entry on oeis.org

1, 2, 4, 7, 12, 23, 38, 66, 112, 193, 319, 539, 887, 1466, 2415, 3951, 6417, 10428, 16817, 27072, 43505, 69560, 110916, 176469, 279893, 442742, 698919, 1100898, 1729530, 2712134, 4244263, 6628174, 10332499, 16077835, 24972415, 38729239, 59958797, 92685287

Offset: 1

Gus Wiseman, Jan 31 2018

nonn

			The a(5) = 12 compositions:
      (5) = (5)
     (41) = (4)*(1)
     (14) = (14)
     (32) = (3)*(2)
     (23) = (23)
    (311) = (3)*(1)*(1)
    (131) = (13)*(1)
    (221) = (2)*(2)*(1)
    (212) = (2)*(12)
   (2111) = (2)*(1)*(1)*(1)
   (1211) = (12)*(1)*(1)
  (11111) = (1)*(1)*(1)*(1)*(1)
Not included:
    (113) = (113)
    (122) = (122)
   (1121) = (112)*(1)
   (1112) = (1112)

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

Cf. A001045, A032020, A032153, A034691, A049311, A059966, A089259, A098407, A116540, A185700, A270995, A296373, A299024, A299026, A299027.

nn=50;
ser=Product[1/(1-x^n)^Total[(Length[#]-1)!&/@Select[IntegerPartitions[n],UnsameQ@@#&]],{n,nn}];
Table[SeriesCoefficient[ser,{x,0,n}],{n,nn}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(N)={EulerT(Vec(sum(n=1, N-1, (n-1)!*x^(n*(n+1)/2)/prod(k=1, n, 1-x^k + O(x^N)))))} \\ Andrew Howroyd, Dec 01 2018

Euler transform of A032153.

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

A102659 List of Lyndon words on {1,2} sorted first by length and then lexicographically.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A185700 The number of periods in a reshuffling operation for compositions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

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

A281013 Tetrangle T(n,k,i) = i-th part of k-th prime composition of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author