login
Number of integer compositions of n where adjacent parts are indivisible (either way) and the last and first part are also indivisible (either way).
8

%I #12 Sep 08 2018 17:03:02

%S 1,1,1,1,3,1,5,3,5,13,9,23,15,37,45,63,115,131,207,265,415,603,823,

%T 1251,1673,2521,3519,5147,7409,10449,15225,21497,31285,44719,64171,

%U 92315,131619,190085,271871,391189,560979,804265,1155977,1656429,2381307,3414847

%N Number of integer compositions of n where adjacent parts are indivisible (either way) and the last and first part are also indivisible (either way).

%H Andrew Howroyd, <a href="/A318727/b318727.txt">Table of n, a(n) for n = 1..200</a>

%e The a(10) = 13 compositions:

%e (10)

%e (7,3) (3,7) (6,4) (4,6)

%e (5,3,2) (5,2,3) (3,5,2) (3,2,5) (2,5,3) (2,3,5)

%e (3,2,3,2) (2,3,2,3)

%t Table[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,({___,x_,y_,___}/;Divisible[x,y]||Divisible[y,x])|({y_,___,x_}/;Divisible[x,y]||Divisible[y,x])]&]//Length,{n,20}]

%o (PARI)

%o b(n,k,pred)={my(M=matrix(n,n)); for(n=1, n, M[n,n]=pred(k,n); for(j=1, n-1, M[n,j]=sum(i=1, n-j, if(pred(i,j), M[n-j,i], 0)))); sum(i=1, n, if(pred(i,k), M[n,i], 0))}

%o a(n)={1 + sum(k=1, n-1, b(n-k, k, (i,j)->i%j<>0&&j%i<>0))} \\ _Andrew Howroyd_, Sep 08 2018

%Y Cf. A000740, A008965, A167606, A285573, A296302, A303362, A304713, A316476, A318726.

%K nonn

%O 1,5

%A _Gus Wiseman_, Sep 02 2018

%E a(21)-a(28) from _Robert Price_, Sep 07 2018

%E Terms a(29) and beyond from _Andrew Howroyd_, Sep 08 2018