login
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

%I #33 Nov 22 2022 19:26:20

%S 0,0,0,0,0,0,0,1,3,6,10,15,21,29,40,55,75,101,134,176,230,300,391,509,

%T 661,856,1106,1427,1840,2372,3057,3938,5070,6524,8392,10793,13880,

%U 17849,22951,29508,37934,48762,62678,80564,103553,133100,171074,219877,282597,363204,466801,599946,771066,990990

%N 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.

%C 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.

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

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

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1,0,0,1,-2,1).

%F a(n) = Sum_{k=0..floor((n-1)/6)} binomial(n-6*k+k+1, k+2). - _Andrew Howroyd_, Aug 11 2020

%F From _Colin Barker_, May 26 2020: (Start)

%F G.f.: x^7 / ((1 - x)^2*(1 - x - x^6)).

%F 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.

%F (End)

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

%t With[{k = 6}, Array[Count[Subsets[Range[# + k], {2, # + k}], _?(AllTrue[Differences@ #, # >= k &] &)] &, 16]] (* _Michael De Vlieger_, Jun 26 2020 *)

%t LinearRecurrence[{3,-3,1,0,0,1,-2,1},{0,0,0,0,0,0,0,1},60] (* _Harvey P. Dale_, Nov 22 2022 *)

%o (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

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

%K nonn

%O 0,9

%A _Enrique Navarrete_, May 25 2020