A209436 Table of a(n,m) = number of subsets of {1,...,n} which contain two elements whose difference is m+1.

0, 0, 0, 1, 0, 0, 3, 0, 0, 0, 8, 2, 0, 0, 0, 19, 7, 0, 0, 0, 0, 43, 17, 4, 0, 0, 0, 0, 94, 39, 14, 0, 0, 0, 0, 0, 201, 88, 37, 8, 0, 0, 0, 0, 0, 423, 192, 83, 28, 0, 0, 0, 0, 0, 0, 880, 408, 181, 74, 16, 0, 0, 0, 0, 0, 0, 1815, 855, 387, 175, 56, 0, 0, 0, 0

Offset

0,7

Links

G. C. Greubel, Table of n, a(n) for the first 100 aintidiagonals, flattened

M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.

Formula

a(n,m) = 2^n - Product_{i=0 to m} F(floor[(n + i)/(m + 1) + 2]) where F(n) is the n-th Fibonacci number.

Example

Table begins:
0,   0,   0,   0,   0,   0,   0,   0,   0,   0, 0, ...
0,   0,   0,   0,   0,   0,   0,   0,   0,   0, 0, ...
1,   0,   0,   0,   0,   0,   0,   0,   0,   0, 0, ...
3,   2,   0,   0,   0,   0,   0,   0,   0,   0, 0, ...
8,   7,   4,   0,   0,   0,   0,   0,   0,   0, 0, ...
19,  17,  14,  8,   0,   0,   0,   0,   0,   0, 0, ...
43,  39,  37,  28,  16,  0,   0,   0,   0,   0, 0, ...
94,  88,  83,  74,  56,  32,  0,   0,   0,   0, 0, ...
201, 192, 181, 175, 148, 112, 64,  0,   0,   0, 0, ...
423, 408, 387, 377, 350, 296, 224, 128, 0,   0, 0, ...
880, 855, 824, 799, 781, 700, 592, 448, 256, 0, 0, ...
......................................................
a(3,1) is the number of subsets of {1,2,3} containing two elements whose difference is two.  There are 2 of these: {1,3} and {1,2,3} so a(1,3) = 2.

Mathematica

a[n_, m_] := 2^n - Product[Fibonacci[Floor[(n + i)/(m + 1) + 2]], {i, 0, m}]; Flatten[Table[a[j - i, i], {j, 0, 20}, {i, 0, j}]]

Crossrefs

Cf. A209434, A209435, A209437.

Sequence in context: A344876 A129170 A342590 * A229121 A190609 A370146

Adjacent sequences: A209433 A209434 A209435 * A209437 A209438 A209439

Keyword

nonn,tabl

Author

David Nacin, Mar 09 2012

Status

approved