A335184 a(n) is the number of subsets of {1,2,...,n} with at least two elements and the difference between successive elements at least 6.

0, 0, 0, 0, 0, 0, 0, 1, 3, 6, 10, 15, 21, 29, 40, 55, 75, 101, 134, 176, 230, 300, 391, 509, 661, 856, 1106, 1427, 1840, 2372, 3057, 3938, 5070, 6524, 8392, 10793, 13880, 17849, 22951, 29508, 37934, 48762, 62678, 80564, 103553, 133100, 171074, 219877, 282597, 363204, 466801, 599946, 771066, 990990

Offset: 0

Author

Enrique Navarrete, May 25 2020

Keywords

• nonn

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

Examples

			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}.
		

Links

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

Crossrefs

Similar sequences with minimum difference 1..5 are A000295, A001924, A050228, A145131, A330910.

Programs

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

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

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)