A328609 Number of compositions of n whose circularly adjacent parts are relatively prime.

1, 1, 1, 3, 6, 12, 23, 42, 81, 150, 284, 534, 1004, 1882, 3532, 6630, 12459, 23406, 43951, 82537, 154998, 291087, 546673, 1026686, 1928117, 3621016, 6800299, 12771085, 23984328, 45042958, 84591338, 158863806, 298348612, 560303341, 1052258401, 1976157509

Offset: 0

Author

Gus Wiseman, Oct 26 2019

Keywords

• nonn

Comments

Circularity means the last part is followed by the first.

Examples

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

Links

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

Crossrefs

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

The aperiodic version is A328670.

The Lyndon word version is A318745.

The version with singletons is A318748.

The non-circular version is A167606.

Relatively prime compositions are A000740.

Compositions with no part circularly followed by a divisor are A328598.

Cf. A008965, A178470, A318726, A325680, A328172, A328335, A328599, A328600.

Programs

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],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)={concat([1], sum(k=1, n, b(n, k, (i, j)->gcd(i, j)==1)))} \\ Andrew Howroyd, Nov 01 2019

Formula

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