A300760 - OEIS

%I #38 Feb 18 2024 12:20:42

%S 0,1,4,10,25,51,98,165,267,407,601,849,1175,1580,2089,2703,3452,4338,

%T 5395,6622,8058,9706,11606,13758,16210,18963,22066,25520,29379,33645,

%U 38376,43571,49293,55545,62391,69831,77937,86710,96223,106477,117550,129444,142241

%N Number of ways to select 4 numbers from the set of the first n natural numbers avoiding 3-term arithmetic progressions.

%H Heinrich Ludwig, <a href="/A300760/b300760.txt">Table of n, a(n) for n = 4..1000</a>

%H <a href="/index/Rec#order_11">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1,0,-2,2,0,1,0,-2,1).

%F a(n) = (n^4 - 12*n^3 + 51*n^2 - 78*n + 32)/24 + b(n) + c(n), where

%F   b(n) = 0          for n even

%F   b(n) = (-n + 2)/4 for n odd

%F   c(n) = 0          for n == 1,2,5,7,10,11 (mod 12)

%F   c(n) = -1/3       for n == 3,6,9         (mod 12)

%F   c(n) = -4/3       for n == 0             (mod 12)

%F   c(n) = -1         for n == 4,8           (mod 12).

%F 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)).

%F From _Colin Barker_, Mar 12 2018: (Start)

%F 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)).

%F 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.

%F (End)

%e 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}.

%t 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 *)

%t 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 *)

%o (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

%Y Cf. A212964, A300761.

%Y Column k=4 of A334187.

%K nonn,easy

%O 4,3

%A _Heinrich Ludwig_, Mar 12 2018