A330910 -id:A330910 - cp's OEIS frontend

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

Enrique Navarrete, May 25 2020

nonn

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

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

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

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

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

a(n) = {my(d=6); sum(k=0, (n-1)\d, binomial(n-d*k+k+1, k+2))} \\ Andrew Howroyd, Aug 11 2020

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)

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula