A005709 -id:A005709 - cp's OEIS frontend

A000204 Lucas numbers (beginning with 1): L(n) = L(n-1) + L(n-2) with L(1) = 1, L(2) = 3.

1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324

Offset: 1

N. J. A. Sloane

See A000032 for the version beginning 2, 1, 3, 4, 7, ...
Also called Schoute's accessory series (see Jean, 1984). - N. J. A. Sloane, Jun 08 2011
L(n) is the number of matchings in a cycle on n vertices: L(4)=7 because the matchings in a square with edges a, b, c, d (labeled consecutively) are the empty set, a, b, c, d, ac and bd. - Emeric Deutsch, Jun 18 2001
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_{i=1..n/m} binomial(n - 1 - (m - 1)*i, i - 1)/i. 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.
L(n) is the number of points of period n in the golden mean shift. The number of orbits of length n in the golden mean shift is given by the n-th term of the sequence A006206. - Thomas Ward, Mar 13 2001
Row sums of A029635 are 1, 1, 3, 4, 7, ... - Paul Barry, Jan 30 2005
a(n) counts circular n-bit strings with no repeated 1's. E.g., for a(5): 00000 00001 00010 00100 00101 01000 01001 01010 10000 10010 10100. Note #{0...} = fib(n+1), #{1...} = fib(n-1), #{000..., 001..., 100...} = a(n-1), #{010..., 101...} = a(n-2). - Len Smiley, Oct 14 2001
Row sums of the triangle in A182579. - Reinhard Zumkeller, May 07 2012
If p is prime then L(p) == 1 (mod p). L(2^k) == -1 (mod 2^(k+1)) for k = 0,1,2,... - Thomas Ordowski, Sep 25 2013
Satisfies Benford's law [Brown-Duncan, 1970; Berger-Hill, 2017]. - N. J. A. Sloane, Feb 08 2017

			G.f. = x + 3*x^2 + 4*x^3 + 7*x^4 + 11*x^5 + 18*x^6 + 29*x^7 + 47*x^8 + ...

P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 69.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 46.
Leonhard Euler, Introductio in analysin infinitorum (1748), sections 216 and 229.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 148.
Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
V. E. Hoggatt, Jr., Fibonacci and Lucas Numbers. Houghton, Boston, MA, 1969.
R. V. Jean, Mathematical Approach to Pattern and Form in Plant Growth, Wiley, 1984. See p. 5. - N. J. A. Sloane, Jun 08 2011
Thomas Koshy, "Fibonacci and Lucas Numbers with Applications", John Wiley and Sons, 2001.
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).
S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.

Indranil Ghosh, Table of n, a(n) for n = 1..4780 (terms 1..500 computed by N. J. A. Sloane)
Mohammad K. Azarian, Identities Involving Lucas or Fibonacci and Lucas Numbers as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 45, 2012, pp. 2221-2227.
Arno Berger and Theodore P. Hill, What is Benford's Law?, Notices, Amer. Math. Soc., 64:2 (2017), 132-134.
J. Brown and R. L. Duncan, Modulo one uniform distribution of the sequence of logarithms of certain recursive sequences, Fibonacci Quarterly 8 (1970) 482-486.
Enrico Di Cera and Yong Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, Integer Sequences and Periodic Points, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3
Sergio Falcon, On The Generating Functions of the Powers of the K-Fibonacci Numbers, Scholars Journal of Engineering and Technology (SJET), 2014; 2 (4C):669-675.
Scott Garrabrant and Igor Pak, Counting with irrational tiles, arXiv:1407.8222 [math.CO], 2014.
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
Sarah H. Holliday and Takao Komatsu, On the Sum of Reciprocal Generalized Fibonacci Numbers, Integers. Volume 11, Issue 4, Pages 441-455.
R. Jovanovic, First 70 Lucas numbers
Blair Kelly, Factorizations of Lucas numbers
Tanya Khovanova, Recursive Sequences
Clark Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.
Ron Knott, The Lucas Numbers in Pascal's Triangle.
Kantaphon Kuhapatanakul, On the Sums of Reciprocal Generalized Fibonacci Numbers, J. Int. Seq. 16 (2013) #13.7.1.
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 59-67. [Annotated and corrected scanned copy]
Edouard Lucas, The Theory of Simply Periodic Numerical Functions, Fibonacci Association, 1969. English translation of article "Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184-240.
Mathilde Noual, Dynamics in parallel of double Boolean automata circuits, arXiv:1011.3930 [cs.DM], 2010. - _N. J. A. Sloane_, Jul 07 2012
Mathilde Noual, Dynamics of Circuits and Intersecting Circuits, in Language and Automata Theory and Applications, Lecture Notes in Computer Science, 2012, Volume 7183/2012, 433-444. - _N. J. A. Sloane_, Jul 07 2012
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Yash Puri and Thomas Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quarterly, Volume 39, Number 5 (November 2001), pp. 398-402.
Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake, arXiv preprint arXiv:1212.1368 [cs.DM], 2012.
José L. Ramírez and Gustavo N. Rubiano, Properties and Generalizations of the Fibonacci Word Fractal, The Mathematica Journal, Vol. 16 (2014).
Mark A. Shattuck and Carl G. Wagner, Periodicity and Parity Theorems for a Statistic on r-Mino Arrangements, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.6.
N. J. A. Sloane, Illustration of initial terms: the Lucas tree
Zdzisław Skupień, Sums of Powered Characteristic Roots Count Distance-Independent Circular Sets, Discussiones Mathematicae Graph Theory. Volume 33, Issue 1, Pages 217-229, ISSN (Print) 2083-5892, DOI: 10.7151/dmgt.1658, April 2013.
Eric Weisstein's World of Mathematics, Lucas Number
Eric Weisstein's World of Mathematics, Lucas n-Step Number
Richard J. Yanco, Letter and Email to N. J. A. Sloane, 1994
Index entries for "core" sequences
Index entries for linear recurrences with constant coefficients, signature (1,1).
Index entries for sequences related to Benford's law

Cf. A000032, A000045, A061084, A027960, A001609, A014097, A000079, A003269, A003520, A005708, A005709, A005710, A006206, A101033, A101032, A100492, A099731, A094216, A094638, A000108, A090946 (complement).

a000204 n = a000204_list !! n
a000204_list = 1 : 3 : zipWith (+) a000204_list (tail a000204_list)
-- Reinhard Zumkeller, Dec 18 2011

[Lucas(n): n in [1..30]]; // G. C. Greubel, Dec 17 2017

A000204 := proc(n) option remember; if n <=2 then 2*n-1; else procname(n-1)+procname(n-2); fi; end;
with(combinat): A000204 := n->fibonacci(n+1)+fibonacci(n-1);
# alternative Maple program:
L:= n-> (<<1|1>, <1|0>>^n. <<2, -1>>)[1, 1]:
seq(L(n), n=1..50);  # Alois P. Heinz, Jul 25 2008
# Alternative:
a := n -> `if`(n=1, 1, `if`(n=2, 3, hypergeom([(1-n)/2, -n/2], [1-n], -4))):
seq(simplify(a(n)), n=1..39); # Peter Luschny, Sep 03 2019

c = (1 + Sqrt[5])/2; Table[Expand[c^n + (1 - c)^n], {n, 30}] (* Artur Jasinski, Oct 05 2008 *)
Table[LucasL[n, 1], {n, 36}] (* Zerinvary Lajos, Jul 09 2009 *)
LinearRecurrence[{1, 1},{1, 3}, 50] (* Sture Sjöstedt, Nov 28 2011 *)
lukeNum[n_] := If[n < 1, 0, LucasL[n]]; (* Michael Somos, May 18 2015 *)
lukeNum[n_] := SeriesCoefficient[x D[Log[1 / (1 - x - x^2)], x], {x, 0, n}]; (* Michael Somos, May 18 2015 *)

