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

1, 0, 3, 0, 0, 8, 0, 0, 4, 20, 0, 0, 0, 15, 47, 0, 0, 0, 0, 37, 107, 0, 0, 0, 0, 16, 87, 238, 0, 0, 0, 0, 0, 60, 200, 520, 0, 0, 0, 0, 0, 0, 169, 448, 1121, 0, 0, 0, 0, 0, 0, 64, 387, 992, 2391, 0, 0, 0, 0, 0, 0, 0, 240, 865, 2160, 5056

Offset

3,3

Comments

Offset for n is 3, offset for d is 1, thus 1st entry is T(1,3).

Links

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

Formula

T(d,n) = 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, 3, 8, 20, 47, 107, 238, 520 ...
0, 0, 4, 15, 37, 87,  200, 448 ...
0, 0, 0, 0,  16, 60,  169, 387 ...
0, 0, 0, 0,  0,  0,   64,  240 ...
0, 0, 0, 0,  0,  0,   0,   0   ...
0, 0, 0, 0,  0,  0,   0,   0   ...
0, 0, 0, 0,  0,  0,   0,   0   ...
0, 0, 0, 0,  0,  0,   0,   0   ...
0, 0, 0, 0,  0,  0,   0,   0   ...
0, 0, 0, 0,  0,  0,   0,   0   ...
..................................
For T(2,5) 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(2,5) = 4.

Mathematica

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

Crossrefs

Cf. A209491, A209438, A209439.

Sequence in context: A227724 A218538 A243163 * A346879 A326397 A140577

Adjacent sequences: A209487 A209488 A209489 * A209491 A209492 A209493

Keyword

nonn,tabl

Author

David Nacin, Mar 09 2012

Status

approved