|
| |
|
|
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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
a(n) = Sum_{k=0..floor((n-1)/6)} binomial(n-6*k+k+1, k+2). - Andrew Howroyd, Aug 11 2020
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