A000204(n)=fibonacci(n+1)+fibonacci(n-1) \\ Michael B. Porter, Nov 05 2009

from functools import cache
@cache
def a(n): return [1, 3][n-1] if n < 3 else a(n-1) + a(n-2)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Nov 13 2022

[(i:=-1)+(j:=2)] + [(j:=i+j)+(i:=j-i) for  in range(100)] # _Jwalin Bhatt, Apr 02 2025

def A000204():
    x, y = 1, 2
    while true:
       yield x
       x, y = x + y, x
a = A000204(); print([next(a) for i in range(39)])  # Peter Luschny, Dec 17 2015

def lucas(n: BigInt): BigInt = {
  val zero = BigInt(0)
  def fibTail(n: BigInt, a: BigInt, b: BigInt): BigInt = n match {
    case `zero` => a
    case _ => fibTail(n - 1, b, a + b)
  }
  fibTail(n, 2, 1)
}
(1 to 50).map(lucas()) // _Alonso del Arte, Oct 20 2019

Expansion of x(1 + 2x)/(1 - x - x^2). - Simon Plouffe, dissertation 1992; multiplied by x. - R. J. Mathar, Nov 14 2007
a(n) = A000045(2n)/A000045(n). - Benoit Cloitre, Jan 05 2003
For n > 1, L(n) = F(n + 2) - F(n - 2), where F(n) is the n-th Fibonacci number (A000045). - Gerald McGarvey, Jul 10 2004
a(n+1) = 4*A054886(n+3) - A022388(n) - 2*A022120(n+1) (a conjecture; note that the above sequences have different offsets). - Creighton Dement, Nov 27 2004
a(n) = Sum_{k=0..floor((n+1)/2)} (n+1)*binomial(n - k + 1, k)/(n - k + 1). - Paul Barry, Jan 30 2005
L(n) = A000045(n+3) - 2*A000045(n). - Creighton Dement, Oct 07 2005
L(n) = A000045(n+1) + A000045(n-1). - John Blythe Dobson, Sep 29 2007
a(n) = 2*Fibonacci(n-1) + Fibonacci(n), n >= 1. - Zerinvary Lajos, Oct 05 2007
L(n) is the term (1, 1) in the 1 X 2 matrix [2, -1].[1, 1; 1, 0]^n. - Alois P. Heinz, Jul 25 2008
a(n) = phi^n + (1 - phi)^n = phi^n + (-phi)^(-n) = ((1 + sqrt(5))^n + (1 - sqrt(5))^n)/(2^n) where phi is the golden ratio (A001622). - Artur Jasinski, Oct 05 2008
a(n) = A014217(n+1) - A014217(n-1). See A153263. - Paul Curtz, Dec 22 2008
a(n) = ((1 + sqrt(5))^n - (1 - sqrt(5))^n)/(2^n*sqrt(5)) + ((1 + sqrt(5))^(n - 1) - (1 - sqrt(5))^(n - 1))/(2^(n - 2)*sqrt(5)). - Al Hakanson (hawkuu(AT)gmail.com), Jan 12 2009, Jan 14 2009
From Hieronymus Fischer, Oct 20 2010 (Start)
Continued fraction for n odd: [L(n); L(n), L(n), ...] = L(n) + fract(Fib(n) * phi).
Continued fraction for n even: [L(n); -L(n), L(n), -L(n), L(n), ...] = L(n) - 1 + fract(Fib(n)*phi). Also: [L(n) - 2; 1, L(n) - 2, 1, L(n) - 2, ...] = L(n) - 2 + fract(Fib(n)*phi). (End)
INVERT transform of (1, 2, -1, -2, 1, 2, ...). - Gary W. Adamson, Mar 07 2012
L(2n - 1) = floor(phi^(2n - 1)); L(2n) = ceiling(phi^(2n)). - Thomas Ordowski, Jun 15 2012
a(n) = hypergeom([(1 - n)/2, -n/2], [1 - n], -4) for n >= 3. - Peter Luschny, Sep 03 2019
E.g.f.: 2*(exp(x/2)*cosh(sqrt(5)*x/2) - 1). - Stefano Spezia, Jul 26 2022

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

Plouffe Maple line edited by N. J. A. Sloane, May 13 2008

A000930 Narayana's cows sequence: a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n-1) + a(n-3).

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491, 183916, 269542, 395033, 578949, 848491, 1243524, 1822473, 2670964, 3914488, 5736961, 8407925

Offset: 0

N. J. A. Sloane

Named after a 14th-century Indian mathematician. [The sequence first appeared in the book "Ganita Kaumudi" (1356) by the Indian mathematician Narayana Pandita (c. 1340 - c. 1400). - Amiram Eldar, Apr 15 2021]
Number of compositions of n into parts 1 and 3. - Joerg Arndt, Jun 25 2011
A Lamé sequence of higher order.
Could have begun 1,0,0,1,1,1,2,3,4,6,9,... (A078012) but that would spoil many nice properties.
Number of tilings of a 3 X n rectangle with straight trominoes.
Number of ways to arrange n-1 tatami mats in a 2 X (n-1) room such that no 4 meet at a point. For example, there are 6 ways to cover a 2 X 5 room, described by 11111, 2111, 1211, 1121, 1112, 212.
Equivalently, number of compositions (ordered partitions) of n-1 into parts 1 and 2 with no two 2's adjacent. E.g., there are 6 such ways to partition 5, namely 11111, 2111, 1211, 1121, 1112, 212, so a(6) = 6. [Minor edit by Keyang Li, Oct 10 2020]
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 = 0...m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..floor(n/m)} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
a(n+2) is the number of n-bit 0-1 sequences that avoid both 00 and 010. - David Callan, Mar 25 2004 [This can easily be proved by the Cluster Method - see for example the Noonan-Zeilberger article. - N. J. A. Sloane, Aug 29 2013]
a(n-4) is the number of n-bit sequences that start and end with 0 but avoid both 00 and 010. For n >= 6, such a sequence necessarily starts 011 and ends 110; deleting these 6 bits is a bijection to the preceding item. - David Callan, Mar 25 2004
Also number of compositions of n+1 into parts congruent to 1 mod m. Here m=3, A003269 for m=4, etc. - Vladeta Jovovic, Feb 09 2005
Row sums of Riordan array (1/(1-x^3), x/(1-x^3)). - Paul Barry, Feb 25 2005
Row sums of Riordan array (1,x(1+x^2)). - Paul Barry, Jan 12 2006
Starting with offset 1 = row sums of triangle A145580. - Gary W. Adamson, Oct 13 2008
Number of digits in A061582. - Dmitry Kamenetsky, Jan 17 2009
From Jon Perry, Nov 15 2010: (Start)
The family a(n) = a(n-1) + a(n-m) with a(n)=1 for n=0..m-1 can be generated by considering the sums (A102547):
1 1 1 1 1 1 1 1 1  1  1  1  1
      1 2 3 4 5 6  7  8  9  10
            1 3 6  10 15 21 28
                   1  4  10 20
                            1
