A300760 Number of ways to select 4 numbers from the set of the first n natural numbers avoiding 3-term arithmetic progressions.
0, 1, 4, 10, 25, 51, 98, 165, 267, 407, 601, 849, 1175, 1580, 2089, 2703, 3452, 4338, 5395, 6622, 8058, 9706, 11606, 13758, 16210, 18963, 22066, 25520, 29379, 33645, 38376, 43571, 49293, 55545, 62391, 69831, 77937, 86710, 96223, 106477, 117550, 129444, 142241
Offset: 4
Examples
There are 4 selections of 4 natural numbers from the set {1,2,3,4,5,6} free of 3-term arithmetic progressions: {1,2,4,5}, {1,2,5,6}, {1,3,4,6}, {2,3,5,6}.
Links
- Heinrich Ludwig, Table of n, a(n) for n = 4..1000
- Index entries for linear recurrences with constant coefficients, signature (2,0,-1,0,-2,2,0,1,0,-2,1).
Programs
-
Mathematica
Array[(#^4 - 12 #^3 + 51 #^2 - 78 # + 32)/24 + Boole[OddQ@ #] (-# + 2)/4 - Boole[Mod[#, 3] == 0]/3 - Boole[Mod[#, 4] == 0] &, 43, 4] (* Michael De Vlieger, Mar 14 2018 *) LinearRecurrence[{2,0,-1,0,-2,2,0,1,0,-2,1},{0,1,4,10,25,51,98,165,267,407,601},50] (* Harvey P. Dale, Feb 18 2024 *)
-
PARI
concat(0, Vec(x^5*(1 + 2*x + 2*x^2 + 6*x^3 + 5*x^4 + 8*x^5) / ((1 - x)^5*(1 + x)^2*(1 + x^2)*(1 + x + x^2)) + O(x^60))) \\ Colin Barker, Aug 06 2018
Formula
a(n) = (n^4 - 12*n^3 + 51*n^2 - 78*n + 32)/24 + b(n) + c(n), where
b(n) = 0 for n even
b(n) = (-n + 2)/4 for n odd
c(n) = 0 for n == 1,2,5,7,10,11 (mod 12)
c(n) = -1/3 for n == 3,6,9 (mod 12)
c(n) = -4/3 for n == 0 (mod 12)
c(n) = -1 for n == 4,8 (mod 12).
a(n) = (n^4 - 12*n^3 + 51*n^2 - 78*n + 32)/24 + (n == 1 (mod 2))*(-n + 2)/4 - (n == 0 (mod 3))/3 - (n == 0 (mod 4)).
From Colin Barker, Mar 12 2018: (Start)
G.f.: x^5*(1 + 2*x + 2*x^2 + 6*x^3 + 5*x^4 + 8*x^5) / ((1 - x)^5*(1 + x)^2*(1 + x^2)*(1 + x + x^2)).
a(n) = 2*a(n-1) - a(n-3) - 2*a(n-5) + 2*a(n-6) + a(n-8) - 2*a(n-10) + a(n-11) for n>14.
(End)