OFFSET
0,9
COMMENTS
For n >= 6 the sequence contains the triangular numbers; for n >= 12 we have to add the tetrahedral numbers; for n >= 18 we have to add the numbers binomial(n,4) (starting with 0,1,5,...); for n >= 24 we have to add the numbers binomial(n,5) (starting with 0,1,6,..); in general, for n >= 6*k we have to add to the sequence the numbers binomial(n, k+1), k >= 1.
For example, a(26) = 1106 = 210+560+330+6, where 210 is a triangular number, 560 is a tetrahedral number, 330 is a number binomial(n,4) and 6 is a number binomial(m,5) (with the proper n, m due to shifts in names of the sequences).
The sequence counts sets with more than 2 elements such as {1,7,14}, {1,8,14}, {2,8,14,20}, etc. The first 3-element set is {1,7,13}, the first 4-element set is {1,7,13,19}, etc. Every time a larger set needs to be counted is when we have to add a term binomial(n, k+1).
LINKS
Index entries for linear recurrences with constant coefficients, signature (3,-3,1,0,0,1,-2,1).
FORMULA
a(n) = Sum_{k=0..floor((n-1)/6)} binomial(n-6*k+k+1, k+2). - Andrew Howroyd, Aug 11 2020
From Colin Barker, May 26 2020: (Start)
G.f.: x^7 / ((1 - x)^2*(1 - x - x^6)).
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) + a(n-6) - 2*a(n-7) + a(n-8) for n>=8.
(End)
EXAMPLE
a(11) = 15 and the 15 subsets of {1,2,...11} with at least two elements and whose difference between successive elements is at least 6 are: {1,7}, {1,8}, {1,9}, {1,10}, {1,11}, {2,8}, {2,9}, {2,10}, {2,11}, {3,9}, {3,10}, {3,11}, {4,10}, {4,11}, {5,11}.
MATHEMATICA
With[{k = 6}, Array[Count[Subsets[Range[# + k], {2, # + k}], _?(AllTrue[Differences@ #, # >= k &] &)] &, 16]] (* Michael De Vlieger, Jun 26 2020 *)
LinearRecurrence[{3, -3, 1, 0, 0, 1, -2, 1}, {0, 0, 0, 0, 0, 0, 0, 1}, 60] (* Harvey P. Dale, Nov 22 2022 *)
PROG
(PARI) a(n) = {my(d=6); sum(k=0, (n-1)\d, binomial(n-d*k+k+1, k+2))} \\ Andrew Howroyd, Aug 11 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Enrique Navarrete, May 25 2020
STATUS
approved