cp's OEIS Frontend

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

%I A238569 #24 Feb 16 2022 07:07:00
%S A238569 1,1,2,3,7,11,19,28,53,83,140,201,332,486,775,1207,1716,2498,3870,
%T A238569 5623,8020,11276,17168,23323,34746,46141,64879,90467,127971,176201,
%U A238569 242869,333508,456683,606403,844818,1125922,1496466,2005446,2737912,3543506,4824442
%N A238569 Number of compositions of n avoiding any 3-term arithmetic progression.
%H A238569 Fausto A. C. Cariboni, <a href="/A238569/b238569.txt">Table of n, a(n) for n = 0..85</a>
%H A238569 <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>
%e A238569 a(3) = 3: [1,2], [2,1], [3].
%e A238569 a(4) = 7: [1,1,2], [1,2,1], [1,3], [2,1,1], [2,2], [3,1], [4].
%e A238569 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].
%e A238569 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].
%p A238569 b:= proc(n, i, o) option remember; `if`(n=0, 1, add(
%p A238569       `if`(j in o, 0, b(n-j, i union {j}, select(y->0<y
%p A238569        and y<=n, o union map(x->2*j-x, i)))), j=1..n))
%p A238569     end:
%p A238569 a:= n-> b(n, {}, {}):
%p A238569 seq(a(n), n=0..30);
%t A238569 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 *)
%Y A238569 Cf. A003407 (the same for permutations).
%Y A238569 Cf. A178932 (the same for strict partitions).
%Y A238569 Cf. A238423 (the same for consecutive 3-term arithmetic progressions).
%Y A238569 Cf. A238571 (the same for partitions).
%Y A238569 Cf. A238686.
%K A238569 nonn
%O A238569 0,3
%A A238569 _Joerg Arndt_ and _Alois P. Heinz_, Feb 28 2014