A356619 a(n) = number of k-tuples (u(1), u(2), ..., u(k)) with 1 <= u(1) < u(2) < ... < u(k) <= n such that u(i) - u(i-1) <= 3 for i = 2,...,k.

0, 1, 4, 11, 25, 52, 103, 198, 374, 699, 1298, 2401, 4431, 8166, 15037, 27676, 50924, 93685, 172336, 316999, 583077, 1072472, 1972611, 3628226, 6673378, 12274287, 22575966, 41523709, 76374043, 140473802, 258371641, 475219576, 874065112, 1607656425

Offset

0,3

Links

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

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

Formula

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

a(n) = 3*a(n-1) - 2*a(n-2) - a(n-4) + a(n-5).

a(n) = A221949(n+2)-1 for n >= 0.

Mathematica

maxDiff = 3;
t = Map[Length[Select[Map[{#, Max[Differences[#]]} &,
     Drop[Subsets[Range[#]], # + 1]], #[[2]] <= maxDiff &]] &, Range[16]]
FindGeneratingFunction[%, x]
FindLinearRecurrence[t]
LinearRecurrence[{3, -2, 0, -1, 1}, {0, 1, 4, 11, 25}, 45]

Crossrefs

Cf. A001891, A062544, A221949, A356620, A356621.

Sequence in context: A014162 A014169 A113684 * A014173 A290986 A209232

Adjacent sequences: A356616 A356617 A356618 * A356620 A356621 A356622

Keyword

nonn,easy

Author

Clark Kimberling, Aug 24 2022

Status

approved