cp's OEIS Frontend

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

%I A328609 #10 Nov 02 2019 03:20:34
%S A328609 1,1,1,3,6,12,23,42,81,150,284,534,1004,1882,3532,6630,12459,23406,
%T A328609 43951,82537,154998,291087,546673,1026686,1928117,3621016,6800299,
%U A328609 12771085,23984328,45042958,84591338,158863806,298348612,560303341,1052258401,1976157509
%N A328609 Number of compositions of n whose circularly adjacent parts are relatively prime.
%C A328609 Circularity means the last part is followed by the first.
%H A328609 Andrew Howroyd, <a href="/A328609/b328609.txt">Table of n, a(n) for n = 0..200</a>
%F A328609 a(n > 1) = A318748(n) - 1.
%e A328609 The a(1) = 1 through a(6) = 23 compositions:
%e A328609   (1)  (11)  (12)   (13)    (14)     (15)
%e A328609              (21)   (31)    (23)     (51)
%e A328609              (111)  (112)   (32)     (114)
%e A328609                     (121)   (41)     (123)
%e A328609                     (211)   (113)    (132)
%e A328609                     (1111)  (131)    (141)
%e A328609                             (311)    (213)
%e A328609                             (1112)   (231)
%e A328609                             (1121)   (312)
%e A328609                             (1211)   (321)
%e A328609                             (2111)   (411)
%e A328609                             (11111)  (1113)
%e A328609                                      (1131)
%e A328609                                      (1212)
%e A328609                                      (1311)
%e A328609                                      (2121)
%e A328609                                      (3111)
%e A328609                                      (11112)
%e A328609                                      (11121)
%e A328609                                      (11211)
%e A328609                                      (12111)
%e A328609                                      (21111)
%e A328609                                      (111111)
%t A328609 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],And@@CoprimeQ@@@Partition[#,2,1,1]&]],{n,10}]
%o A328609 (PARI)
%o A328609 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, ]}
%o A328609 seq(n)={concat([1], sum(k=1, n, b(n, k, (i, j)->gcd(i, j)==1)))} \\ _Andrew Howroyd_, Nov 01 2019
%Y A328609 The necklace version is A328597 or A318728 (with singletons).
%Y A328609 The aperiodic version is A328670.
%Y A328609 The Lyndon word version is A318745.
%Y A328609 The version with singletons is A318748.
%Y A328609 The non-circular version is A167606.
%Y A328609 Relatively prime compositions are A000740.
%Y A328609 Compositions with no part circularly followed by a divisor are A328598.
%Y A328609 Cf. A008965, A178470, A318726, A325680, A328172, A328335, A328599, A328600.
%K A328609 nonn
%O A328609 0,4
%A A328609 _Gus Wiseman_, Oct 26 2019