------------------------------
1 1 1 2 3 4 6 9 13 19 28 41 60
with (in this case 3) leading zeros added to each row.
(End)
Number of pairs of rabbits existing at period n generated by 1 pair. All pairs become fertile after 3 periods and generate thereafter a new pair at all following periods. - Carmine Suriano, Mar 20 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=3, 2*a(n-3) equals the number of 2-colored compositions of n with all parts >= 3, such that no adjacent parts have the same color. - Milan Janjic, Nov 27 2011
For n>=2, row sums of Pascal's triangle (A007318) with triplicated diagonals. - Vladimir Shevelev, Apr 12 2012
Pisano period lengths of the sequence read mod m, m >= 1: 1, 7, 8, 14, 31, 56, 57, 28, 24, 217, 60, 56, 168, ... (A271953) If m=3, for example, the remainder sequence becomes 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, ... with a period of length 8. - R. J. Mathar, Oct 18 2012
Diagonal sums of triangle A011973. - John Molokach, Jul 06 2013
"In how many ways can a kangaroo jump through all points of the integer interval [1,n+1] starting at 1 and ending at n+1, while making hops that are restricted to {-1,1,2}? (The OGF is the rational function 1/(1 - z - z^3) corresponding to A000930.)" [Flajolet and Sedgewick, p. 373] - N. J. A. Sloane, Aug 29 2013
a(n) is the number of length n binary words in which the length of every maximal run of consecutive 0's is a multiple of 3. a(5) = 4 because we have: 00011, 10001, 11000, 11111. - Geoffrey Critzer, Jan 07 2014
a(n) is the top left entry of the n-th power of the 3X3 matrix [1, 0, 1; 1, 0, 0; 0, 1, 0] or of the 3 X 3 matrix [1, 1, 0; 0, 0, 1; 1, 0, 0]. - R. J. Mathar, Feb 03 2014
a(n-3) is the top left entry of the n-th power of any of the 3 X 3 matrices [0, 1, 0; 0, 1, 1; 1, 0, 0], [0, 0, 1; 1, 1, 0; 0, 1, 0], [0, 1, 0; 0, 0, 1; 1, 0, 1] or [0, 0, 1; 1, 0, 0; 0, 1, 1]. - R. J. Mathar, Feb 03 2014
Counts closed walks of length (n+3) on a unidirectional triangle, containing a loop at one of remaining vertices. - David Neil McGrath, Sep 15 2014
a(n+2) equals the number of binary words of length n, having at least two zeros between every two successive ones. - Milan Janjic, Feb 07 2015
a(n+1)/a(n) tends to x = 1.465571... (decimal expansion given in A092526) in the limit n -> infinity. This is the real solution of x^3 - x^2 -1 = 0. See also the formula by Benoit Cloitre, Nov 30 2002. - Wolfdieter Lang, Apr 24 2015
a(n+2) equals the number of subsets of {1,2,..,n} in which any two elements differ by at least 3. - Robert FERREOL, Feb 17 2016
Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*. Let g(n) be the set of nodes in the n-th generation, so that g(0) = {0}, g(1) = {1}, g(2) = {2,x}, g(3) = {3,2x,x+1,x^2}, etc. Let T(r) be the tree obtained by substituting r for x. If a positive integer N such that r = N^(1/3) is not an integer, then the number of (not necessarily distinct) integers in g(n) is A000930(n), for n >= 1. (See A274142.) - Clark Kimberling, Jun 13 2016
a(n-3) is the number of compositions of n excluding 1 and 2, n >= 3. - Gregory L. Simay, Jul 12 2016
Antidiagonal sums of array A277627. - Paul Curtz, May 16 2019
a(n+1) is the number of multus bitstrings of length n with no runs of 3 ones. - Steven Finch, Mar 25 2020
Suppose we have a(n) samples, exactly one of which is positive. Assume the cost for testing a mix of k samples is 3 if one of the samples is positive (but you will not know which sample was positive if you test more than 1) and 1 if none of the samples is positive. Then the cheapest strategy for finding the positive sample is to have a(n-3) undergo the first test and then continue with testing either a(n-4) if none were positive or with a(n-6) otherwise. The total cost of the tests will be n. - Ruediger Jehn, Dec 24 2020

			The number of compositions of 11 without any 1's and 2's is a(11-3) = a(8) = 13. The compositions are (11), (8,3), (3,8), (7,4), (4,7), (6,5), (5,6), (5,3,3), (3,5,3), (3,3,5), (4,4,3), (4,3,4), (3,4,4). - _Gregory L. Simay_, Jul 12 2016
The compositions from the above example may be mapped to the a(8) compositions of 8 into 1's and 3's using this (more generally applicable) method: replace all numbers greater than 3 with a 3 followed by 1's to make the same total, then remove the initial 3 from the composition. Maintaining the example's order, they become (1,1,1,1,1,1,1,1), (1,1,1,1,1,3), (3,1,1,1,1,1), (1,1,1,1,3,1), (1,3,1,1,1,1), (1,1,1,3,1,1), (1,1,3,1,1,1), (1,1,3,3), (3,1,1,3), (3,3,1,1), (1,3,1,3), (1,3,3,1), (3,1,3,1). - _Peter Munn_, May 31 2017

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, id. 8,80.
R. K. Guy, "Anyone for Twopins?" in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [See p. 12, line 3]
H. Langman, Play Mathematics. Hafner, NY, 1962, p. 13.
David Sankoff and Lani Haque, Power Boosts for Cluster Tests, in Comparative Genomics, Lecture Notes in Computer Science, Volume 3678/2005, Springer-Verlag. - N. J. A. Sloane, Jul 09 2009
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).

