|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Circularity means the last part is followed by the first.
|
|
LINKS
|
|
|
FORMULA
|
|
|
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 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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|