A357291 a(n) = number of subsets S of {1,2,...,n} having more than 2 elements such that (sum of least two elements of S) < difference between greatest two elements of S.

0, 0, 0, 0, 0, 0, 1, 3, 8, 19, 42, 89, 185, 378, 766, 1544, 3102, 6220, 12459, 24939, 49902, 99831, 199692, 399417, 798871, 1597782, 3195608, 6391264, 12782580, 25565216, 51130493, 102261051, 204522172, 409044419, 818088918, 1636177921, 3272355933

Offset

0,8

Links

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

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

Formula

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

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

a(n) ~ A021025*2^n. - Stefano Spezia, Oct 03 2022

a(n) = 2^n/21 - n^2/12 + n/6 + O(1). Conjecture: a(n) = round(2^n/21 - n^2/12 + n/6). - Charles R Greathouse IV, Oct 11 2022

Example

The 3 relevant subsets of {1,2,3,4,5,6,7} are {1, 2, 6}, {1, 2, 7}, {1, 2, 3, 7}.

Mathematica

s[n_] := s[n] = Select[Subsets[Range[n]], Length[#] >= 3 &];
a[n_] := Select[s[n], #[[1]] + #[[2]] < #[[-1]] - #[[-2]] &]
Table[Length[a[n]], {n, 0, 15}]

Crossrefs

Cf. A357290, A357292.

Cf. A021025.

Sequence in context: A229198 A095681 A079583 * A099050 A065352 A161993

Adjacent sequences: A357288 A357289 A357290 * A357292 A357293 A357294

Keyword

nonn,easy

Author

Clark Kimberling, Oct 02 2022

Status

approved