login
A328609
Number of compositions of n whose circularly adjacent parts are relatively prime.
10
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,4
COMMENTS
Circularity means the last part is followed by the first.
LINKS
FORMULA
a(n > 1) = A318748(n) - 1.
EXAMPLE
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)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], 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)={concat([1], sum(k=1, n, b(n, k, (i, j)->gcd(i, j)==1)))} \\ Andrew Howroyd, Nov 01 2019
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.
Sequence in context: A327546 A181844 A162506 * A227681 A055244 A089068
KEYWORD
nonn
AUTHOR
Gus Wiseman, Oct 26 2019
STATUS
approved