A062544 a(n) = n plus sum of previous three terms.

0, 1, 3, 7, 15, 30, 58, 110, 206, 383, 709, 1309, 2413, 4444, 8180, 15052, 27692, 50941, 93703, 172355, 317019, 583098, 1072494, 1972634, 3628250, 6673403, 12274313, 22575993, 41523737, 76374072, 140473832, 258371672, 475219608, 874065145, 1607656459, 2956941247

Offset: 0

Author

Henry Bottomley, Jun 26 2001

Keywords

• nonn
• easy

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 aA119407 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

Examples

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

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

Crossrefs

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.

Cf. A007800, A119407.

Cf. A001590 and A325473.

Programs

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 *)

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 */

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