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

1, 0, 2, 5, 11, 20, 41, 75, 147, 272, 533, 976, 1881, 3490, 6616, 12378, 23405, 43781, 82536, 154709, 291043, 546139, 1026685, 1927038, 3621004, 6798417, 12770935, 23980791, 45042957, 84584416, 158863805, 298336153, 560302805, 1052234995, 1976157456, 3711209272

Offset: 1

Author

Gus Wiseman, Oct 29 2019

Keywords

• nonn

Comments

A sequence is aperiodic if all of its cyclic rotations are different.

Examples

			The a(1) = 1 through a(6) = 20 compositions (empty column not shown):
  (1)  (12)  (13)   (14)    (15)
       (21)  (31)   (23)    (51)
             (112)  (32)    (114)
             (121)  (41)    (123)
             (211)  (113)   (132)
                    (131)   (141)
                    (311)   (213)
                    (1112)  (231)
                    (1121)  (312)
                    (1211)  (321)
                    (2111)  (411)
                            (1113)
                            (1131)
                            (1311)
                            (3111)
                            (11112)
                            (11121)
                            (11211)
                            (12111)
                            (21111)
		

Links

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

Crossrefs

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

The non-aperiodic, non-circular version is A167606.

The Lyndon word case is A328669.

Lyndon compositions are A059966, with relatively prime case A318731.

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

Programs

Mathematica

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

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, b(n, k, (i, j)->gcd(i, j)==1))); vector(n, n, sumdiv(n, d, moebius(d)*v[n/d]))} \\ Andrew Howroyd, Nov 01 2019

Extensions

Terms a(21) and beyond from Andrew Howroyd, Nov 01 2019