A334187
Number T(n,k) of k-element subsets of [n] avoiding 3-term arithmetic progressions; triangle T(n,k), n>=0, 0<=k<=A003002(n), read by rows.
Original entry on oeis.org
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 4, 6, 2, 1, 5, 10, 6, 1, 1, 6, 15, 14, 4, 1, 7, 21, 26, 10, 1, 8, 28, 44, 25, 1, 9, 36, 68, 51, 4, 1, 10, 45, 100, 98, 24, 1, 11, 55, 140, 165, 64, 7, 1, 12, 66, 190, 267, 144, 25, 1, 13, 78, 250, 407, 284, 78, 6, 1, 14, 91, 322, 601, 520, 188, 22, 1
Offset: 0
Triangle T(n,k) begins:
1;
1, 1;
1, 2, 1;
1, 3, 3;
1, 4, 6, 2;
1, 5, 10, 6, 1;
1, 6, 15, 14, 4;
1, 7, 21, 26, 10;
1, 8, 28, 44, 25;
1, 9, 36, 68, 51, 4;
1, 10, 45, 100, 98, 24;
1, 11, 55, 140, 165, 64, 7;
1, 12, 66, 190, 267, 144, 25;
1, 13, 78, 250, 407, 284, 78, 6;
1, 14, 91, 322, 601, 520, 188, 22, 1;
1, 15, 105, 406, 849, 862, 386, 64, 4;
1, 16, 120, 504, 1175, 1394, 763, 164, 14;
...
Last elements of rows give
A262347.
-
b:= proc(n, s) option remember; `if`(n=0, 1, b(n-1, s)+ `if`(
ormap(j-> 2*j-n in s, s), 0, expand(x*b(n-1, s union {n}))))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, {})):
seq(T(n), n=0..16);
-
b[n_, s_] := b[n, s] = If[n == 0, 1, b[n-1, s] + If[AnyTrue[s, MemberQ[s, 2 # - n]&], 0, Expand[x b[n-1, s ~Union~ {n}]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, {}]];
T /@ Range[0, 16] // Flatten (* Jean-François Alcover, May 30 2020, after Maple *)
A140577
Decimal expansion of Wroblewski's constant arising in nonaveraging sequences.
Original entry on oeis.org
3, 0, 0, 8, 4, 9
Offset: 1
- Steven R. Finch, "Erdos' Reciprocal Sum Constants." 2.20 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 163-166, 2003.
- R. K. Guy, "Nonaveraging Sets. Nondividing Sets." C16 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 131-132, 1994.
A334893
Number of subsets of [n] avoiding 3-term arithmetic progressions and containing n if n>0.
Original entry on oeis.org
1, 1, 2, 3, 6, 10, 17, 25, 41, 63, 109, 165, 262, 412, 643, 932, 1459, 2163, 3212, 4601, 6817, 9904, 14741, 20906, 30352, 43993, 63540, 89442, 132037, 187587, 266842, 378061, 535907, 751709, 1077809, 1499972, 2084027, 2951390, 4114165, 5651914, 7968177
Offset: 0
-
b:= proc(n, s) option remember; `if`(n<1, 1, b(n-1, s)+
`if`(ormap(j-> 2*j-n in s, s), 0, b(n-1, s union {n})))
end:
a:= n-> b(n-1, {n}):
seq(a(n), n=0..23);
-
b[n_, s_] := b[n, s] = If[n < 1, 1, b[n-1, s] +
If[AnyTrue[s, MemberQ[s, 2 # - n]&], 0, b[n-1, s ~Union~ {n}]]];
a[n_] := b[n-1, {n}];
a /@ Range[0, 23] (* Jean-François Alcover, May 03 2021, after Alois P. Heinz *)
A018788
Number of subsets of {1,...,n} containing an arithmetic progression of length 3.
Original entry on oeis.org
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
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
-
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 *)
-
# 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
A136299
a(n) = 3*a(n-1) - 4*a(n-3), with a(0)=1, a(1)=2, a(2)=4, a(3)=7.
Original entry on oeis.org
1, 2, 4, 7, 13, 23, 41, 71, 121, 199, 313, 455, 569, 455, -455, -3641, -12743, -36409, -94663, -233017, -553415, -1281593, -2912711, -6524473, -14447047, -31690297, -68972999, -149130809, -320631239, -686001721, -1461481927, -3101920825, -6561755591, -13839339065
Offset: 0
-
[1] cat [(2^(n-2)*(41-3*n) + (-1)^n)/9: n in [1..40]]; // G. C. Greubel, Apr 12 2021
-
LinearRecurrence[{3,0,-4}, {1,2,4,7}, 41] (* G. C. Greubel, Apr 12 2021 *)
-
[1]+[(2^(n-2)*(41-3*n) + (-1)^n)/9 for n in (1..40)] # G. C. Greubel, Apr 12 2021
A066369
Number of subsets of {1, ..., n} with no four terms in arithmetic progression.
Original entry on oeis.org
1, 2, 4, 8, 15, 29, 56, 103, 192, 364, 668, 1222, 2233, 3987, 7138, 12903, 22601, 40200, 71583, 125184, 218693, 386543, 670989, 1164385, 2021678, 3462265, 5930954, 10189081, 17266616, 29654738, 50912618, 86017601, 145327544, 247555043, 415598432, 698015188
Offset: 0
a(5) = 29 because there are 32 subsets and three of them contain four terms in arithmetic progression: {1, 2, 3, 4}, {2, 3, 4, 5} and {1, 2, 3, 4, 5}.
-
from sympy import subsets
def noap4(n):
avoid=list()
for skip in range(1,(n+2)//3):
for start in range (1,n+1-3*skip):
avoid.append(set({start,start+skip,start+2*skip,start+3*skip}))
s=list()
for i in range(4):
for smallset in subsets(range(1,n+1),i):
s.append(smallset)
for i in range(4,n+1):
for temptuple in subsets(range(1,n+1),i):
tempset=set(temptuple)
status=True
for avoidset in avoid:
if avoidset <= tempset:
status=False
break
if status:
s.append(tempset)
return s
# Counts all such sets
def a(n):
return len(noap4(n)) # David Nacin, Mar 05 2012
Showing 1-6 of 6 results.
Comments