login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Table T(n,d), read by antidiagonals, gives the number of subsets of length n containing an arithmetic progression of length 3 with distance d.
3

%I #16 Mar 24 2017 00:47:54

%S 1,3,0,8,0,0,20,4,0,0,47,15,0,0,0,107,37,0,0,0,0,238,87,16,0,0,0,0,

%T 520,200,60,0,0,0,0,0,1121,448,169,0,0,0,0,0,0,2391,992,387,64,0,0,0,

%U 0,0,0,5056,2160,865,240,0,0,0,0,0,0,0

%N Table T(n,d), read by antidiagonals, gives the number of subsets of length n containing an arithmetic progression of length 3 with distance d.

%C n offset is 3, d offset is 1, so 1st term is T(3,1).

%F T(n,d) = 2^n - prod_{1=0 to d-1} Tri(floor((n + i)/d) + 2) where Tri(n) is the n-th tribonacci number.

%e Table begins:

%e 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ...

%e 3, 0, 0, 0, 0, 0, 0, 0, 0, 0 ...

%e 8, 4, 0, 0, 0, 0, 0, 0, 0, 0 ...

%e 20, 15, 0, 0, 0, 0, 0, 0, 0, 0 ...

%e 47, 37, 16, 0, 0, 0, 0, 0, 0, 0 ...

%e 107, 87, 60, 0, 0, 0, 0, 0, 0, 0 ...

%e 238, 200, 169, 64, 0, 0, 0, 0, 0, 0 ...

%e 520, 448, 387, 240, 0, 0, 0, 0, 0, 0 ...

%e ........................................

%e For T(5,2) we count subsets of {1,...,5} containing {1,3,5}, the only d=2 AP possible here. There are 4 subsets containing {1,3,5} so T(5,2) = 4.

%t T[0]=0; T[1] = 1; T[2] = 1; T[n_] := T[n - 1] + T[n - 2] + T[n - 3]; a[n_, d_] := 2^n - Product[T[Floor[(n + i)/d] + 2], {i, 0, d - 1}]; Table[a[i, j], {i, 3, 10}, {j, 1, 10}]; Flatten[Table[a[j - i + 3, i + 1], {j, 0, 10}, {i, 0, j}]];

%Y Cf. A209438, A209439, A209490.

%K nonn,tabl

%O 3,2

%A _David Nacin_, Mar 09 2012