A238432 Number of compositions of n avoiding equidistant 3-term arithmetic progressions.

1, 1, 2, 3, 7, 13, 22, 41, 74, 133, 233, 400, 714, 1209, 2091, 3591, 6089, 10316, 17477, 29413, 49515, 82474, 137659, 228461, 377936, 623710, 1025445, 1680418, 2746242, 4474654, 7270430, 11774128, 19020802, 30640812, 49222427, 78857338, 126033488, 200872080

Offset

0,3

Links

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..45

Example

The a(5) = 13 such compositions are:
01:  [ 1 1 2 1 ]
02:  [ 1 1 3 ]
03:  [ 1 2 1 1 ]
04:  [ 1 2 2 ]
05:  [ 1 3 1 ]
06:  [ 1 4 ]
07:  [ 2 1 2 ]
08:  [ 2 2 1 ]
09:  [ 2 3 ]
10:  [ 3 1 1 ]
11:  [ 3 2 ]
12:  [ 4 1 ]
13:  [ 5 ]
Note that the first and third composition contain the progression 1,1,1, but not in equidistant positions.

Maple

b:= proc(n, l) local j;
      for j from 2 to iquo(nops(l)+1, 2) do
      if l[1]-l[j]=l[j]-l[2*j-1] then return 0 fi od;
     `if`(n=0, 1, add(b(n-i, [i, l[]]), i=1..n))
    end:
a:= n-> b(n, []):
seq(a(n), n=0..20);

Mathematica

b[n_, l_] := b[n, l] = Module[{j}, For[j = 2, j <= Quotient[Length[l] + 1, 2], j++, If[l[[1]] - l[[j]] == l[[j]] - l[[2*j - 1]], Return[0]]]; If[n == 0, 1, Sum[b[n - i, Prepend[l, i]], {i, 1, n}]]];
a[n_] := b[n, {}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 21 2018, translated from Maple *)

Crossrefs

Cf. A238433 (same for partitions).

Cf. A238569 (compositions avoiding any 3-term arithmetic progression).

Cf. A238423 (compositions avoiding three consecutive parts in arithmetic progression).

Cf. A238686.

Sequence in context: A049887 A048216 A003509 * A238423 A133370 A237283

Adjacent sequences: A238429 A238430 A238431 * A238433 A238434 A238435

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Mar 01 2014

Status

approved