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,2

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.

Links

Table of n, a(n) for n=0..30.

Yifan Xie, Proof for the comment

Index entries for linear recurrences with constant coefficients, signature (1,3,1).

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

Example

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

Mathematica

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

Prog

(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)

Crossrefs

Cf. A001333 (b), A000129 (c), A097076 (d).

Sequence in context: A293993 A072824 A360229 * A369432 A089406 A027852

Adjacent sequences: A375723 A375724 A375725 * A375727 A375728 A375729

Keyword

nonn,easy

Author

Yifan Xie, Aug 25 2024

Status

approved