login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001609 a(1) = a(2) = 1, a(3) = 4; thereafter a(n) = a(n-1) + a(n-3).
(Formerly M3240 N1308)
15
1, 1, 4, 5, 6, 10, 15, 21, 31, 46, 67, 98, 144, 211, 309, 453, 664, 973, 1426, 2090, 3063, 4489, 6579, 9642, 14131, 20710, 30352, 44483, 65193, 95545, 140028, 205221, 300766, 440794, 646015, 946781, 1387575, 2033590, 2980371, 4367946, 6401536, 9381907 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 1...m-1, a(m) = m+1. The generating function is (x+m*x^m)/(1-x-x^m). Also a(n) = 1 + n*sum(binomial(n-1-(m-1)*i, i-1)/i, i=1..n/m). This gives the number of ways to cover (without overlapping) a ring lattice (or necklace) of n sites with molecules that are m sites wide. Special cases: m=2: A000204, m=3: A001609, m=4: A014097, m=5: A058368, m=6: A058367, m=7: A058366, m=8: A058365, m=9: A058364.

The sequence defined by a(n)-1 plays a role for the computation of A065414, A146486, A146487, and A146488 equivalent to the role of A001610 for A005596, A146482, A146483 and A146484, see the variable a_{2,n} in arXiv:0903.2514. - R. J. Mathar, Mar 28 2009

REFERENCES

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Indranil Ghosh, Table of n, a(n) for n = 1..6012 (terms 1..500 from T. D. Noe)

E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.

Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.

Daniel C. Fielder, Errata:Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.

Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 91.

Matthew Macauley, Jon McCammond, Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.

M. Newman and D. Shanks, On a sequence arising in series for pi, Math. Comp., 42 (1984), 199-217 (see Eq. 29).

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Z. Skupien, Sparse Hamiltonian 2-decompositions together with exact count of numerous Hamilton cycles, Discr. Math., 309 (2009), 6382-6390. - N. J. A. Sloane, Feb 12 2010

Index entries for linear recurrences with constant coefficients, signature (1,0,1).

FORMULA

G.f.: x*(1+3*x^2)/(1-x-x^3).

a(n) = trace of successive powers of matrix ({{0,0,1},{1,0,0},{0,1,1}})^n. - Artur Jasinski, Jan 10 2007

a(n) = A000930(n)+3*A000930(n-2). - R. J. Mathar, Nov 16 2007

Logarithmic derivative of Narayana's cows sequence A000930. - Paul D. Hanna, Oct 28 2012

a(n) = w1^n+w2^n+w3^n, where w1,w2,w3 are the roots of the cubic: (-1-x^2+x^3). - Gerry Martens, Jun 27 2015

EXAMPLE

G.f. = x + x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 10*x^6 + 15*x^7 + 21*x^8 + ...

MAPLE

A001609:=-(1+3*z**2)/(-1+z+z**3); # Simon Plouffe in his 1992 dissertation

f:= gfun:-rectoproc({a(n) = a(n-1) + a(n-3), a(1)=1, a(2)=1, a(3)=4}, a(n), remember):

map(f, [$1..100]); # Robert Israel, Jun 29 2015

MATHEMATICA

Table[Tr[MatrixPower[{{0, 0, 1}, {1, 0, 0}, {0, 1, 1}}, n]], {n, 1, 60}] (* Artur Jasinski, Jan 10 2007 *)

Table[ HypergeometricPFQ[{1/3 - n/3, 2/3 - n/3, -(n/3)}, {1/2 - n/2, 1 - n/2}, -(27/4)], {n, 20}] (* Alexander R. Povolotsky, Nov 21 2008 *)

a[1] = a[2] = 1; a[3] = 4; m = 3; a[n_] := 1 + n*Sum [Binomial [n - 1 - (m - 1)*i, i - 1]/i, {i, n/m}] A001609 = Table[a[n], {n, 100}] (* Zak Seidov, Nov 21 2008 *)

LinearRecurrence[{1, 0, 1}, {1, 1, 4}, 50] (* Vincenzo Librandi, Jun 28 2015 *)

PROG

(PARI) {a(n) = if( n<1, n=-n; polcoeff( (3 + x^2) / (1 + x^2 - x^3) + x * O(x^n), n), polcoeff( x * (1 + 3*x^2) / (1 - x - x^3) + x * O(x^n), n))}; /* Michael Somos, Aug 15 2016 */

(MAGMA) I:=[1, 1, 4]; [n le 3 select I[n] else Self(n-1)+Self(n-3): n in [1..45]]; // Vincenzo Librandi, Jun 28 2015

CROSSREFS

Cf. A000204, A014097, A000079, A003269, A003520, A005708, A005709, A005710, A000930, A218439.

Sequence in context: A114439 A271146 A079257 * A101590 A057916 A249853

Adjacent sequences:  A001606 A001607 A001608 * A001610 A001611 A001612

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000

More terms from Michael Somos, Oct 03 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 27 16:49 EDT 2017. Contains 287207 sequences.