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

Author

Joerg Arndt and Alois P. Heinz, Feb 28 2014

Keywords

• nonn

Examples

			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].
		

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 0..85
• Index entries related to non-averaging sequences

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.

Programs

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->02*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 *)