Harvey P. Dale and T. D. Noe, Table of n, a(n) for n = 0..5000 [The first 500 terms were computed by T. D. Noe]
Gene Abrams, Stefan Erickson, and Cristóbal Gil Canto, Leavitt path algebras of Cayley graphs C_n^j, arXiv:1712.06480 [math.RA], 2017.
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [The hal link does not always work. - _N. J. A. Sloane_, Feb 19 2025]
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [Local copy with annotations and a correction from _N. J. A. Sloane_, Feb 19 2025]
I. Amburg, K. Dasaratha, L. Flapan, T. Garrity, C. Lee, C. Mihailak, N. Neumann-Chun, S. Peluse, and M. Stoffregen, Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences, arXiv:1509.05239v1 [math.CO] Sep 17 2015. See Conjecture 5.8.
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
Bruce M. Boman, Geometric Capitulum Patterns Based on Fibonacci p-Proportions, Fibonacci Quart. 58 (2020), no. 5, 91-102.
Bruce M. Boman, Thien-Nam Dinh, Keith Decker, Brooks Emerick, Christopher Raymond, and Gilberto Schleinger, Why do Fibonacci numbers appear in patterns of growth in nature?, in Fibonacci Quarterly, 55(5): pp 30-41, (2017).
Eric Fernando Bravo, On concatenations of Padovan and Perrin numbers, Math. Commun. (2023) Vol 28, 105-119.
Russ Chamberlain, Sam Ginsburg and Chi Zhang, Generating Functions and Wilf-equivalence on Theta_k-embeddings, University of Wisconsin, April 2012.
Eunice Y. S. Chan, A comparison of solution methods for Mandelbrot-like polynomials, MS Thesis, 2016, University of Western Ontario; Electronic Thesis and Dissertation Repository. 4028.
Eunice Y. S. Chan, Algebraic Companions and Linearizations, The University of Western Ontario (Canada, 2019) Electronic Thesis and Dissertation Repository. 6414.
Eunice Y. S. Chan and Robert Corless, A new kind of companion matrix, Electronic Journal of Linear Algebra, Volume 32, Article 25, 2017, see p. 339.
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
Hùng Việt Chu, Various sequences from counting subsets, version 2, June 2021.
Johann Cigler, Some remarks on generalized Fibonacci and Lucas polynomials, arXiv:1912.06651 [math.CO], 2019.
Tony Crilly, A supergolden rectangle, The Mathematical Gazette 78, No. 483 (1994): 320-325. See page 234.
Tony Crilly, Narayana's integer sequence revisited, Math. Gaz. (2024) Vol. 108, Issue 572, 262-269.
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
James East and Nicholas Ham, Lattice paths and submonoids of Z^2, arXiv:1811.05735 [math.CO], 2018.
Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Catalan-Spitzer permutations, arXiv:2310.06288 [math.CO], 2023. See p. 11.
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012. - _N. J. A. Sloane_, Jun 10 2012
M. Feinberg, New slants, Fib. Quart. 2 (1964), 223-227.
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 373.
Lukas Fleischer and Jeffrey Shallit, Words With Few Palindromes, Revisited, arXiv:1911.12464 [cs.FL], 2019.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
Philip Gibbs and Judson McCranie, The Ulam Numbers up to One Trillion, (2017).
Maria M. Gillespie, Kenneth G. Monks, and Kenneth M. Monks, Enumerating Anchored Permutations with Bounded Gaps, arXiv:1808.03573 [math.CO], 2018.
Taras Goy, On identities with multinomial coefficients for Fibonacci-Narayana sequence, Annales Mathematicae et Informaticae (2018) 49, Eszterházy Károly University Institute of Mathematics and Informatics, 75-84.
T. M. Green, Recurrent sequences and Pascal's triangle, Math. Mag., 41 (1968), 13-21.
Russelle Guadalupe, On the 3-adic valuation of the Narayana numbers, arXiv:2112.06187 [math.NT], 2021.
R. K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]
R. K. Guy, The strong law of small numbers, Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,2,1).
W. R. Heinson, Simulation studies on shape and growth kinetics for fractal aggregates in aerosol and colloidal systems, PhD Dissertation, Kansas State Univ., Manhattan, Kansas, 2015; see page 49.
J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 14
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 376
Milan Janjic, Recurrence Relations and Determinants, arXiv preprint arXiv:1112.2466 [math.CO], 2011.
Milan Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5.
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 91.
Tom Johnson, Illustrated Music #8, Narayana's Cows
B. Keszegh, N Lemons and D. Palvolgyi, Online and quasi-online colorings of wedges and intervals, arXiv preprint arXiv:1207.4415 [math.CO], 2012-2015.
K. Kirthi, Narayana Sequences for Cryptographic Applications, arXiv preprint arXiv:1509.05745 [math.NT], 2015.
Martin Küttler, Maksym Planeta, Jan Bierbaum, Carsten Weinhold, Hermann Härtig, Amnon Barak, and Torsten Hoefler, Corrected trees for reliable group communication, Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming (PPoPP 2019), 287-299.
Steven Linton, James Propp, Tom Roby, and Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.
K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.
T. Mansour and M. Shattuck, Polynomials whose coefficients are generalized Tribonacci numbers, Applied Mathematics and Computation, Volume 219, Issue 15, Apr 01 2013, Pages 8366-8374.
T. Mansour and M. Shattuck, A monotonicity property for generalized Fibonacci sequences, arXiv preprint arXiv:1410.6943 [math.CO], 2014.
R. J. Mathar, Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 17.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO] (2016), Section 4.2.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.8.3.
J. Noonan and D. Zeilberger, The Goulden-Jackson Cluster Method: Extensions, Applications and Implementations, arXiv:math/9806036 [math.CO], Jun 08 1998.
Antonio M. Oller-Marcén, The Dying Rabbit Problem Revisited, INTEGERS, 9 (2009), 129-138.
Pagdame Tiebekabe and Kouèssi Norbert Adédji, Narayana's cows numbers which are concatenations of three repdigits in base Rho, arXiv:2304.00773 [math.NT], 2023.
Dömötör Pálvölgyi, Coloring Geometric Hypergraphs, Ph. D. Dissertation, Hungarian Acad. Sci. (Hungary, 2023). See p. 35.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Abhishek Raj, Vadim Oganesyan, and Antonello Scardicchio, A kinetically constrained model exhibiting non-linear diffusion and jamming, arXiv:2412.05231 [cond-mat.stat-mech], 2024. See p. 8.
Narad Rampersad and Max Wiebe, Sums of products of binomial coefficients mod 2 and 2-regular sequences, Integers (2024) Vol. 24, Art. No. A73. See p. 9.
M. Randic, D. Morales, and O. Araujo, Higher-order Lucas numbers, Divulgaciones Matematicas 6:2 (2008), pp. 275-283.
Frank Ruskey and Jennifer Woodcock, Counting Fixed-Height Tatami Tilings, Electronic Journal of Combinatorics, Paper R126 (2009), 20 pages.
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.
T. Sillke, The binary form of Conway's Sequence
Parmanand Singh, The Ganita Kaumudi of Narayana Pandita, Ganita-Bharati, Vol. 20, No. 1-4 (1998), pp. 25-82. See pp. 79-80.
Z. Skupien, Sparse Hamiltonian 2-decompositions together with exact count of numerous Hamiltonian cycles, Discr. Math., 309 (2009), 6382-6390. - _N. J. A. Sloane_, Feb 12 2010
Yüksel Soykan, On Generalized co-Narayana Numbers, Earthline Journal of Mathematical Sciences, 15(4), 605-638, (2025). See p. 607.
Krzysztof Strasburger, The order of three lowest-energy states of the six-electron harmonium at small force constant, The Journal of Chemical Physics 144, 234304 (2016).
Krzysztof Strasburger, Explicitly correlated wavefunctions of the ground state and the lowest 5-tuple state of the carbon atom, arXiv:1903.06051 [physics.chem-ph], 2019.
Krzysztof Strasburger, Energy difference between the lowest doublet and quartet states of the boron atom, arXiv:2009.08723 [physics.chem-ph], 2020.
Liam Taylor-West, Modularity, technology, and geometry in compositional practice: a portfolio of original compositions, D. mus. dissertation, Royal College of Music (London, England 2023), p. 56.
Eric Weisstein's World of Mathematics, Narayana Cow Sequence.
E. Wilson, The Scales of Mt. Meru
Index entries for linear recurrences with constant coefficients, signature (1,0,1).

For Lamé sequences of orders 1 through 9 see A000045, this sequence, and A017898 - A017904.
Cf. A000073, A000213, A048715, A069241, A092526, A170954.
See also A000079, A003269, A003520, A005708, A005709, A005710.
Essentially the same as A068921 and A078012.
See also A001609, A145580, A179070, A214551 (same rule except divide by GCD).
A271901 and A271953 give the period of this sequence mod n.
Cf. A007318, A060576, A102547, A277627, A289207.
A120562 has the same recurrence for odd n.

a:=[1,1,1];; for n in [4..50] do a[n]:=a[n-1]+a[n-3]; od; a; # Muniru A Asiru, Aug 13 2018

a000930 n = a000930_list !! n
a000930_list = 1 : 1 : 1 : zipWith (+) a000930_list (drop 2 a000930_list)
-- Reinhard Zumkeller, Sep 25 2011

[1,1] cat [ n le 3 select n else Self(n-1)+Self(n-3): n in [1..50] ]; // Vincenzo Librandi, Apr 25 2015

f := proc(r) local t1,i; t1 := []; for i from 1 to r do t1 := [op(t1),0]; od: for i from 1 to r+1 do t1 := [op(t1),1]; od: for i from 2*r+2 to 50 do t1 := [op(t1),t1[i-1]+t1[i-1-r]]; od: t1; end; # set r = order
with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 2)}, unlabeled]: seq(count(SeqSetU, size=j), j=3..40); # Zerinvary Lajos, Oct 10 2006
A000930 := proc(n)
    add(binomial(n-2*k,k),k=0..floor(n/3)) ;
end proc: # Zerinvary Lajos, Apr 03 2007
a:= n-> (<<1|1|0>, <0|0|1>, <1|0|0>>^n)[1,1]:
seq(a(n), n=0..50); # Alois P. Heinz, Jun 20 2008

