A375726 a(n) = a(n-1) + 3*a(n-2) + a(n-3) with a(0) = 1, a(1) = 3, a(2) = 6.

1, 3, 6, 16, 37, 91, 218, 528, 1273, 3075, 7422, 17920, 43261, 104443, 252146, 608736, 1469617, 3547971, 8565558, 20679088, 49923733, 120526555, 290976842, 702480240, 1695937321, 4094354883, 9884647086, 23863649056, 57611945197, 139087539451, 335787024098

Offset: 0

Author

Yifan Xie, Aug 25 2024

Keywords

• nonn
• easy

Comments

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.

Examples

			For n = 2, the a(2) = 6 subsets of {1, 2, 3, 4} are {}, {1}, {2}, {3}, {4}, {1, 4}.
		

Links

• Yifan Xie, Table of n, a(n) for n = 0..2612
• Yifan Xie, Proof for the comment
• Index entries for linear recurrences with constant coefficients, signature (1,3,1).

Crossrefs

Cf. A001333, A000129, A097076.

Programs

Mathematica

LinearRecurrence[{1, 3, 1}, {1, 3, 6}, 31] (* Hugo Pfoertner, Aug 26 2024 *)

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)

Formula

a(n) = (1/4)*((3 + sqrt(2))*(1+sqrt(2))^n + (3 - sqrt(2))*(1-sqrt(2))^n-2*(-1)^n).

For n >= 2, a(n) = 2*a(n-1) + a(n-2) - (-1)^n.

From Stefano Spezia, Aug 26 2024: (Start)

G.f.: (1 + 2*x)/((1 + x)*(1 - 2*x - x^2)).

E.g.f.: (sinh(x) - cosh(x) + exp(x)*(3*cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x)))/2. (End)

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

a(n)+a(n-1) = A048654(n). - R. J. Mathar, Sep 27 2024