%I #26 Sep 27 2024 05:24:54
%S 1,3,6,16,37,91,218,528,1273,3075,7422,17920,43261,104443,252146,
%T 608736,1469617,3547971,8565558,20679088,49923733,120526555,290976842,
%U 702480240,1695937321,4094354883,9884647086,23863649056,57611945197,139087539451,335787024098
%N a(n) = a(n-1) + 3*a(n-2) + a(n-3) with a(0) = 1, a(1) = 3, a(2) = 6.
%C a(n) is the number of subsets T of A = {1, 2, ..., 2*n} such that no pair of elements a, b of T satisfy |a-b| = 1 or n.
%H Yifan Xie, <a href="/A375726/a375726.txt">Proof for the comment</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,1).
%F a(n) = (1/4)*((3 + sqrt(2))*(1+sqrt(2))^n + (3 - sqrt(2))*(1-sqrt(2))^n-2*(-1)^n).
%F For n >= 2, a(n) = 2*a(n-1) + a(n-2) - (-1)^n.
%F From _Stefano Spezia_, Aug 26 2024: (Start)
%F G.f.: (1 + 2*x)/((1 + x)*(1 - 2*x - x^2)).
%F E.g.f.: (sinh(x) - cosh(x) + exp(x)*(3*cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x)))/2. (End)
%F Let f = (3 - sqrt(2))*exp((1 - sqrt(2))*x) + (3 + sqrt(2))*exp((1 + sqrt(2))*x), then 4*a(n) + 2*(-1)^n = n! * [x^n] f. - _Peter Luschny_, Sep 10 2024
%F a(n)+a(n-1) = A048654(n). - _R. J. Mathar_, Sep 27 2024
%e For n = 2, the a(2) = 6 subsets of {1, 2, 3, 4} are {}, {1}, {2}, {3}, {4}, {1, 4}.
%t LinearRecurrence[{1, 3, 1}, {1, 3, 6}, 31] (* _Hugo Pfoertner_, Aug 26 2024 *)
%o (PARI) my(a=1, b=3, c=6); for(n=1, 31, print1(a, ", "); my(d=a+3*b+c); a=b; b=c; c=d)
%Y Cf. A001333 (b), A000129 (c), A097076 (d).
%K nonn,easy
%O 0,2
%A _Yifan Xie_, Aug 25 2024