A238569 Number of compositions of n avoiding any 3-term arithmetic progression.

1, 1, 2, 3, 7, 11, 19, 28, 53, 83, 140, 201, 332, 486, 775, 1207, 1716, 2498, 3870, 5623, 8020, 11276, 17168, 23323, 34746, 46141, 64879, 90467, 127971, 176201, 242869, 333508, 456683, 606403, 844818, 1125922, 1496466, 2005446, 2737912, 3543506, 4824442

Offset

0,3

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..85

Index entries related to non-averaging sequences

Example

a(3) = 3: [1,2], [2,1], [3].
a(4) = 7: [1,1,2], [1,2,1], [1,3], [2,1,1], [2,2], [3,1], [4].
a(5) = 11: [1,1,3], [1,2,2], [1,3,1], [1,4], [2,1,2], [2,2,1], [2,3], [3,1,1], [3,2], [4,1], [5].
a(6) = 19: [1,1,2,2], [1,1,4], [1,2,1,2], [1,2,2,1], [1,3,2], [1,4,1], [1,5], [2,1,1,2], [2,1,2,1], [2,1,3], [2,2,1,1], [2,3,1], [2,4], [3,1,2], [3,3], [4,1,1], [4,2], [5,1], [6].

Maple

b:= proc(n, i, o) option remember; `if`(n=0, 1, add(
      `if`(j in o, 0, b(n-j, i union {j}, select(y->0<y
       and y<=n, o union map(x->2*j-x, i)))), j=1..n))
    end:
a:= n-> b(n, {}, {}):
seq(a(n), n=0..30);

Mathematica

b[n_, i_List, o_List] := b[n, i, o] = If[n == 0, 1, Sum[If[MemberQ[o, j], 0, b[n - j, i  ~Union~ {j}, Select[o ~Union~ (2j-i), 0<# && # <= n &]]], {j, 1, n}]]; a[n_] := b[n, {}, {}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 06 2015, translated from Maple *)

Crossrefs

Cf. A003407 (the same for permutations).

Cf. A178932 (the same for strict partitions).

Cf. A238423 (the same for consecutive 3-term arithmetic progressions).

Cf. A238571 (the same for partitions).

Cf. A238686.

Sequence in context: A105897 A129386 A278699 * A064270 A235633 A232232

Adjacent sequences: A238566 A238567 A238568 * A238570 A238571 A238572

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Feb 28 2014

Status

approved