a[0] = 1; a[1] = a[2] = 1; a[n_] := a[n] = a[n - 1] + a[n - 3]; Table[ a[n], {n, 0, 40} ]
CoefficientList[Series[1/(1 - x - x^3), {x, 0, 45}], x] (* Zerinvary Lajos, Mar 22 2007 *)
LinearRecurrence[{1, 0, 1}, {1, 1, 1}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 11 2012 *)
a[n_] := HypergeometricPFQ[{(1 - n)/3, (2 - n)/3, -n/3}, {(1 - n)/ 2, -n/2}, -27/4]; Table[a[n], {n, 0, 43}] (* Jean-François Alcover, Feb 26 2013 *)
Table[-RootSum[1 + #^2 - #^3 &, 3 #^(n + 2) - 11 #^(n + 3) + 2 #^(n + 4) &]/31, {n, 20}] (* Eric W. Weisstein, Feb 14 2025 *)

makelist(sum(binomial(n-2*k,k),k,0,n/3),n,0,18); /* Emanuele Munarini, May 24 2011 */

a(n)=polcoeff(exp(sum(m=1,n,((1+sqrt(1+4*x))^m + (1-sqrt(1+4*x))^m)*(x/2)^m/m)+x*O(x^n)),n) \\ Paul D. Hanna, Oct 08 2009

x='x+O('x^66); Vec(1/(1-(x+x^3))) \\ Joerg Arndt, May 24 2011

a(n)=([0,1,0;0,0,1;1,0,1]^n*[1;1;1])[1,1] \\ Charles R Greathouse IV, Feb 26 2017

from itertools import islice
def A000930_gen(): # generator of terms
    blist = [1]*3
    while True:
        yield blist[0]
        blist = blist[1:]+[blist[0]+blist[2]]
A000930_list = list(islice(A000930_gen(),30)) # Chai Wah Wu, Feb 04 2022

@CachedFunction
def a(n): # A000930
    if (n<3): return 1
    else: return a(n-1) + a(n-3)
[a(n) for n in (0..80)] # G. C. Greubel, Jul 29 2022

G.f.: 1/(1-x-x^3). - Simon Plouffe in his 1992 dissertation
a(n) = Sum_{i=0..floor(n/3)} binomial(n-2*i, i).
a(n) = a(n-2) + a(n-3) + a(n-4) for n>3.
a(n) = floor(d*c^n + 1/2) where c is the real root of x^3-x^2-1 and d is the real root of 31*x^3-31*x^2+9*x-1 (c = 1.465571... = A092526 and d = 0.611491991950812...). - Benoit Cloitre, Nov 30 2002
a(n) = Sum_{k=0..n} binomial(floor((n+2k-2)/3), k). - Paul Barry, Jul 06 2004
a(n) = Sum_{k=0..n} binomial(k, floor((n-k)/2))(1+(-1)^(n-k))/2. - Paul Barry, Jan 12 2006
a(n) = Sum_{k=0..n} binomial((n+2k)/3,(n-k)/3)*(2*cos(2*Pi*(n-k)/3)+1)/3. - Paul Barry, Dec 15 2006
a(n) = term (1,1) in matrix [1,1,0; 0,0,1; 1,0,0]^n. - Alois P. Heinz, Jun 20 2008
G.f.: exp( Sum_{n>=1} ((1+sqrt(1+4*x))^n + (1-sqrt(1+4*x))^n)*(x/2)^n/n ).
Logarithmic derivative equals A001609. - Paul D. Hanna, Oct 08 2009
a(n) = a(n-1) + a(n-2) - a(n-5) for n>4. - Paul Weisenhorn, Oct 28 2011
For n >= 2, a(2*n-1) = a(2*n-2)+a(2*n-4); a(2*n) = a(2*n-1)+a(2*n-3). - Vladimir Shevelev, Apr 12 2012
INVERT transform of (1,0,0,1,0,0,1,0,0,1,...) = (1, 1, 1, 2, 3, 4, 6, ...); but INVERT transform of (1,0,1,0,0,0,...) = (1, 1, 2, 3, 4, 6, ...). - Gary W. Adamson, Jul 05 2012
G.f.: 1/(G(0)-x) where G(k) = 1 - x^2/(1 - x^2/(x^2 - 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 16 2012
G.f.: 1 + x/(G(0)-x) where G(k) = 1 - x^2*(2*k^2 + 3*k +2) + x^2*(k+1)^2*(1 - x^2*(k^2 + 3*k +2))/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 27 2012
a(2*n) = A002478(n), a(2*n+1) = A141015(n+1), a(3*n) = A052544(n), a(3*n+1) = A124820(n), a(3*n+2) = A052529(n+1). - Johannes W. Meijer, Jul 21 2013, corrected by Greg Dresden, Jul 06 2020
G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + x^2)/( x*(4*k+3 + x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 08 2013
a(n) = v1*w1^n+v3*w2^n+v2*w3^n, where v1,2,3 are the roots of (-1+9*x-31*x^2+31*x^3): [v1=0.6114919920, v2=0.1942540040 - 0.1225496913*I, v3=conjugate(v2)] and w1,2,3 are the roots of (-1-x^2+x^3): [w1=1.4655712319, w2=-0.2327856159 - 0.7925519925*I, w3=conjugate(w2)]. - Gerry Martens, Jun 27 2015
a(n) = (6*A001609(n+3) + A001609(n-7))/31 for n>=7. - Areebah Mahdia, Jun 07 2020
a(n+6)^2 + a(n+1)^2 + a(n)^2 = a(n+5)^2 + a(n+4)^2 + 3*a(n+3)^2 + a(n+2)^2. - Greg Dresden, Jul 07 2021
a(n) = Sum_{i=(n-7)..(n-1)} a(i) / 2. - Jules Beauchamp, May 10 2025

Name expanded by N. J. A. Sloane, Sep 07 2012

A003269 a(n) = a(n-1) + a(n-4) with a(0) = 0, a(1) = a(2) = a(3) = 1.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181, 250, 345, 476, 657, 907, 1252, 1728, 2385, 3292, 4544, 6272, 8657, 11949, 16493, 22765, 31422, 43371, 59864, 82629, 114051, 157422, 217286, 299915, 413966, 571388, 788674, 1088589, 1502555, 2073943

Offset: 0

N. J. A. Sloane

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 = 0..m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
For this family of sequences, a(n+1) is the number of compositions of n+1 into parts 1 and m. For n>=m, a(n-m+1)is the number of compositions of n in which each part is greater than m or equivalently, in which parts 1 through m are excluded. - Gregory L. Simay, Jul 14 2016
For this family of sequences, let a(m,n) = a(n-1) + a(n-m). Then the number of compositions of n having m as a least summand is a(m, n-m) - a(m+1, n-m-1). - Gregory L. Simay, Jul 14 2016
For n>=3, a(n-3) = number of compositions of n in which each part is >=4. - Milan Janjic, Jun 28 2010
For n>=1, number of compositions of n into parts == 1 (mod 4). Example: a(8)=5 because there are 5 compositions of 8 into parts 1 or 5: (1,1,1,1,1,1,1,1), (1,1,1,5), (1,1,5,1), (1,5,1,1), (5,1,1,1). - Adi Dani, Jun 16 2011
a(n+1) is the number of compositions of n into parts 1 and 4. - Joerg Arndt, Jun 25 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=4, 2*a(n-3) equals the number of 2-colored compositions of n with all parts >= 4, such that no adjacent parts have the same color. - Milan Janjic, Nov 27 2011
Number of permutations satisfying -k<=p(i)-i<=r and p(i)-i not in I, i=1..n, with k=1, r=3, I={1,2}. - Vladimir Baltic, Mar 07 2012
a(n+4) equals the number of binary words of length n having at least 3 zeros between every two successive ones. - Milan Janjic, Feb 07 2015
From Clark Kimberling, Jun 13 2016: (Start)
Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*.
Let g(n) be the set of nodes in the n-th generation, so that g(0) = {0}, g(1) = {1}, g(2) = {2,x}, g(3) = {3, 2*x, x+1, x^2}, etc.
Let T(r) be the tree obtained by substituting r for x.
If N is a positive integer such that r = N^(1/4) is not an integer, then the number of (not necessarily distinct) integers in g(n) is A003269(n), for n > = 1. See A274142. (End)

			G.f.: x + x^2 + x^3 + x^4 + 2*x^5 + 3*x^6 + 4*x^7 + 5*x^8 + 7*x^9 + 10*x^10 + ...
The number of compositions of 12 having 4 as a least summand is a(4, 12 -4 + 1) - a(5, 12 - 5 + 1) = A003269(9) - A003520(8) = 7-4 = 3. The compositions are (84), (48) and (444). - _Gregory L. Simay_, Jul 14 2016

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 120.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..501
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 18, 22.
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [The hal link does not always work. - _N. J. A. Sloane_, Feb 19 2025]
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [Local copy with annotations and a correction from _N. J. A. Sloane_, Feb 19 2025]
Peter G. Anderson, More Properties of the Zeckendorf Array, Fib. Quart. 52-5 (2014), 15-21. With 2 more initial zeros.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 9.
Bruce M. Boman, Geometric Capitulum Patterns Based on Fibonacci p-Proportions, Fibonacci Quart. 58 (2020), no. 5, 91-102.
Russ Chamberlain, Sam Ginsburg and Chi Zhang, Generating Functions and Wilf-equivalence on Theta_k-embeddings, University of Wisconsin, April 2012.
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
Hùng Việt Chu, Nurettin Irmak, Steven J. Miller, László Szalay, and Sindy Xin Zhang, Schreier Multisets and the s-step Fibonacci Sequences, arXiv:2304.05409 [math.CO], 2023. See also Integers (2024) Vol. 24A, Art. No. A7, p. 3.
Adi Dani, Compositions of natural numbers over arithmetic progressions
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,3,1).
J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.
Brian Hopkins and Hua Wang, Restricted Color n-color Compositions, arXiv:2003.05291 [math.CO], 2020.
Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 377
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.
S. Kitaev, Independent sets on path-schemes, JIS 9 (2006) # 06.2.2 G(x) for M={1,2,3} gives seq. shifted 4 places left
R. J. Mathar, Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 17.
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 [math.CO] (2014), eq. (23).
Flaviano Morone, Ian Leifer, and Hernán A. Makse, Fibration symmetries uncover the building blocks of biological networks, Proceedings of the National Academy of Sciences (2020) Vol. 117, No. 15, 8306-8314.
Augustine O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper No. A60, 10 pp.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.8.3.
Djamila Oudrar and Maurice Pouzet, Ordered structures with no finite monomorphic decomposition. Application to the profile of hereditary classes, arXiv:2312.05913 [math.CO], 2023. See p. 18.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
E. Wilson, The Scales of Mt. Meru
Dominika Závacká, Cristina Dalfó, and Miquel Angel Fiol, Integer sequences from k-iterated line digraphs, CEUR: Proc. 24th Conf. Info. Tech. - Appl. and Theory (ITAT 2024) Vol 3792, 156-161. See p. 161, Table 2.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).

Cf. A000045, A000079, A000930, A003520, A005708, A005709, A005710, A005711, A017898.
Cf. A048718, A072827, A072850, A072851, A072852, A072853, A072854, A072855, A072856.
Cf. A079955 - A080014.
See A017898 for an essentially identical sequence.
Row sums of A180184.

a003269 n = a003269_list !! n
a003269_list = 0 : 1 : 1 : 1 : zipWith (+) a003269_list
                                          (drop 3 a003269_list)
-- Reinhard Zumkeller, Feb 27 2011

I:=[0,1,1,1]; [n le 4 select I[n] else Self(n-1) + Self(n-4) :n in [1..50]]; // Marius A. Burtea, Sep 13 2019

with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 3)}, unlabeled]: seq(count(SeqSetU, size=j), j=4..51);
seq(add(binomial(n-3*k,k),k=0..floor(n/3)),n=0..47); # Zerinvary Lajos, Apr 03 2007
A003269:=z/(1-z-z**4); # Simon Plouffe in his 1992 dissertation
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 3)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=3..50); # Zerinvary Lajos, Mar 26 2008
M:= Matrix(4, (i,j)-> if j=1 then [1,0,0,1][i] elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,2]; seq(a(n), n=0..48); # Alois P. Heinz, Jul 27 2008

