%I #47 Jun 19 2024 02:04:52
%S 0,1,3,7,15,30,58,110,206,383,709,1309,2413,4444,8180,15052,27692,
%T 50941,93703,172355,317019,583098,1072494,1972634,3628250,6673403,
%U 12274313,22575993,41523737,76374072,140473832,258371672,475219608,874065145,1607656459,2956941247
%N a(n) = n plus sum of previous three terms.
%C 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
%C 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
%H Harry J. Smith, <a href="/A062544/b062544.txt">Table of n, a(n) for n = 0..300</a>
%H Zuwen Luo and Kexiang Xu, <a href="https://doi.org/10.1016/j.amc.2024.128883">The number of connected sets in Apollonian networks</a>, Applied Mathematics and Computation, Volume 479, 2024. On <a href="https://www.researchgate.net/publication/381160571_The_number_of_connected_sets_in_Apollonian_networks">ResearchGate</a>. See p. 12.
%H L. Moser and E. L. Whitney, <a href="https://doi.org/10.4153/CMB-1961-006-0">Weighted compositions</a>, Canad. Math. Bull. 4 (1961), 39-43.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,0,-1,1).
%F a(n) = 3*a(n-1) - 2*a(n-2) - 1*a(n-4) + 1*a(n-5). - _Joerg Arndt_, Apr 02 2011
%F a(n) = n + a(n-1) + a(n-2) + a(n-3) =(A001590(n+4) - n - 3)/2.
%F 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
%F a(n) = A325473(n+3) - (n+3). - _Brian Hopkins_, Sep 06 2019
%e a(5) = 5 + 15 + 7 + 3 = 30.
%e 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 + ...
%t 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 *)
%o (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
%o (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 */
%Y n plus sum of all previous terms gives A000225, n plus sum of two previous terms gives A001924, n plus previous term gives A000217, n gives A001477.
%Y Cf. A007800, A119407.
%Y Cf. A001590 and A325473.
%K nonn,easy
%O 0,3
%A _Henry Bottomley_, Jun 26 2001