

A119407


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 ba=d).


3



1, 3, 7, 15, 31, 62, 122, 238, 462, 894, 1727, 3333, 6429, 12397, 23901, 46076, 88820, 171212, 330028, 636156, 1226237, 2363655, 4556099, 8782171, 16928187, 32630138, 62896622, 121237146, 233692122, 450456058, 868281979, 1673667337, 3226097529, 6218502937, 11986549817, 23104817656
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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.


LINKS

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3, 2, 0, 0, 1, 1).


FORMULA

G.f. for number of nonempty subsets of {1,2,...,n} with no gap of length greater than d is x/((1x)*(12*x+x^(d+1))).  Vladeta Jovovic, Apr 27 2008
From Michael Somos, Dec 28 2012: (Start)
G.f.: x/((1x)^2*(1xx^2x^3x^4)) = x/((1x)*(12*x+x^5)).
First difference is A107066. (End)


EXAMPLE

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


MATHEMATICA

Rest@CoefficientList[Series[x/((1x)*(12*x+x^5)), {x, 0, 40}], x] (* G. C. Greubel, Jun 05 2019 *)
LinearRecurrence[{3, 2, 0, 0, 1, 1}, {1, 3, 7, 15, 31, 62}, 40] (* Harvey P. Dale, Dec 04 2019 *)


PROG

(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 */
(PARI) my(x='x+O('x^40)); Vec(x/((1x)*(12*x+x^5))) \\ G. C. Greubel, Jun 05 2019
(MAGMA) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( x/((1x)*(12*x+x^5)) )); // G. C. Greubel, Jun 05 2019
(Sage) a=(x/((1x)*(12*x+x^5))).series(x, 40).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Jun 05 2019


CROSSREFS

Cf. A000217, A001924, A062544, A107066.
Sequence in context: A218281 A057703 A006739 * A224521 A269167 A261586
Adjacent sequences: A119404 A119405 A119406 * A119408 A119409 A119410


KEYWORD

nonn,changed


AUTHOR

John W. Layman, Jul 25 2006


EXTENSIONS

Terms a(25) onward added by G. C. Greubel, Jun 05 2019


STATUS

approved



