login
A238569
Number of compositions of n avoiding any 3-term arithmetic progression.
6
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
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
KEYWORD
nonn
AUTHOR
Joerg Arndt and Alois P. Heinz, Feb 28 2014
STATUS
approved