A318726 Number of integer compositions of n that have only one part or whose consecutive parts are indivisible and the last and first part are also indivisible.

1, 1, 1, 1, 3, 1, 5, 3, 8, 13, 12, 23, 27, 56, 64, 100, 150, 216, 325, 459, 700, 1007, 1493, 2186, 3203, 4735, 6929, 10243, 14952, 22024, 32366, 47558, 69906, 102634, 150984, 221713, 325919, 478842, 703648, 1034104, 1519432, 2233062, 3281004, 4821791, 7085359

Offset: 1

Author

Gus Wiseman, Sep 02 2018

Keywords

• nonn

Examples

			The a(10) = 13 compositions:
  (10)
  (7,3) (3,7) (6,4) (4,6)
  (5,3,2) (5,2,3) (3,5,2) (3,2,5) (2,5,3) (2,3,5)
  (3,2,3,2) (2,3,2,3)
The a(11) = 12 compositions:
  (11)
  (9,2) (2,9) (8,3) (3,8) (7,4) (4,7) (6,5) (5,6)
  (5,2,4) (4,5,2) (2,4,5)
		

Links

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

Crossrefs

Cf. A000740, A008965, A167606, A285573, A296302, A303362, A304713, A316476, A318727.

Programs

Mathematica

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

PARI

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))}
a(n)={1 + sum(k=1, n-1, b(n-k, k, (i,j)->i%j<>0))} \\ Andrew Howroyd, Sep 08 2018

Formula

a(n) = A328598(n) + 1. - Gus Wiseman, Nov 04 2019

Extensions

a(21)-a(28) from Robert Price, Sep 08 2018

Terms a(29) and beyond from Andrew Howroyd, Sep 08 2018

Name corrected by Gus Wiseman, Nov 04 2019