login
Number of nonempty subsets of {1,2,...,n} with no gap of length greater than 4 (a set S has a gap of length d if a and b are in S but no x with a < x < b is in S, where b-a=d).
3

%I #31 Sep 08 2022 08:45:25

%S 1,3,7,15,31,62,122,238,462,894,1727,3333,6429,12397,23901,46076,

%T 88820,171212,330028,636156,1226237,2363655,4556099,8782171,16928187,

%U 32630138,62896622,121237146,233692122,450456058,868281979,1673667337,3226097529,6218502937,11986549817,23104817656

%N Number of nonempty subsets of {1,2,...,n} with no gap of length greater than 4 (a set S has a gap of length d if a and b are in S but no x with a < x < b is in S, where b-a=d).

%C The numbers of subsets of {1,2,...,n} with no gap of length greater than d, for d=1,2 and 3, seem to be given in A000217, A001924 and A062544, respectively.

%H G. C. Greubel, <a href="/A119407/b119407.txt">Table of n, a(n) for n = 1..1000</a>

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

%F G.f. for number of nonempty subsets of {1,2,...,n} with no gap of length greater than d is x/((1-x)*(1-2*x+x^(d+1))). - _Vladeta Jovovic_, Apr 27 2008

%F From _Michael Somos_, Dec 28 2012: (Start)

%F G.f.: x/((1-x)^2*(1-x-x^2-x^3-x^4)) = x/((1-x)*(1-2*x+x^5)).

%F First difference is A107066. (End)

%F a(n-3) = Sum_{k=0..n} (n-k)*A000078(k) for n>3. - _Greg Dresden_, Jan 01 2021

%e G.f. = x + 3*x^2 + 7*x^3 + 15*x^4 + 31*x^5 + 62*x^6 + 122*x^7 + 238*x^8 + 462*x^9 + ...

%t Rest@CoefficientList[Series[x/((1-x)*(1-2*x+x^5)), {x, 0, 40}], x] (* _G. C. Greubel_, Jun 05 2019 *)

%t LinearRecurrence[{3,-2,0,0,-1,1},{1,3,7,15,31,62},40] (* _Harvey P. Dale_, Dec 04 2019 *)

%o (PARI) {a(n) = if( n<0, n = -n; polcoeff( x^5 / ((1 - x)^2 * (1 + x + x^2 + x^3 - x^4)) + x * O(x^n), n), polcoeff( x / ((1 - x)^2 * (1 - x - x^2 - x^3 - x^4)) + x * O(x^n), n))} /* _Michael Somos_, Dec 28 2012 */

%o (PARI) my(x='x+O('x^40)); Vec(x/((1-x)*(1-2*x+x^5))) \\ _G. C. Greubel_, Jun 05 2019

%o (Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( x/((1-x)*(1-2*x+x^5)) )); // _G. C. Greubel_, Jun 05 2019

%o (Sage) a=(x/((1-x)*(1-2*x+x^5))).series(x, 40).coefficients(x, sparse=False); a[1:] # _G. C. Greubel_, Jun 05 2019

%Y Cf. A000217, A001924, A062544, A107066.

%K nonn

%O 1,2

%A _John W. Layman_, Jul 25 2006

%E Terms a(25) onward added by _G. C. Greubel_, Jun 05 2019