A018788 Number of subsets of {1,...,n} containing an arithmetic progression of length 3.

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)

Wikipedia, Salem-Spencer set

Index entries related to non-averaging sequences

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

Adjacent sequences: A018785 A018786 A018787 * A018789 A018790 A018791

Keyword

nonn

Author

David W. Wilson

Extensions

a(33) from Alois P. Heinz, Jan 31 2014

Status

approved