a[0]= 0; a[1]= a[2]= a[3]= 1; a[n_]:= a[n]= a[n-1] + a[n-4]; Table[a[n], {n,0,50}]
CoefficientList[Series[x/(1-x-x^4), {x,0,50}], x] (* Zerinvary Lajos, Mar 29 2007 *)
Table[Sum[Binomial[n-3*i-1,i], {i,0,(n-1)/3}], {n,0,50}]
LinearRecurrence[{1,0,0,1}, {0,1,1,1}, 50] (* Robert G. Wilson v, Jul 12 2014 *)
nxt[{a_,b_,c_,d_}]:={b,c,d,a+d}; NestList[nxt,{0,1,1,1},50][[;;,1]] (* Harvey P. Dale, May 27 2024 *)

{a(n) = polcoeff( if( n<0, (1 + x^3) / (1 + x^3 - x^4), 1 / (1 - x - x^4)) + x * O(x^abs(n)), abs(n))} /* Michael Somos, Jul 12 2003 */

@CachedFunction
def a(n): return ((n+2)//3) if (n<4) else a(n-1) + a(n-4) # a = A003269
[a(n) for n in (0..50)] # G. C. Greubel, Jul 25 2022

G.f.: x/(1-x-x^4).
G.f.: -1 + 1/(1-Sum_{k>=0} x^(4*k+1)).
a(n) = a(n-3) + a(n-4) + a(n-5) + a(n-6) for n>4.
a(n) = floor(d*c^n + 1/2) where c is the positive real root of -x^4+x^3+1 and d is the positive real root of 283*x^4-18*x^2-8*x-1 (c=1.38027756909761411... and d=0.3966506381592033124...). - Benoit Cloitre, Nov 30 2002
Equivalently, a(n) = floor(c^(n+3)/(c^4+3) + 1/2) with c as defined above (see A086106). - Greg Dresden and Shuer Jiang, Aug 31 2019
a(n) = term (1,2) in the 4 X 4 matrix [1,1,0,0; 0,0,1,0; 0,0,0,1; 1,0,0,0]^n. - Alois P. Heinz, Jul 27 2008
From Paul Barry, Oct 20 2009: (Start)
a(n+1) = Sum_{k=0..n} C((n+3*k)/4,k)*((1+(-1)^(n-k))/2 + cos(Pi*n/2))/2;
a(n+1) = Sum_{k=0..n} C(k,floor((n-k)/3))(2*cos(2*Pi*(n-k)/3)+1)/3. (End)
a(n) = Sum_{j=0..(n-1)/3} binomial(n-1-3*j,j) (cf. A180184). - Vladimir Kruchinin, May 23 2011
A017817(n) = a(-4 - n) * (-1)^n. - Michael Somos, Jul 12 2003
G.f.: Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(2*k+1 + x^3)/( x*(2*k+2 + x^3) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 29 2013
Appears a(n) = hypergeometric([1/4-n/4,1/2-n/4,3/4-n/4,1-n/4], [1/3-n/3,2/3-n/3,1-n/3], -4^4/3^3) for n>=10. - Peter Luschny, Sep 18 2014

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

Initial 0 prepended by N. J. A. Sloane, Apr 09 2008

A003520 a(n) = a(n-1) + a(n-5); a(0) = ... = a(4) = 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 26, 34, 45, 60, 80, 106, 140, 185, 245, 325, 431, 571, 756, 1001, 1326, 1757, 2328, 3084, 4085, 5411, 7168, 9496, 12580, 16665, 22076, 29244, 38740, 51320, 67985, 90061, 119305, 158045, 209365, 277350, 367411, 486716, 644761

Offset: 0

N. J. A. Sloane

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 = 0..m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
Also counts ordered partitions such that no part is less than 5. For example, a(12) = a(11) + a(7) where a(7) counts 11,6+5 and 5+6 and a(11) counts 15,10+5, 9+6,8+7,7+8,6+9,5+10 and 5+5+5. Thus a(12) = 3 + 8 = 11. a(12) counts 16,11+5,10+6,9+7,8+8,7+9,6+10 and 6+5+5 but also 5+11,5+6+5 and 5+5+6. Similar results hold for the other sequences formed by a(n) = a(n-1) + a(n-k). - Alford Arnold, Aug 06 2003
Number of compositions of n into parts 1 and 5. - Joerg Arndt, Jun 25 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=5, 2*a(n-5) equals the number of 2-colored compositions of n with all parts >= 5, such that no adjacent parts have the same color. - Milan Janjic, Nov 27 2011
a(n+4) equals the number of binary words of length n having at least 4 zeros between every two successive ones. - Milan Janjic, Feb 07 2015
Number of tilings of a 5 X n rectangle with 5 X 1 pentominoes. - M. Poyraz Torcuk, Mar 26 2022

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 119.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..500
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 18, 22.
Roland Bacher, On the number of perfect lattices, arXiv:1704.02234 [math.NT], 2017. See Section 6.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 9.
Bruce M. Boman, Geometric Capitulum Patterns Based on Fibonacci p-Proportions, Fibonacci Quart. 58 (2020), no. 5, 91-102.
Bruce M. Boman, Thien-Nam Dinh, Keith Decker, Brooks Emerick, Christopher Raymond, and Gilberto Schleinger, Why do Fibonacci numbers appear in patterns of growth in nature?, in Fibonacci Quarterly, 55(5): pp 30-41, (2017).
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,4,1).
V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
Brian Hopkins and Hua Wang, Restricted Color n-color Compositions, arXiv:2003.05291 [math.CO], 2020.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 378
S. Kitaev, Independent sets on path-schemes, JIS 9 (2006) # 06.2.2 G(x) for M={1,2,3,4} gives seq. shifted 4 places left
T. G. Lewis, B. J. Smith and M. Z. Smith, Fibonacci sequences and money management, Fib. Quart., 14 (1976), 37-41.
Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.
R. J. Mathar, Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 33.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO] (2016), Section 4.4.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
E. Wilson, The Scales of Mt. Meru
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1)

