OFFSET
0,3
COMMENTS
It appears that this is the number of nonempty subsets of {1,2,...,n} with no gap of length greater than 3 (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). See A119407 for the corresponding problem for gaps of length 4. - John W. Layman, Nov 02 2011
a(n-3) is the number of compositions of n with no part divisible by 3 and an odd number of parts congruent to 4 or 5 modulo 6. See Moser & Whitney reference. a(2) = 3 counts (5), (4,1), and (1,4) among the compositions of 5. - Brian Hopkins, Sep 06 2019
LINKS
Harry J. Smith, Table of n, a(n) for n = 0..300
Zuwen Luo and Kexiang Xu, The number of connected sets in Apollonian networks, Applied Mathematics and Computation, Volume 479, 2024. On ResearchGate. See p. 12.
L. Moser and E. L. Whitney, Weighted compositions, Canad. Math. Bull. 4 (1961), 39-43.
Index entries for linear recurrences with constant coefficients, signature (3,-2,0,-1,1).
FORMULA
a(n) = 3*a(n-1) - 2*a(n-2) - 1*a(n-4) + 1*a(n-5). - Joerg Arndt, Apr 02 2011
a(n) = n + a(n-1) + a(n-2) + a(n-3) =(A001590(n+4) - n - 3)/2.
G.f.: x / ((1 - x) * (1 - 2*x + x^4)). a(n) = 2*a(n-1) - a(n-4) + 1. - Michael Somos, Dec 28 2012
a(n) = A325473(n+3) - (n+3). - Brian Hopkins, Sep 06 2019
EXAMPLE
a(5) = 5 + 15 + 7 + 3 = 30.
x + 3*x^2 + 7*x^3 + 15*x^4 + 30*x^5 + 58*x^6 + 110*x^7 + 206*x^8 + 383*x^9 + ...
MATHEMATICA
Join[{c=0}, a=b=0; Table[z=b+a+c+n; a=b; b=c; c=z, {n, 1, 40}]] (* Vladimir Joseph Stephan Orlovsky, Apr 02 2011 *)
PROG
(PARI) { a=a1=a2=a3=0; for (n=0, 300, write("b062544.txt", n, " ", a+=n + a2 + a3); a3=a2; a2=a1; a1=a ) } \\ Harry J. Smith, Aug 08 2009
(PARI) {a(n) = if( n<0, n = -n; polcoeff( x^4 / ((1 - x) * (1 - 2*x^3 + x^4)) + x * O(x^n), n), polcoeff( x / ((1 - x) * (1 - 2*x + x^4)) + x * O(x^n), n))} /* Michael Somos, Dec 28 2012 */
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Henry Bottomley, Jun 26 2001
STATUS
approved