A238569 - OEIS

%I #24 Feb 16 2022 07:07:00

%S 1,1,2,3,7,11,19,28,53,83,140,201,332,486,775,1207,1716,2498,3870,

%T 5623,8020,11276,17168,23323,34746,46141,64879,90467,127971,176201,

%U 242869,333508,456683,606403,844818,1125922,1496466,2005446,2737912,3543506,4824442

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

%H Fausto A. C. Cariboni, <a href="/A238569/b238569.txt">Table of n, a(n) for n = 0..85</a>

%H <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>

%e a(3) = 3: [1,2], [2,1], [3].

%e a(4) = 7: [1,1,2], [1,2,1], [1,3], [2,1,1], [2,2], [3,1], [4].

%e 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 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 b:= proc(n, i, o) option remember; `if`(n=0, 1, add(

%p       `if`(j in o, 0, b(n-j, i union {j}, select(y->0<y

%p        and y<=n, o union map(x->2*j-x, i)))), j=1..n))

%p     end:

%p a:= n-> b(n, {}, {}):

%p seq(a(n), n=0..30);

%t 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 Cf. A003407 (the same for permutations).

%Y Cf. A178932 (the same for strict partitions).

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

%Y Cf. A238571 (the same for partitions).

%Y Cf. A238686.

%K nonn

%O 0,3

%A _Joerg Arndt_ and _Alois P. Heinz_, Feb 28 2014