Apart from initial terms, same as A017899.

Cf. A000045, A000079, A000930, A003269, A005708, A005709, A005710, A005711.

a[0]:=1:a[1]:=1:a[2]:=1:a[3]:=1:a[4]:=1:for n from 5 to 60 do a[n]:=a[n-1]+a[n-5] od:seq(a[n],n=0..60);
with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 4)}, unlabeled]: seq(count(SeqSetU, size=j), j=5..55); # Zerinvary Lajos, Oct 10 2006
A003520:=-1/(z**3+z**2-1)/(z**2-z+1); # Simon Plouffe in his 1992 dissertation
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 4)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=4..54); # Zerinvary Lajos, Mar 26 2008
M := Matrix(5, (i,j)-> if j=1 then [1, 0, 0, 0, 1][i] elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,1]: seq(a(n), n=0..50); # Alois P. Heinz, Jul 27 2008

a[0] = a[1] = a[2] = a[3] = a[4] = 1; a[n_] := a[n] = a[n - 1] + a[n - 5]; Table[ a[n], {n, 0, 49}] (* Robert G. Wilson v, Dec 09 2004 *)
CoefficientList[Series[1/(1 - x - x^5), {x, 0, 51}], x] (* Zerinvary Lajos, Mar 29 2007 *)
LinearRecurrence[{1, 0, 0, 0, 1}, {1, 1, 1, 1, 1}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)
nxt[{a_,b_,c_,d_,e_}]:={b,c,d,e,e+a}; NestList[nxt,{1,1,1,1,1},50][[;;,1]] (* Harvey P. Dale, Sep 27 2023 *)

a(n):=sum(binomial(n-1+(-4)*j,j),j,0,(n-1)/4); /* Vladimir Kruchinin, May 23 2011 */

my(x='x+O('x^66)); Vec(x/(1-(x+x^5))) /* Joerg Arndt, Jun 25 2011 */

G.f.: 1/(1-x-x^5) = 1/((1-x+x^2)(1-x^2-x^3)).
a(n) = Sum_{j=0..(n-1)/4} binomial(n-1+(-4)*j,j).
For n>5, a(n) = floor( d*c^n + 1/2) where c is the positive real root of x^5-x^4-1 and d is the positive real root of 161*x^3-23*x^2-12*x-1 ( c=1.32471795724474602... and d=0.3811571478326847...) - Benoit Cloitre, Nov 30 2002
a(n) = term (1,1) in the 5 X 5 matrix [1,1,0,0,0; 0,0,1,0,0; 0,0,0,1,0; 0,0,0,0,1; 1,0,0,0,0]^n. - Alois P. Heinz, Jul 27 2008
For positive integers n and k such that k <= n <= 5*k, and 4 divides n-k, define c(n,k) = binomial(k,(n-k)/4), and c(n,k)=0, otherwise. Then, for n >= 1,  a(n) = sum(c(n,k), k=1..n). - Milan Janjic, Dec 09 2011
Apparently a(n) = hypergeometric([-1/5*n, 1/5-1/5*n, 2/5-1/5*n, 3/5-1/5*n, 4/5-1/5*n], [-1/4*n, 1/4-1/4*n, 1/2-1/4*n, 3/4-1/4*n], -5^5/4^4) for n>=16. - Peter Luschny, Sep 18 2014
7*a(n) = A117373(n+4) +5*b(n) +4*b(n-1) +b(n-2) where b(n) = A182097(n). - R. J. Mathar, Aug 07 2017

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

A005708 a(n) = a(n-1) + a(n-6), with a(i) = 1 for i = 0..5.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 12, 16, 21, 27, 34, 43, 55, 71, 92, 119, 153, 196, 251, 322, 414, 533, 686, 882, 1133, 1455, 1869, 2402, 3088, 3970, 5103, 6558, 8427, 10829, 13917, 17887, 22990, 29548, 37975, 48804, 62721, 80608, 103598, 133146, 171121, 219925, 282646

Offset: 0

N. J. A. Sloane

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 = 0...m-1. The generating function is 1/(1-x-x^m). Also a(n) = sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
For n>=6, a(n-6) = number of compositions of n in which each part is >=6. - Milan Janjic, Jun 28 2010
Number of compositions of n into parts 1 and 6. - Joerg Arndt, Jun 24 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=6, 2*a(n-6) equals the number of 2-colored compositions of n with all parts >=6, such that no adjacent parts have the same color. - Milan Janjic, Nov 27 2011
a(n+5) equals the number of binary words of length n having at least 5 zeros between every two successive ones. - Milan Janjic, Feb 07 2015
Number of tilings of a 6 X n rectangle with 6 X 1 hexominoes. - M. Poyraz Torcuk, Mar 26 2022

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

