login
Number of nonaveraging subsets on {1,2,...,n}.
7

%I #44 Feb 17 2024 08:11:19

%S 1,2,4,7,13,23,40,65,106,169,278,443,705,1117,1760,2692,4151,6314,

%T 9526,14127,20944,30848,45589,66495,96847,140840,204380,293822,425859,

%U 613446,880288,1258349,1794256,2545965,3623774,5123746,7207773,10159163,14273328,19925242,27893419

%N Number of nonaveraging subsets on {1,2,...,n}.

%H Fausto A. C. Cariboni, <a href="/A051013/b051013.txt">Table of n, a(n) for n = 0..80</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/NonaveragingSequence.html">Nonaveraging Sequence</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Salem-Spencer_set">Salem-Spencer set</a>

%H <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>

%F a(n) = 2^n - A018788(n). - _David Nacin_, Mar 03 2012

%e The only subset of s = {1,2,3} that contains a 3-term arithmetic progression is s itself, so a(3) = 7.

%t a[n_] := a[n] = 2^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 *)

%o (Python)

%o # Prints out all such sets

%o def nonaveragingsets(n):

%o avoid=list()

%o for skip in range(1,(n+1)//2):

%o for start in range (1,n+1-2*skip):

%o avoid.append(set({start,start+skip,start+2*skip}))

%o s=list()

%o for i in range(3):

%o for smallset in comb(range(1,n+1),i):

%o s.append(smallset)

%o for i in range(3,n+1):

%o for temptuple in comb(range(1,n+1),i):

%o tempset=set(temptuple)

%o status=True

%o for avoidset in avoid:

%o if avoidset <= tempset:

%o status=False

%o break

%o if status:

%o s.append(tempset)

%o return s

%o # Counts all such sets

%o def a(n):

%o return len(nonaveragingsets(n)) # _David Nacin_, Mar 03 2012

%Y Cf. A018788.

%Y Row sums of A334187.

%Y First differences give A334893.

%K nonn

%O 0,2

%A _Eric W. Weisstein_

%E More terms from _John W. Layman_, Nov 27 2001

%E a(29)-a(37) from _Donovan Johnson_, Aug 15 2010

%E a(38)-a(40) from _Alois P. Heinz_, Oct 27 2011