login
A209491
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
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, 520, 200, 60, 0, 0, 0, 0, 0, 1121, 448, 169, 0, 0, 0, 0, 0, 0, 2391, 992, 387, 64, 0, 0, 0, 0, 0, 0, 5056, 2160, 865, 240, 0, 0, 0, 0, 0, 0, 0
OFFSET
3,2
COMMENTS
n offset is 3, d offset is 1, so 1st term is T(3,1).
FORMULA
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.
EXAMPLE
Table begins:
1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ...
3, 0, 0, 0, 0, 0, 0, 0, 0, 0 ...
8, 4, 0, 0, 0, 0, 0, 0, 0, 0 ...
20, 15, 0, 0, 0, 0, 0, 0, 0, 0 ...
47, 37, 16, 0, 0, 0, 0, 0, 0, 0 ...
107, 87, 60, 0, 0, 0, 0, 0, 0, 0 ...
238, 200, 169, 64, 0, 0, 0, 0, 0, 0 ...
520, 448, 387, 240, 0, 0, 0, 0, 0, 0 ...
........................................
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.
MATHEMATICA
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}]];
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
David Nacin, Mar 09 2012
STATUS
approved