T. D. Noe, Table of n, a(n) for n=0..500
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 18, 22.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 10.
Bruce M. Boman, Thien-Nam Dinh, Keith Decker, Brooks Emerick, Christopher Raymond, and Gilberto Schleinger, Why do Fibonacci numbers appear in patterns of growth in nature?, in Fibonacci Quarterly, 55(5): pp 30-41, (2017).
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,5,1).
V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.
S. Kitaev, Independent sets on path-schemes, JIS 9 (2006) # 06.2.2 G(x) for M={1,2,3,4,5} gives seq. shifted 5 places left
D. Kleitman, Solution to Problem E3274, Amer. Math. Monthly, 98 (1991), 958-959.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO] (2016), Section 4.5
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
D. Newman, Problem E3274, Amer. Math. Monthly, 95 (1988), 555.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 379
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,1).

Cf. A000045, A000079, A000930, A003269, A003520, A005709, A005710, A005711.

with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 5)}, unlabeled]: seq(count(SeqSetU, size=j), j=6..59); # Zerinvary Lajos, Oct 10 2006
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 5)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=5..58); # Zerinvary Lajos, Mar 26 2008
M := Matrix(6, (i,j)-> if j=1 and member(i,[1,6]) then 1 elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,1]; seq(a(n), n=0..60); # Alois P. Heinz, Jul 27 2008

LinearRecurrence[{1, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)

x='x+O('x^66); Vec(x/(1-(x+x^6))) /* Joerg Arndt, Jun 25 2011 */

G.f.: 1/(1-x-x^6). - Simon Plouffe in his 1992 dissertation
a(n) = term (1,1) in the 6 X 6 matrix [1,1,0,0,0,0; 0,0,1,0,0,0; 0,0,0,1,0,0; 0,0,0,0,1,0; 0,0,0,0,0,1; 1,0,0,0,0,0]^n. - Alois P. Heinz, Jul 27 2008
For positive integers n and k such that k <= n <= 6*k and 5 divides n-k, define c(n,k) = binomial(k,(n-k)/5), and c(n,k)=0, otherwise. Then, for n>= 1, a(n) = sum_{k=1..n} c(n,k). - Milan Janjic, Dec 09 2011
Apparently a(n) = hypergeometric([1/6-n/6, 1/3-n/6, 1/2-n/6, 2/3-n/6, 5/6-n/6, -n/6], [1/5-n/5, 2/5-n/5, 3/5- n/5, 4/5-n/5, -n/5], -6^6/5^5) for n>=25. - Peter Luschny, Sep 19 2014

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

A005710 a(n) = a(n-1) + a(n-8), with a(i) = 1 for i = 0..7.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 14, 18, 23, 29, 36, 44, 53, 64, 78, 96, 119, 148, 184, 228, 281, 345, 423, 519, 638, 786, 970, 1198, 1479, 1824, 2247, 2766, 3404, 4190, 5160, 6358, 7837, 9661, 11908, 14674, 18078, 22268, 27428, 33786, 41623

Offset: 0

N. J. A. Sloane

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 = 0...m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
For n >= 8, a(n-8) = number of compositions of n in which each part is >= 8. - Milan Janjic, Jun 28 2010
Number of compositions of n into parts 1 and 8. - Joerg Arndt, Jun 24 2011
a(n+7) equals the number of binary words of length n having at least 7 zeros between every two successive ones. - Milan Janjic, Feb 09 2015

P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..500
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See p. 18.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 10.
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018.
D. Kleitman, Solution to Problem E3274, Amer. Math. Monthly, 98 (1991), 958-959.
A. O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper No. A60, 10 pp.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
D. Newman, Problem E3274, Amer. Math. Monthly, 95 (1988), 555.
Djamila Oudrar and Maurice Pouzet, Ordered structures with no finite monomorphic decomposition. Application to the profile of hereditary classes, arXiv:2312.05913 [math.CO], 2023. See p. 18.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 381
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,1).

Cf. A000045, A000079, A000930, A003269, A003520, A005708, A005709, A005711.

A005710:=-1/(-1+z+z**8); # Simon Plouffe in his 1992 dissertation.
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 7)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=7..62); # Zerinvary Lajos, Mar 26 2008
M := Matrix(8, (i,j)-> if j=1 and member(i,[1,8]) then 1 elif (i=j-1) then 1 else 0 fi); a := n -> (M^(n))[1,1]; seq(a(n), n=0..55); # Alois P. Heinz, Jul 27 2008

LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)
CoefficientList[Series[1/(1-x-x^8),{x,0,60}],x] (* Harvey P. Dale, Jun 14 2016 *)

x='x+O('x^66); Vec(x/(1-(x+x^8))) /* Joerg Arndt, Jun 25 2011 */

G.f.: 1/(1-x-x^8).
For positive integers n and k such that k <= n <= 8*k, and 7 divides n-k, define c(n,k) = binomial(k,(n-k)/7), and c(n,k) = 0, otherwise. Then, for n >= 1, a(n-1) = Sum_{k=1..n} c(n,k). - Milan Janjic, Dec 09 2011
Apparently a(n) = hypergeometric([1/8-n/8, 1/4-n/8, 3/8-n/8, 1/2-n/8, 5/8-n/8, 3/4-n/8, 7/8-n/8, -n/8], [1/7-n/7, 2/7-n/7, 3/7-n/7, 4/7-n/7, 5/7-n/7, 6/7-n/7, -n/7], -8^8/7^7) for n >= 49. - Peter Luschny, Sep 19 2014

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

A001609 a(1) = a(2) = 1, a(3) = 4; thereafter a(n) = a(n-1) + a(n-3).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

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_{i=1..n/m} binomial(n-1-(m-1)*i, i-1)/i. 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
Except for n = 2, a(n) is the number of digits in n-th term of A049064. This can be derived form the T. Sillke link below. - Jianing Song, Apr 28 2019

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

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

Indranil Ghosh, Table of n, a(n) for n = 1..6012 (terms 1..500 from T. D. Noe)
Ignacio Cascudo, On squares of cyclic codes, arXiv:1703.01267 [cs.IT], 2017. See Theorem 6.1/Table 1.
Johann Cigler, Some remarks on generalized Fibonacci and Lucas polynomials, arXiv:1912.06651 [math.CO], 2019.
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; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Souvik Roy, Nazim Fatès, and Sukanta Das, Reversibility of Elementary Cellular Automata with fully asynchronous updating: an analysis of the rules with partial recurrence, hal-04456320 [nlin.CG], [cs], 2024. See p. 19.
T. Sillke, The binary form of Conway's sequence
Z. Skupien, Sparse Hamiltonian 2-decompositions together with exact count of numerous Hamiltonian 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).

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

Cf. also A049064, A049194.

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

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

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

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

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), see A092526. - Gerry Martens, Jun 27 2015

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
More terms from Michael Somos, Oct 03 2002
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

cp's OEIS Frontend

A000204 Lucas numbers (beginning with 1): L(n) = L(n-1) + L(n-2) with L(1) = 1, L(2) = 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Python

Sage

Scala

Formula

Extensions

A000930 Narayana's cows sequence: a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n-1) + a(n-3).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

PARI

Python

SageMath

Formula

Extensions

A003269 a(n) = a(n-1) + a(n-4) with a(0) = 0, a(1) = a(2) = a(3) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A003520 a(n) = a(n-1) + a(n-5); a(0) = ... = a(4) = 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A005708 a(n) = a(n-1) + a(n-6), with a(i) = 1 for i = 0..5.

Views