login
A018788
Number of subsets of {1,...,n} containing an arithmetic progression of length 3.
2
0, 0, 0, 1, 3, 9, 24, 63, 150, 343, 746, 1605, 3391, 7075, 14624, 30076, 61385, 124758, 252618, 510161, 1027632, 2066304, 4148715, 8322113, 16680369, 33413592, 66904484, 133923906, 268009597, 536257466, 1072861536, 2146225299, 4293173040, 8587388627
OFFSET
0,5
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 0..80 (terms up to a(40) from Alois P. Heinz)
FORMULA
a(n) = 2^n - A051013(n). - David Nacin, Mar 03 2012
EXAMPLE
For n=4 the only subsets containing an arithmetic progression of length 3 are {1,2,3}, {2,3,4} and {1,2,3,4}. Thus a(4) = 3. - David Nacin, Mar 03 2012
MATHEMATICA
a[n_] := a[n] = Count[Subsets[Range[n], {3, n}], {___, a_, ___, b_, ___, c_, ___} /; b-a == c-b]; Table[Print[n, " ", a[n]]; a[n], {n, 0, 32}] (* Jean-François Alcover, May 30 2019 *)
PROG
(Python)
# Prints out all such sets
from itertools import combinations as comb
def containsap3(n):
ap3list=list()
for skip in range(1, (n+1)//2):
for start in range (1, n+1-2*skip):
ap3list.append(set({start, start+skip, start+2*skip}))
s=list()
for i in range(3, n+1):
for temptuple in comb(range(1, n+1), i):
tempset=set(temptuple)
for sub in ap3list:
if sub <= tempset:
s.append(tempset)
break
return s #
# Counts all such sets
def a(n):
return len(containsap3(n)) # David Nacin, Mar 03 2012
CROSSREFS
Cf. A051013.
Sequence in context: A006684 A342795 A267465 * A098690 A267960 A268938
KEYWORD
nonn
EXTENSIONS
a(33) from Alois P. Heinz, Jan 31 2014
STATUS
approved