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,5

Links

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

Formula

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

Example

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)

Mathematica

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

Prog

(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

Crossrefs

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

Sequence in context: A324894 A200498 A227361 * A333871 A364034 A373079

Adjacent sequences: A318723 A318724 A318725 * A318727 A318728 A318729

Keyword

nonn

Author

Gus Wiseman, Sep 02 2018

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

Status

approved