A328669 Number of Lyndon compositions of n where every pair of adjacent parts (including the last with the first) is relatively prime.

1, 0, 1, 2, 4, 6, 11, 18, 31, 52, 93, 157, 278, 479, 846, 1486, 2646, 4675, 8348, 14864, 26629, 47699, 85777, 154289, 278317, 502436, 908879, 1645712, 2984545, 5417742, 9847188, 17914493, 32625522, 59467892, 108493133, 198089609, 361965237, 661883230, 1211161990

Offset

1,4

Comments

A Lyndon composition of n is a finite sequence of positive integers summing to n that is lexicographically strictly less than all of its cyclic rotations.

Links

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

Formula

a(n > 1) = A318745(n) - 1.

Example

The a(1) = 1 through a(8) = 18 Lyndon compositions (empty column not shown):
  (1)  (12)  (13)   (14)    (15)     (16)      (17)
             (112)  (23)    (114)    (25)      (35)
                    (113)   (123)    (34)      (116)
                    (1112)  (132)    (115)     (125)
                            (1113)   (1114)    (134)
                            (11112)  (1123)    (143)
                                     (1132)    (152)
                                     (1213)    (1115)
                                     (11113)   (1214)
                                     (11212)   (1232)
                                     (111112)  (11114)
                                               (11123)
                                               (11132)
                                               (11213)
                                               (11312)
                                               (111113)
                                               (111212)
                                               (1111112)

Mathematica

aperQ[q_]:=Array[RotateRight[q, #]&, Length[q], 1, UnsameQ];
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], aperQ[#]&&neckQ[#]&&And@@CoprimeQ@@@Partition[#, 2, 1, 1]&]], {n, 10}]

Prog

(PARI)
b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q, ]}
seq(n)={my(v=sum(k=1, n, k*b(n, k, (i, j)->gcd(i, j)==1))); vector(n, n, sumdiv(n, d, moebius(d)*v[n/d])/n)} \\ Andrew Howroyd, Nov 01 2019

Crossrefs

The non-Lyndon version is A328609 or A318748 (with singletons).

The non-Lyndon non-circular version is A167606.

The version with singletons is A318745.

The necklace case is A328597 or A318728 (with singletons).

The aperiodic case is A328670.

Lyndon compositions are A059966, with relatively prime case A318731.

Cf. A000031, A000740, A008965, A328172, A328601, A328602.

Sequence in context: A138688 A131298 A168445 * A185192 A007053 A005684

Adjacent sequences: A328666 A328667 A328668 * A328670 A328671 A328672

Keyword

nonn

Author

Gus Wiseman, Oct 26 2019

Status

approved