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.

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).

Links

Table of n, a(n) for n=3..68.

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

Cf. A209438, A209439, A209490.

Sequence in context: A013450 A013421 A011081 * A201575 A194796 A147600

Adjacent sequences: A209488 A209489 A209490 * A209492 A209493 A209494

Keyword

nonn,tabl

Author

David Nacin, Mar 09 2012

Status

approved