A002478 -id:A002478 - cp's OEIS frontend

A001333 Pell-Lucas numbers: numerators of continued fraction convergents to sqrt(2).

1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, 19601, 47321, 114243, 275807, 665857, 1607521, 3880899, 9369319, 22619537, 54608393, 131836323, 318281039, 768398401, 1855077841, 4478554083, 10812186007, 26102926097, 63018038201, 152139002499, 367296043199

Offset: 0

N. J. A. Sloane and R. K. Guy

Number of n-step non-selfintersecting paths starting at (0,0) with steps of types (1,0), (-1,0) or (0,1) [Stanley].
Number of n steps one-sided prudent walks with east, west and north steps. - Shanzhen Gao, Apr 26 2011
Number of ternary strings of length n-1 with subwords (0,2) and (2,0) not allowed. - Olivier Gérard, Aug 28 2012
Number of symmetric 2n X 2 or (2n-1) X 2 crossword puzzle grids: all white squares are edge connected; at least 1 white square on every edge of grid; 180-degree rotational symmetry. - Erich Friedman
a(n+1) is the number of ways to put molecules on a 2 X n ladder lattice so that the molecules do not touch each other.
In other words, a(n+1) is the number of independent vertex sets and vertex covers in the n-ladder graph P_2 X P_n. - Eric W. Weisstein, Apr 04 2017
Number of (n-1) X 2 binary arrays with a path of adjacent 1's from top row to bottom row, see A359576. - R. H. Hardin, Mar 16 2002
a(2*n+1) with b(2*n+1) := A000129(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation a^2 - 2*b^2 = -1.
a(2*n) with b(2*n) := A000129(2*n), n >= 1, give all (positive integer) solutions to Pell equation a^2 - 2*b^2 = +1 (see Emerson reference).
Bisection: a(2*n) = T(n,3) = A001541(n), n >= 0 and a(2*n+1) = S(2*n,2*sqrt(2)) = A002315(n), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. See A053120, resp. A049310.
Binomial transform of A077957. - Paul Barry, Feb 25 2003
For n > 0, the number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 4 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 2, s(n) = 2. - Herbert Kociemba, Jun 02 2004
For n > 1, a(n) corresponds to the longer side of a near right-angled isosceles triangle, one of the equal sides being A000129(n). - Lekraj Beedassy, Aug 06 2004
Exponents of terms in the series F(x,1), where F is determined by the equation F(x,y) = xy + F(x^2*y,x). - Jonathan Sondow, Dec 18 2004
Number of n-words from the alphabet A={0,1,2} which two neighbors differ by at most 1. - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Aug 30 2006
Consider the mapping f(a/b) = (a + 2b)/(a + b). Taking a = b = 1 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the following sequence 1/1, 3/2, 7/5, 17/12, 41/29, ... converging to 2^(1/2). Sequence contains the numerators. - Amarnath Murthy, Mar 22 2003 [Amended by Paul E. Black (paul.black(AT)nist.gov), Dec 18 2006]
Odd-indexed prime numerators are prime RMS numbers (A140480) and also NSW primes (A088165). - Ctibor O. Zizka, Aug 13 2008
The intermediate convergents to 2^(1/2) begin with 4/3, 10/7, 24/17, 58/41; essentially, numerators=A052542 and denominators here. - Clark Kimberling, Aug 26 2008
Equals right border of triangle A143966. Starting (1, 3, 7, ...) equals INVERT transform of (1, 2, 2, 2, ...) and row sums of triangle A143966. - Gary W. Adamson, Sep 06 2008
Inverse binomial transform of A006012; Hankel transform is := [1, 2, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 2008
From Charlie Marion, Jan 07 2009: (Start)
In general, denominators, a(k,n) and numerators, b(k,n), of continued fraction convergents to sqrt((k+1)/k) may be found as follows:
let a(k,0) = 1, a(k,1) = 2k; for n>0, a(k,2n) = 2*a(k,2n-1) + a(k,2n-2) and a(k,2n+1) = (2k)*a(k,2n) + a(k,2n-1);
let b(k,0) = 1, b(k,1) = 2k+1; for n>0, b(k,2n) = 2*b(k,2n-1) + b(k,2n-2) and b(k,2n+1) = (2k)*b(k,2n) + b(k,2n-1).
For example, the convergents to sqrt(2/1) start 1/1, 3/2, 7/5, 17/12, 41/29.
In general, if a(k,n) and b(k,n) are the denominators and numerators, respectively, of continued fraction convergents to sqrt((k+1)/k) as defined above, then
k*a(k,2n)^2 - a(k,2n-1)*a(k,2n+1) = k = k*a(k,2n-2)*a(k,2n) - a(k,2n-1)^2 and
b(k,2n-1)*b(k,2n+1) - k*b(k,2n)^2 = k+1 = b(k,2n-1)^2 - k*b(k,2n-2)*b(k,2n);
for example, if k=1 and n=3, then b(1,n)=a(n+1) and
1*a(1,6)^2 - a(1,5)*a(1,7) = 1*169^2 - 70*408 = 1;
1*a(1,4)*a(1,6) - a(1,5)^2 = 1*29*169 - 70^2 = 1;
b(1,5)*b(1,7) - 1*b(1,6)^2 = 99*577 - 1*239^2 = 2;
b(1,5)^2 - 1*b(1,4)*b(1,6) = 99^2 - 1*41*239 = 2.
Cf. A000129, A142238-A142239, A153313-A153318.
(End)
This sequence occurs in the lower bound of the order of the set of equivalent resistances of n equal resistors combined in series and in parallel (A048211). - Sameen Ahmed Khan, Jun 28 2010
Let M = a triangle with the Fibonacci series in each column, but the leftmost column is shifted upwards one row. A001333 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. - Gary W. Adamson, Jul 27 2010
a(n) is the number of compositions of n when there are 1 type of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010
Equals the INVERTi transform of A055099. - Gary W. Adamson, Aug 14 2010
From L. Edson Jeffery, Apr 04 2011: (Start)
Let U be the unit-primitive matrix (see [Jeffery])
U = U_(8,2) = (0 0 1 0)
              (0 1 0 1)
              (1 0 2 0)
              (0 2 0 1).
Then a(n) = (1/4)*Trace(U^n). (See also A084130, A006012.)
(End)
For n >= 1, row sums of triangle
  m/k.|..0.....1.....2.....3.....4.....5.....6.....7
  ==================================================
  .0..|..1
  .1..|..1.....2
  .2..|..1.....2.....4
  .3..|..1.....4.....4.....8
  .4..|..1.....4....12.....8....16
  .5..|..1.....6....12....32....16....32
  .6..|..1.....6....24....32....80....32....64
  .7..|..1.....8....24....80....80...192....64...128
which is the triangle for numbers 2^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 12 2012
a(n) is also the number of ways to place k non-attacking wazirs on a 2 X n board, summed over all k >= 0 (a wazir is a leaper [0,1]). - Vaclav Kotesovec, May 08 2012
The sequences a(n) and b(n) := A000129(n) are entries of powers of the special case of the Brahmagupta Matrix - for details see Suryanarayan's paper. Further, as Suryanarayan remark, if we set A = 2*(a(n) + b(n))*b(n), B = a(n)*(a(n) + 2*b(n)), C = a(n)^2 + 2*a(n)*b(n) + 2*b(n)^2 we obtain integral solutions of the Pythagorean relation A^2 + B^2 = C^2, where A and B are consecutive integers. - Roman Witula, Jul 28 2012
Pisano period lengths: 1, 1, 8, 4, 12, 8, 6, 4, 24, 12, 24, 8, 28, 6, 24, 8, 16, 24, 40, 12, .... - R. J. Mathar, Aug 10 2012
This sequence and A000129 give the diagonal numbers described by Theon of Smyrna. - Sture Sjöstedt, Oct 20 2012
a(n) is the top left entry of the n-th power of any of the following six 3 X 3 binary matrices: [1, 1, 1; 1, 1, 1; 1, 0, 0] or [1, 1, 1; 1, 1, 0; 1, 1, 0] or [1, 1, 1; 1, 0, 1; 1, 1, 0] or [1, 1, 1; 1, 1, 0; 1, 0, 1] or [1, 1, 1; 1, 0, 1; 1, 0, 1] or [1, 1, 1; 1, 0, 0; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
If p is prime, a(p) == 1 (mod p) (compare with similar comment for A000032). - Creighton Dement, Oct 11 2005, modified by Davide Colazingari, Jun 26 2016
a(n) = A000129(n) + A000129(n-1), where A000129(n) is the n-th Pell Number; e.g., a(6) = 99 = A000129(6) + A000129(5) = 70 + 29. Hence the sequence of fractions has the form 1 + A000129(n-1)/A000129(n), and the ratio A000129(n-1)/A000129(n)converges to sqrt(2) - 1. - Gregory L. Simay, Nov 30 2018
For n > 0, a(n+1) is the length of tau^n(1) where tau is the morphism: 1 -> 101, 0 -> 1. See Song and Wu. - Michel Marcus, Jul 21 2020
For n > 0, a(n) is the number of nonisomorphic quasitrivial semigroups with n elements, see Devillet, Marichal, Teheux. A292932 is the number of labeled quasitrivial semigroups. - Peter Jipsen, Mar 28 2021
a(n) is the permanent of the n X n tridiagonal matrix defined in A332602. - Stefano Spezia, Apr 12 2022
From Greg Dresden, May 08 2023: (Start)
For n >= 2, 4*a(n) is the number of ways to tile this T-shaped figure of length n-1 with two colors of squares and one color of domino; shown here is the figure of length 5 (corresponding to n=6), and it has 4*a(6) = 396 different tilings.
   _
  || _  
  |||_|||
  |_|
(End)
12*a(n) = number of walks of length n in the cyclic Kautz digraph CK(3,4). - Miquel A. Fiol, Feb 15 2024

			Convergents are 1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, 8119/5741, 19601/13860, 47321/33461, 114243/80782, ... = A001333/A000129.
The 15 3 X 2 crossword grids, with white squares represented by an o:
  ooo ooo ooo ooo ooo ooo ooo oo. o.o .oo o.. .o. ..o oo. .oo
  ooo oo. o.o .oo o.. .o. ..o ooo ooo ooo ooo ooo ooo .oo oo.
G.f. = 1 + x + 3*x^2 + 7*x^3 + 17*x^4 + 41*x^5 + 99*x^6 + 239*x^7 + 577*x^8 + ...

M. R. Bacon and C. K. Cook, Some properties of Oresme numbers and convolutions ..., Fib. Q., 62:3 (2024), 233-240.
A. H. Beiler, Recreations in the Theory of Numbers. New York: Dover, pp. 122-125, 1964.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 204.
John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, see p. 16.
J. Devillet, J.-L. Marichal, and B. Teheux, Classifications of quasitrivial semigroups, Semigroup Forum, 100 (2020), 743-764.
Maribel Díaz Noguera [Maribel Del Carmen Díaz Noguera], Rigoberto Flores, Jose L. Ramirez, and Martha Romero Rojas, Catalan identities for generalized Fibonacci polynomials, Fib. Q., 62:2 (2024), 100-111.
Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
R. P. Grimaldi, Ternary strings with no consecutive 0's and no consecutive 1's, Congressus Numerantium, 205 (2011), 129-149.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §8.5 The Fibonacci and Related Sequences, p. 288.
A. F. Horadam, R. P. Loh, and A. G. Shannon, Divisibility properties of some Fibonacci-type sequences, pp. 55-64 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979.
Thomas Koshy, Pell and Pell-Lucas Numbers with Applications, Springer, New York, 2014.
Kin Y. Li, Math Problem Book I, 2001, p. 24, Problem 159.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 102, Problem 10.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 224.
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).
R. P. Stanley, Enumerative Combinatorics, Volume 1 (1986), p. 203, Example 4.1.2.
A. Tarn, Approximations to certain square roots and the series of numbers connected therewith, Mathematical Questions and Solutions from the Educational Times, 1 (1916), 8-12.
R. C. Tilley et al., The cell growth problem for filaments, Proc. Louisiana Conf. Combinatorics, ed. R. C. Mullin et al., Baton Rouge, 1970, 310-339.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987, p. 34.

T. D. Noe, Table of n, a(n) for n = 0..500
Antoni Amengual, The intriguing properties of the equivalent resistances of n equal resistors combined in series and in parallel, American Journal of Physics, 68(2), (2000) 175-179. [From _Sameen Ahmed Khan_, Jun 28 2010]
Joerg Arndt, Matters Computational (The Fxtbook), pp. 313-315.
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002. [Broken link]
S. Barbero, U. Cerruti, and N. Murru, A Generalization of the Binomial Interpolated Operator and its Action on Linear Recurrent Sequences, J. Int. Seq. 13 (2010) # 10.9.7.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
M. Bicknell, A Primer on the Pell Sequence and related sequences, Fibonacci Quarterly, Vol. 13, No. 4, 1975, pp. 345-349.
Florin P. Boca and Christopher Linden, On Minkowski type question mark functions associated with even or odd continued fractions, arXiv:1705.01238 [math.DS], 2017. See p. 7.
J. Bodeen, S. Butler, T. Kim, X. Sun, and S. Wang, Tiling a strip with triangles, El. J. Combinat. 21 (1) (2014) P1.7
K. Böhmová, C. Dalfó, and C. Huemer, The diameter of cyclic Kautz digraphs, Filomat 31(20) (2017) 6551-6560.
Fan Chung and R. L. Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194.
Jimmy Devillet, Jean-Luc Marichal, and Bruno Teheux, Classifications of quasitrivial semigroups, arXiv:1811.11113 [math.RA], 2020.
K. Dohmen, Closed-form expansions for the universal edge elimination polynomial, arXiv preprint arXiv:1403.0969 [math.CO], 2014.
Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, arXiv:1907.06517 [math.CO], 2019.
E. I. Emerson, Recurrent Sequences in the Equation DQ^2=R^2+N, Fib. Quart., 7 (1969), pp. 231-242, see Ex. 1, pp. 237-238.
Reinhardt Euler, The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.
Bruce Fang, Pamela E. Harris, Brian M. Kamau, and David Wang, Vacillating parking functions, arXiv:2402.02538 [math.CO], 2024.
M. C. Firengiz and A. Dil, Generalized Euler-Seidel method for second order recurrence relations, Notes on Number Theory and Discrete Mathematics, Vol. 20, 2014, No. 4, 21-32.
Shanzhen Gaoa and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
David Garth and Adam Gouge, Affinely Self-Generating Sets and Morphisms, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.5.
Martin Griffiths, Pell identities via a quadratic field, International Journal of Mathematical Education in Science and Technology, 2013.
F. Harary and R. W. Robinson, Tapeworms, Unpublished manuscript, circa 1973. (Annotated scanned copy)
R. J. Hetherington, Letter to N. J. A. Sloane, Oct 26 1974.
Gábor Hetyei, The type B permutohedron and the poset of intervals as a Tchebyshev transform, Discrete Comput Geom 71, 918-944 (2024).
Nick Hobson, Python program for this sequence
A. F. Horadam, R. P. Loh, and A. G. Shannon, Divisibility properties of some Fibonacci-type sequences, pp. 55-64 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979. [Annotated scanned copy]
Lucas Hoots, Strong quota pair systems and May's theorem on median semilattices, Univ. Louisville, Electronic Theses and Dissertations. Paper 2253, (2015).
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 143.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
L. E. Jeffery, Unit-primitive matrices.
Sameen Ahmed Khan, The bounds of the set of equivalent resistances of n equal resistors combined in series and in parallel, arXiv:1004.3346 [physics.gen-ph], 2010. [From _Sameen Ahmed Khan_, Jun 28 2010]
Tanya Khovanova, Recursive Sequences.
Y. Kong, Ligand binding on ladder lattices, Biophysical Chemistry, Vol. 81 (1999), pp. 7-21.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, pp. 392-393.
Dmitry Kruchinin, Integer properties of a composition of exponential generating functions, arXiv:1211.2100 [math.NT], 2012.
Markus Kuba and Alois Panholzer, Enumeration formulas for pattern restricted Stirling permutations, Discrete Math. 312 (2012), no. 21, 3179--3194. MR2957938. - From _N. J. A. Sloane_, Sep 25 2012
Pablo Lam-Estrada, Myriam Rosalía Maldonado-Ramírez, José Luis López-Bonilla, and Fausto Jarquín-Zárate, The sequences of Fibonacci and Lucas for each real quadratic fields Q(Sqrt(d)), arXiv:1904.13002 [math.NT], 2019.
J. V. Leyendekkers and A. G. Shannon, Pellian sequence relationships among pi, e, sqrt(2), Notes on Number Theory and Discrete Mathematics, Vol. 18, 2012, No. 2, 58-62. See Table 2. - _N. J. A. Sloane_, Dec 23 2012
Kin Y. Li, p. 24, Problem 159.
Daniel K. Mark, Hong-Ye Hu, Joyce Kwan, Christian Kokail, Soonwon Choi, and Susanne F. Yelin, Efficiently measuring d-wave pairing and beyond in quantum gas microscopes, arXiv:2412.13186 [cond-mat.quant-gas], 2024. See p. 7.
Barry Mazur, Arithmetic on curves, Bull. Amer. Math. Soc. 14 (1986), 207-259.
aBa Mbirika, Janee Schrader, and Jürgen Spilker, Pell and Associated Pell Braid Sequences as GCDs of Sums of k Consecutive Pell, Balancing, and Related Numbers, J. Int. Seq. (2023) Vol. 26, Art. 23.6.4.
Emanuele Munarini, Combinatorial properties of the antichains of a garland, Integers, 9 (2009), 353-374.
Yassine Otmani, The 2-Pascal Triangle and a Related Riordan Array, J. Int. Seq. (2025) Vol. 28, Issue 3, Art. No. 25.3.5. See p. 11.
Serge Perrine, About the diophantine equation z^2 = 32y^2 - 16, SCIREA Journal of Mathematics (2019) Vol. 4, Issue 5, 126-139.
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
H. Prodinger and R. F. Tichy, Fibonacci numbers of graphs, Fibonacci Quarterly, 20, 1982, 16-21.
Jon E. Schoenfield, Prime factorization of a(n) for n = 0..300
B. Srinivasa Rao, Heptagonal numbers in the associated Pell sequence and Diophantine equations x^2(5x - 3)^2 = 8y^2 ± 4, Fib. Quarterly, 43 (2005), 302-306.
John Riordan and N. J. A. Sloane, Correspondence, 1974
Alexander Shelupanov, Oleg Evsyutin, Anton Konev, Evgeniy Kostyuchenko, Dmitry Kruchinin, and Dmitry Nikiforov, Information Security Methods-Modern Research Directions, Symmetry (2019) Vol. 11, Issue 2, 150.
Haocong Song and Wen Wu, Hankel determinants of a Sturmian sequence, arXiv:2007.09940 [math.CO], 2020. See pp. 2, 4.
Claude Soudieux, De l'infini arithmétique, Zurich, 1960. [Annotated scans of selected pages. Contains many sequences including A1333]
E. R. Suryanarayan, The Brahmagupta Polynomials, Fibonacci Quarterly, 34.1 (1996), 30-39.
Wipawee Tangjai, A Non-standard Ternary Representation of Integers, Thai J. Math (2020) Special Issue: Annual Meeting in Mathematics 2019, 269-283.
Albert Tarn, Approximations to certain square roots and the series of numbers connected therewith. [Annotated scanned copy]
G. Tasi and F. Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes. I, J. Math. Chemistry, 25, 1999, 55-64 (see Eq. (21)).
G. Tasi et al., Quantum algebraic-combinatoric study of the conformational properties of n-alkanes. II, J. Math. Chemistry, 27, 2000, 191-199 (see p. 193).
V. Thebault, Concerning two classes of remarkable perfect square pairs, Amer. Math. Monthly, 56 (1949), 443-448.
Lucyna Trojnar-Spelina and Iwona Włoch, On Generalized Pell and Pell-Lucas Numbers, Iranian Journal of Science and Technology, Transactions A: Science (2019), 1-7.
Andrew Vince, The average size of a connected vertex set of a graph - Explicit formulas and open problems, Journal of Graph Theory, Volume 97, Issue 1 pp. 82-103.
Eric Weisstein's World of Mathematics, Independent Vertex Set.
Eric Weisstein's World of Mathematics, Ladder Graph.
Eric Weisstein's World of Mathematics, Pythagoras's Constant.
Eric Weisstein's World of Mathematics, Square Root.
Eric Weisstein's World of Mathematics, Square Triangular Number.
Eric Weisstein's World of Mathematics, Vertex Cover.
Index entries for "core" sequences.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (2,1).

For denominators see A000129.
See A040000 for the continued fraction expansion of sqrt(2).
See also A078057 which is the same sequence without the initial 1.
Cf. also A002203, A152113.
Row sums of unsigned Chebyshev T-triangle A053120. a(n)= A054458(n, 0) (first column of convolution triangle).
Row sums of A140750, A160756, A135837.
Equals A034182(n-1) + 2 and A084128(n)/2^n. First differences of A052937. Partial sums of A052542. Pairwise sums of A048624. Bisection of A002965.
The following sequences (and others) belong to the same family: A001333, A000129, A026150, A002605, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.
Second row of the array in A135597.
Cf. A048211, A153588, A174283, A174284, A174285, A174286, A176499, A176500, A176501, A176502.
Cf. A055099.
Cf. A028859, A001906 / A088305, A033303, A000225, A095263, A003945, A006356, A002478, A214260, A001911 and A000217 for other restricted ternary words.
Cf. Triangle A106513 (alternating row sums).
Equals A293004 + 1.
Cf. A033539, A332602, A086395 (subseq. of primes).

a001333 n = a001333_list !! n
a001333_list = 1 : 1 : zipWith (+)
                       a001333_list (map (* 2) $ tail a001333_list)
-- Reinhard Zumkeller, Jul 08 2012

[n le 2 select 1 else 2*Self(n-1)+Self(n-2): n in [1..35]]; // Vincenzo Librandi, Nov 10 2018

A001333 := proc(n) option remember; if n=0 then 1 elif n=1 then 1 else 2*procname(n-1)+procname(n-2) fi end;
Digits := 50; A001333 := n-> round((1/2)*(1+sqrt(2))^n);
with(numtheory): cf := cfrac (sqrt(2),1000): [seq(nthnumer(cf,i), i=0..50)];
a:= n-> (M-> M[2, 1]+M[2, 2])(<<2|1>, <1|0>>^n):
seq(a(n), n=0..33);  # Alois P. Heinz, Aug 01 2008
A001333List := proc(m) local A, P, n; A := [1,1]; P := [1,1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(A), P[-2]]);
A := [op(A), P[-1]] od; A end: A001333List(32); # Peter Luschny, Mar 26 2022

Insert[Table[Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[2], n]]], {n, 1, 40}], 1, 1] (* Stefan Steinerberger, Apr 08 2006 *)
Table[((1 - Sqrt[2])^n + (1 + Sqrt[2])^n)/2, {n, 0, 29}] // Simplify (* Robert G. Wilson v, May 02 2006 *)
a[0] = 1; a[1] = 1; a[n_] := a[n] = 2a[n - 1] + a[n - 2]; Table[a@n, {n, 0, 29}] (* Robert G. Wilson v, May 02 2006 *)
Table[ MatrixPower[{{1, 2}, {1, 1}}, n][[1, 1]], {n, 0, 30}] (* Robert G. Wilson v, May 02 2006 *)
a=c=0;t={b=1}; Do[c=a+b+c; AppendTo[t,c]; a=b;b=c,{n,40}]; t (* Vladimir Joseph Stephan Orlovsky, Mar 23 2009 *)
LinearRecurrence[{2, 1}, {1, 1}, 40] (* Vladimir Joseph Stephan Orlovsky, Mar 23 2009 *)
Join[{1}, Numerator[Convergents[Sqrt[2], 30]]] (* Harvey P. Dale, Aug 22 2011 *)
Table[(-I)^n ChebyshevT[n, I], {n, 10}] (* Eric W. Weisstein, Apr 04 2017 *)
CoefficientList[Series[(-1 + x)/(-1 + 2 x + x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
Table[Sqrt[(ChebyshevT[n, 3] + (-1)^n)/2], {n, 0, 20}] (* Eric W. Weisstein, Apr 17 2018 *)

{a(n) = if( n<0, (-1)^n, 1) * contfracpnqn( vector( abs(n), i, 1 + (i>1))) [1, 1]}; /* Michael Somos, Sep 02 2012 */

{a(n) = polchebyshev(n, 1, I) / I^n}; /* Michael Somos, Sep 02 2012 */

a(n) = real((1 + quadgen(8))^n); \\ Michel Marcus, Mar 16 2021

{ for (n=0, 4000, a=contfracpnqn(vector(n, i, 1+(i>1)))[1, 1]; if (a > 10^(10^3 - 6), break); write("b001333.txt", n, " ", a); ); } \\ Harry J. Smith, Jun 12 2009

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

from sage.combinat.sloane_functions import recur_gen2
it = recur_gen2(1,1,2,1)
[next(it) for i in range(30)] ## Zerinvary Lajos, Jun 24 2008

[lucas_number2(n,2,-1)/2 for n in range(0, 30)] # Zerinvary Lajos, Apr 30 2009

a(n) = A055642(A125058(n)). - Reinhard Zumkeller, Feb 02 2007
a(n) = 2a(n-1) + a(n-2);
a(n) = ((1-sqrt(2))^n + (1+sqrt(2))^n)/2.
a(n)+a(n+1) = 2 A000129(n+1). 2*a(n) = A002203(n).
G.f.: (1 - x) / (1 - 2*x - x^2) = 1 / (1 - x / (1 - 2*x / (1 + x))). - Simon Plouffe in his 1992 dissertation.
A000129(2n) = 2*A000129(n)*a(n). - John McNamara, Oct 30 2002
a(n) = (-i)^n * T(n, i), with T(n, x) Chebyshev's polynomials of the first kind A053120 and i^2 = -1.
a(n) = a(n-1) + A052542(n-1), n>1. a(n)/A052542(n) converges to sqrt(1/2). - Mario Catalani (mario.catalani(AT)unito.it), Apr 29 2003
E.g.f.: exp(x)cosh(x*sqrt(2)). - Paul Barry, May 08 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)2^k. - Paul Barry, May 13 2003
For n > 0, a(n)^2 - (1 + (-1)^(n))/2 = Sum_{k=0..n-1} ((2k+1)*A001653(n-1-k)); e.g., 17^2 - 1 = 288 = 1*169 + 3*29 + 5*5 + 7*1; 7^2 = 49 = 1*29 + 3*5 + 5*1. - Charlie Marion, Jul 18 2003
a(n+2) = A078343(n+1) + A048654(n). - Creighton Dement, Jan 19 2005
a(n) = A000129(n) + A000129(n-1) = A001109(n)/A000129(n) = sqrt(A001110(n)/A000129(n)^2) = ceiling(sqrt(A001108(n))). - Henry Bottomley, Apr 18 2000
Also the first differences of A000129 (the Pell numbers) because A052937(n) = A000129(n+1) + 1. - Graeme McRae, Aug 03 2006
a(n) = Sum_{k=0..n} A122542(n,k). - Philippe Deléham, Oct 08 2006
For another recurrence see A000129.
a(n) = Sum_{k=0..n} A098158(n,k)*2^(n-k). - Philippe Deléham, Dec 26 2007
a(n) = upper left and lower right terms of [1,1; 2,1]^n. - Gary W. Adamson, Mar 12 2008
If p[1]=1, and p[i]=2, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, Apr 29 2010
For n>=2, a(n)=F_n(2)+F_(n+1)(2), where F_n(x) is Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} binomial(n-i-1,i)x^(n-2*i-1). - Vladimir Shevelev, Apr 13 2012
a(-n) = (-1)^n * a(n). - Michael Somos, Sep 02 2012
Dirichlet g.f.: (PolyLog(s,1-sqrt(2)) + PolyLog(s,1+sqrt(2)))/2. - Ilya Gutkovskiy, Jun 26 2016
a(n) = A000129(n) - A000129(n-1), where A000129(n) is the n-th Pell Number. Hence the continued fraction is of the form 1-(A000129(n-1)/A000129(n)). - Gregory L. Simay, Nov 09 2018
a(n) = (A000129(n+3) + A000129(n-3))/10, n>=3. - Paul Curtz, Jun 16 2021
a(n) = (A000129(n+6) - A000129(n-6))/140, n>=6. - Paul Curtz, Jun 20 2021
a(n) = round((1/2)*sqrt(Product_{k=1..n} 4*(1 + sin(k*Pi/n)^2))), for n>=1. - Greg Dresden, Dec 28 2021
a(n)^2 + a(n+1)^2 = A075870(n+1) = 2*(b(n)^2 + b(n+1)^2) for all n in Z where b(n) := A000129(n). - Michael Somos, Apr 02 2022
a(n) = 2*A048739(n-2)+1. - R. J. Mathar, Feb 01 2024
Sum_{n>=1} 1/a(n) = 1.5766479516393275911191017828913332473... - R. J. Mathar, Feb 05 2024
From Peter Bala, Jul 06 2025: (Start)
G.f.: Sum_{n >= 1} (-1)^(n+1) * x^(n-1) * Product_{k = 1..n} (1 - k*x)/(1 - 3*x + k*x^2).
The following series telescope:
Sum_{n >= 1} (-1)^(n+1)/(a(2*n) + 1/a(2*n)) = 1/4, since 1/(a(2*n) + 1/a(2*n)) = 1/A077445(n) + 1/A077445(n+1).
Sum_{n >= 1} (-1)^(n+1)/(a(2*n+1) - 1/a(2*n+1)) = 1/8, since. 1/(a(2*n+1) - 1/a(2*n+1)) = 1/(4*Pell(2*n)) + 1/(4*Pell(2*n+2)), where Pell(n) = A000129(n).
Sum_{n >= 1} (-1)^(n+1)/(a(2*n+1) + 9/a(2*n+1)) = 1/10, since 1/(a(2*n+1) + 9/a(2*n+1)) = b(n) + b(n+1), where b(n) = A001109(n)/(2*Pell(2*n-1)*Pell(2*n+1)).
Sum_{n >= 1} (-1)^(n+1)/(a(n)*a(n+1)) = 1 - sqrt(2)/2 = A268682, since (-1)^(n+1)/(a(n)*a(n+1)) = Pell(n)/a(n) - Pell(n+1)/a(n+1). (End)

Chebyshev comments from Wolfdieter Lang, Jan 10 2003

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

A291728 p-INVERT of (1,0,1,0,0,0,0,...), where p(S) = 1 - S - S^2.

Original entry on oeis.org

1, 2, 4, 9, 17, 35, 70, 142, 285, 576, 1160, 2340, 4716, 9510, 19171, 38653, 77926, 157110, 316747, 638599, 1287479, 2595698, 5233196, 10550681, 21271280, 42885152, 86460984, 174314476, 351436368, 708532813, 1428476905, 2879960190, 5806303628, 11706120825

Offset: 0

Clark Kimberling, Sep 08 2017

Suppose s = (c(0), c(1), c(2), ...) is a sequence and p(S) is a polynomial. Let S(x) = c(0)*x + c(1)*x^2 + c(2)*x^3 + ... and T(x) = (-p(0) + 1/p(S(x)))/x. The p-INVERT of s is the sequence t(s) of coefficients in the Maclaurin series for T(x). Taking p(S) = 1 - S gives the "INVERT" transform of s, so that p-INVERT is a generalization of the "INVERT" transform (e.g., A033453).
In the following guide to p-INVERT sequences using s = (1,0,1,0,0,0,0,...) = A154272, in some cases t(1,0,1,0,0,0,0,...) is a shifted (or differently indexed) version of the indicated sequence:
***
p(S)             t(1,0,1,0,0,0,0,...)
1 - S                A000930 (Narayana's cows sequence)
1 - S^2              A002478 (except for 0's)
1 - S^3              A291723
1 - S^5              A291724
(1 - S)^2            A291725
(1 - S)^3            A291726
(1 - S)^4            A291727
1 - S - S^2          A291728
1 - 2S - S^2         A291729
1 - 2S - 2S^2        A291730
(1 - 2S)^2           A291732
(1 - S)(1 - 2S)      A291734
1 - S - S^3          A291735
1 - S^2 - S^3        A291736
1 - S - S^2 - S^3    A291737
1 - S - S^4          A291738
1 - S^3 - S^6        A291739
(1 - S)(1 - S^2)     A291740
(1 - S)(1 + S^2)     A291741

Clark Kimberling, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,1,1,2,0,1).

Cf. A154272, A290890, A291000, A291382, A291219, A291382.

z = 60; s = x + x^3; p = 1 - s - s^2;
Drop[CoefficientList[Series[s, {x, 0, z}], x], 1]  (* A154272 *)
Drop[CoefficientList[Series[1/p, {x, 0, z}], x], 1]  (* A291728 *)

G.f.: (-1 - x - x^2 - 2 x^3 - x^5)/(-1 + x + x^2 + x^3 + 2 x^4 + x^6).

a(n) = a(n-1) + a(n-2) + a(n-3) + 2*a(n-4) + a(n-6) for n >= 7.

A219924 Number A(n,k) of tilings of a k X n rectangle using integer-sided square tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 5, 6, 5, 1, 1, 1, 1, 8, 13, 13, 8, 1, 1, 1, 1, 13, 28, 40, 28, 13, 1, 1, 1, 1, 21, 60, 117, 117, 60, 21, 1, 1, 1, 1, 34, 129, 348, 472, 348, 129, 34, 1, 1, 1, 1, 55, 277, 1029, 1916, 1916, 1029, 277, 55, 1, 1

Offset: 0

Alois P. Heinz, Dec 01 2012

For drawings of A(1,1), A(2,2), ..., A(5,5) see A224239.

			A(3,3) = 6, because there are 6 tilings of a 3 X 3 rectangle using integer-sided squares:
  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
  |     |  |   |_|  |_|   |  |_|_|_|  |_|_|_|  |_|_|_|
  |     |  |___|_|  |_|___|  |_|   |  |   |_|  |_|_|_|
  |_____|  |_|_|_|  |_|_|_|  |_|___|  |___|_|  |_|_|_|
Square array A(n,k) begins:
  1,  1,  1,   1,    1,    1,     1,      1, ...
  1,  1,  1,   1,    1,    1,     1,      1, ...
  1,  1,  2,   3,    5,    8,    13,     21, ...
  1,  1,  3,   6,   13,   28,    60,    129, ...
  1,  1,  5,  13,   40,  117,   348,   1029, ...
  1,  1,  8,  28,  117,  472,  1916,   7765, ...
  1,  1, 13,  60,  348, 1916, 10668,  59257, ...
  1,  1, 21, 129, 1029, 7765, 59257, 450924, ...

Alois P. Heinz, Antidiagonals n = 0..30, flattened
Steve Butler, Jason Ekstrand, Steven Osborne, Counting Tilings by Taking Walks in a Graph, A Project-Based Guide to Undergraduate Research in Mathematics, Birkhäuser, Cham (2020), see page 169.

Columns (or rows) k=0+1, 2-10 give: A000012, A000045(n+1), A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Main diagonal gives A045846.
Cf. A113881, A226545.

b:= proc(n, l) option remember; local i, k, s, t;
      if max(l[])>n then 0 elif n=0 or l=[] then 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od; s:=0;
         for i from k to nops(l) while l[i]=0 do s:=s+
           b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])
         od; s
      fi
    end:
A:= (n, k)-> `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
seq(seq(A(n, d-n), n=0..d), d=0..14);
# The following is a second version of the program that lists the actual dissections. It produces a list of pairs for each dissection:
b:= proc(n, l, ll) local i, k, s, t;
      if max(l[])>n then 0 elif n=0 or l=[] then lprint(ll); 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l), ll)
    else for k do if l[k]=0 then break fi od; s:=0;
         for i from k to nops(l) while l[i]=0 do s:=s+
           b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)],
            [ll[],[k,1+i-k]])
         od; s
      fi
    end:
A:= (n, k)-> b(k, [0$n], []):
A(5,5);
# In each list [a,b] means put a square with side length b at
leftmost possible position with upper corner in row a.  For example
[[1,3], [4,2], [4,2], [1,2], [3,1], [3,1], [4,1], [5,1]], gives:
 ___.___.
|     |   |
|     |_|
|___|_|_|
|   |   |_|
|_|___|_|

b[n_, l_List] := b[n, l] = Module[{i, k, s, t}, Which[Max[l] > n, 0, n == 0 || l == {}, 1, Min[l] > 0, t = Min[l]; b[n-t, l-t], True, k = Position[l, 0, 1][[1, 1]]; s = 0; For[i = k, i <= Length[l] && l[[i]] == 0, i++, s = s + b[n, Join[l[[1;; k-1]], Table[1+i-k, {j, k, i}], l[[i+1;; -1]] ] ] ]; s]]; a[n_, k_] := If[n >= k, b[n, Array[0&, k]], b[k, Array[0&, n]]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from 1st Maple program *)

A228285 T(n,k) = Number of n X k binary arrays with top left value 1 and no two ones adjacent horizontally, vertically or nw-se diagonally.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 3, 3, 3, 5, 6, 13, 6, 5, 8, 13, 35, 35, 13, 8, 13, 28, 112, 133, 112, 28, 13, 21, 60, 337, 587, 587, 337, 60, 21, 34, 129, 1034, 2448, 3631, 2448, 1034, 129, 34, 55, 277, 3154, 10414, 21166, 21166, 10414, 3154, 277, 55, 89, 595, 9637, 44024, 126119

Offset: 1

R. H. Hardin, Aug 19 2013

			Table starts
   1   1    2      3       5        8         13          21            34
   1   1    3      6      13       28         60         129           277
   2   3   13     35     112      337       1034        3154          9637
   3   6   35    133     587     2448      10414       44024        186414
   5  13  112    587    3631    21166     126119      745178       4416695
   8  28  337   2448   21166   172082    1428523    11771298      97268701
  13  60 1034  10414  126119  1428523   16566199   190540884    2197847780
  21 129 3154  44024  745178 11771298  190540884  3057290265   49208639399
  34 277 9637 186414 4416695 97268701 2197847780 49208639399 1105411581741
Some solutions for n=4, k=4:
  1 0 0 1   1 0 0 1   1 0 0 0   1 0 1 0   1 0 0 0
  0 0 0 0   0 0 0 0   0 0 0 0   0 0 0 0   0 0 0 0
  0 0 0 1   0 0 0 1   0 0 0 0   0 0 0 0   0 0 0 1
  0 0 1 0   0 1 0 0   0 1 0 1   1 0 1 0   1 0 0 0

R. H. Hardin, Table of n, a(n) for n = 1..1300
Doron Zeilberger, Maple code for columns of A228285 and A226444
Doron Zeilberger, Maple output for columns of A228285

Column 1 is A000045.
Column 2 is A002478(n-1).
For columns 3 through 9 see A228278, A228279, A228280, A228281, A228282, A228283, A228284.
For the main diagonal (n X n matrices) see A228277.
If the requirement that the top corner is 1 is omitted we get A226444.
If the "nw-se" condition in the definition is changed to "ne-sw", we get A228476-A228482.
See also A228390 and A228506 for other variants.

Empirical for column k:
k=1: a(n) = a(n-1) + a(n-2).
k=2: a(n) = a(n-1) + 2*a(n-2) + a(n-3).
k=3: a(n) = a(n-1) + 5*a(n-2) + 4*a(n-3) - a(n-5) with g.f. x(2+x-x^3)/((1+x)(1-2x-3x^2-x^3+x^4)).
k=4: a(n) = a(n-1) +10*a(n-2) +15*a(n-3) +4*a(n-4) -6*a(n-5) -a(n-6) +3*a(n-7) -a(n-8) with g.f. x *(x-1) *(2*x^3 -5*x^2 -6*x -3) / ( 1 -x -10*x^2 -15*x^3 -4*x^4 +6*x^5 +x^6 -3*x^7 +x^8 ).
k=5: [order 13] - see A228280.
k=6: [order 21]
k=7: [order 34]
k=8: [order 55]
k=9: [order 89]
From Doron Zeilberger, Aug 19 2013 and Aug 22 2013: (Start)
Using the C-finite Ansatz one can show that the k-th column satisfies a recurrence of order F_{k+2} for all k. For k <= 11, this is the minimal order. The empirical g.f.'s given above are correct. For further g.f.'s and Maple code, see the links.
In more detail: Every k X n Hardin matrix can be viewed as a walk, of length n, on a graph with F_{k+2} vertices (labeled by the set of {0,1} vectors of length k that avoid two consecutive 1's, which is well known and fairly easy to see has cardinality F_{k+2}).
Then the computer constructs the adjacency matrix.
There is an edge between vertex v1 and vertex v2 only if it is NOT the case that there exists an i (1 <= i <= k) such that v1[i]=1 and v2[i]=1 AND it is not the case that there exists an i (1 <= i <= k-1) such that v1[i]=1 and v2[i+1]=1.
Let us call this matrix A(k).
Then the number of k X n Hardin matrices (without the restriction that the top-left entry is 1, A226444) is the sum of the entries (i,j) of A(k)^n, or equivalently (1,...., 1) A(k)^n (1, ...., 1)^T.
So
f_k(x) = Sum_{n>=0} a(n)*x^n
= (1,...., 1) Sum_{n>=0} A(k)^n*x^n (1, ...., 1)^T
= (1,...., 1) (I-A*x)^(-1)(1, ...., 1)^T
and Maple knows how to invert the symbolic matrix (I-A*x), and this explains why the characteristic polynomial is the symbol for the recurrence.
If we impose that restriction then the answer (A228285) is
[0-1-Vector with 1's for those whose first entry is 1] A(k)^n (1, ...., 1)^T.
(End)

Edited by N. J. A. Sloane, Aug 22 2013

Minor corrections and further edits by M. F. Hasler, Apr 28 2014

A063967 Triangle read by rows, T(n,k) = T(n-1,k) + T(n-2,k) + T(n-1,k-1) + T(n-2,k-1) and T(0,0) = 1.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 3, 7, 5, 1, 5, 15, 16, 7, 1, 8, 30, 43, 29, 9, 1, 13, 58, 104, 95, 46, 11, 1, 21, 109, 235, 271, 179, 67, 13, 1, 34, 201, 506, 705, 591, 303, 92, 15, 1, 55, 365, 1051, 1717, 1746, 1140, 475, 121, 17, 1, 89, 655, 2123, 3979, 4759, 3780, 2010, 703, 154, 19, 1

Offset: 0

Henry Bottomley, Sep 05 2001

			T(3,1) = T(2,1) + T(1,1) + T(2,0) + T(1,0) = 3 + 1 + 2 + 1 = 7.
Triangle begins:
   1,
   1,   1,
   2,   3,   1,
   3,   7,   5,   1,
   5,  15,  16,   7,   1,
   8,  30,  43,  29,   9,   1,
  13,  58, 104,  95,  46,  11,  1,
  21, 109, 235, 271, 179,  67, 13,  1,
  34, 201, 506, 705, 591, 303, 92, 15, 1

Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
E. Deutsch, L. Ferrari and S. Rinaldi, Production Matrices, Advances in Mathematics, 34 (2005) pp. 101-122.
Emanuele Munarini, A generalization of André-Jeannin's symmetric identity, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 98-118.

Row sums are A002605.
Columns include: A000045(n+1), A023610(n-1).
Main diagonal: A000012, a(n, n-1) = A005408(n-1).
Matrix inverse: A091698, matrix square: A091700.
Cf. A321620.
Sum_{k=0..n} x^k*T(n,k) is (-1)^n*A057086(n) (x=-11), (-1)^n*A057085(n+1) (x=-10), (-1)^n*A057084(n) (x=-9), (-1)^n*A030240(n) (x=-8), (-1)^n*A030192(n) (x=-7), (-1)^n*A030191(n) (x=-6), (-1)^n*A001787(n+1) (x=-5), A000748(n) (x=-4), A108520(n) (x=-3), A049347(n) (x=-2), A000007(n) (x=-1), A000045(n) (x=0), A002605(n) (x=1), A030195(n+1) (x=2), A057087(n) (x=3), A057088(n) (x=4), A057089(n) (x=5), A057090(n) (x=6), A057091(n) (x=7), A057092(n) (x=8), A057093(n) (x=9). - Philippe Deléham, Nov 03 2006

a063967_tabl = [1] : [1,1] : f [1] [1,1] where
   f us vs = ws : f vs ws where
     ws = zipWith (+) ([0] ++ us ++ [0]) $
          zipWith (+) (us ++ [0,0]) $ zipWith (+) ([0] ++ vs) (vs ++ [0])
-- Reinhard Zumkeller, Apr 17 2013

T[n_, k_] := Sum[Binomial[j, n - j]*Binomial[j, k], {j, 0, n}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 11 2017, after Paul Barry *)
(* Function RiordanSquare defined in A321620. *)
RiordanSquare[1/(1 - x - x^2), 11] // Flatten (* Peter Luschny, Nov 27 2018 *)

G.f.: 1/(1-x*(1+x)*(1+y)). - Vladeta Jovovic, Oct 11 2003
Riordan array (1/(1-x-x^2), x(1+x)/(1-x-x^2)). The inverse of the signed version (1/(1+x-x^2),x(1-x)/(1+x-x^2)) is abs(A091698). - Paul Barry, Jun 10 2005
T(n, k) = Sum_{j=0..n} C(j, n-j)C(j, k). - Paul Barry, Nov 09 2005
Diagonal sums are A002478. - Paul Barry, Nov 09 2005
A026729*A007318 as infinite lower triangular matrices. - Philippe Deléham, Dec 11 2008
Central coefficients T(2*n,n) are A137644. - Paul Barry, Apr 15 2010
Product of Riordan arrays (1, x(1+x))*(1/(1-x), x/(1-x)), that is, A026729*A007318. - Paul Barry, Mar 14 2011
Triangle T(n,k), read by rows, given by (1,1,-1,0,0,0,0,0,0,0,...) DELTA (1,0,0,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 12 2011

A207170 Number of 2 X n 0..1 arrays avoiding 0 0 0 and 1 0 1 horizontally and 0 0 1 and 1 0 1 vertically.

Original entry on oeis.org

4, 16, 36, 81, 169, 361, 784, 1681, 3600, 7744, 16641, 35721, 76729, 164836, 354025, 760384, 1633284, 3508129, 7535025, 16184529, 34762816, 74666881, 160376896, 344473600, 739894401, 1589218225, 3413480625, 7331811876, 15747991081

Offset: 1

R. H. Hardin, Feb 15 2012

nonn

			Some solutions for n=4
..1..1..1..1....1..0..0..1....0..1..1..0....1..1..1..1....1..0..0..1
..0..1..1..1....1..0..0..1....0..1..1..0....1..1..1..1....1..1..1..1

R. H. Hardin, Table of n, a(n) for n = 1..210

Row 2 of A207169.

Cf. A002478.

Empirical: a(n) = a(n-1) +a(n-2) +3*a(n-3) +a(n-4) -a(n-5) -a(n-6) for n>7.
G.f: 4*x -x^2*(-16-20*x-29*x^2-4*x^3+13*x^4+9*x^5) / ( (x^3+2*x^2+x-1)*(x^3-x^2-1) ). - R. J. Mathar, Aug 10 2017
Empirical: 31*a(n) = 114*A002478(n) +133*A002478(n-1) +55*A002478(n) +10*A077961(n) +32*A077961(n-1) -24*A077961(n-2) for n>1. - R. J. Mathar, Nov 09 2018

A366221 G.f. A(x) satisfies A(x) = 1 + x(1 + x)^2A(x)^3.

Original entry on oeis.org

1, 1, 5, 25, 145, 905, 5941, 40433, 282721, 2018897, 14661349, 107945993, 803922289, 6045458905, 45840518933, 350100674785, 2690717983169, 20794719218593, 161502488175557, 1259855507859193, 9867012143508305, 77554946281194793, 611575725258403061

Offset: 0

Seiichi Manyama, Oct 04 2023

nonn

Cf. A364475, A366200, A366222.
Cf. A002478, A073155.
Cf. A366176, A366434.

nmax = 22; A[_] = 1;
Do[A[x_] = 1 + x*(1 + x)^2*A[x]^3 + O[x]^(nmax+1) // Normal, {nmax+1}];
CoefficientList[A[x], x] (* Jean-François Alcover, Mar 03 2024 *)

a(n) = sum(k=0, n, binomial(2*k, n-k)*binomial(3*k, k)/(2*k+1));

a(n) = Sum_{k=0..n} binomial(2*k,n-k) * binomial(3*k,k)/(2*k+1).

G.f.: A(x) = 1/B(-x) where B(x) is the g.f. of A366434.

A054856 Number of ways to tile a 4 X n region with 1 X 1, 2 X 2, 3 X 3 and 4 X 4 tiles.

Original entry on oeis.org

1, 1, 5, 13, 40, 117, 348, 1029, 3049, 9028, 26738, 79183, 234502, 694476, 2056692, 6090891, 18038173, 53420041, 158203433, 468519406, 1387520047, 4109140098, 12169216863, 36039131181, 106729873498, 316080480394, 936072224321

Offset: 0

Silvia Heubach (silvi(AT)cine.net), Apr 21 2000

It is easy to see that the g.f. for indecomposable tilings, i.e. those that cannot be split vertically into smaller tilings, is g=z+4*z^2+2*z^3+z^4+2*z^3/(1-z); then G.f.=1/(1-g). - Emeric Deutsch, Oct 16 2006

			a(2)=5 as there is one tiling of a 4 X 2 region with only 1 X 1 tiles, 3 tilings with exactly one 2 X 2 tile and 1 tiling with exactly two 2 X 2 tiles.

S. Heubach, Tiling an m-by-n area with squares of size up to k-by-k (m<=5), Congressus Numerantium 140 (1999), 43-64.
Index entries for linear recurrences with constant coefficients, signature (2,3,0,-1,-1).

Cf. A002478, A054857, A226547.

Column k=4 of A219924. - Alois P. Heinz, Dec 01 2012

a[0]:=1: a[1]:=1: a[2]:=5: a[3]:=13: a[4]:=40: for n from 5 to 26 do a[n]:=2*a[n-1]+3*a[n-2]-a[n-4]-a[n-5] od: seq(a[n],n=0..26); # Emeric Deutsch, Oct 16 2006

f[ A_ ] := Module[ {til = A, sum}, sum = 2* Apply[ Plus, Drop[ til, -4 ] ]; AppendTo[ til, A[ [ -1 ] ] + 4A[ [ -2 ] ] + 4A[ [ -3 ] ] + 3A[ [ -4 ] ] + sum ] ]; NumOfTilings[ n_ ] := Nest[ f, {1, 1, 5, 13}, n - 2 ]; NumOfTilings[ 30 ]

a(n) = a(n-1)+4*a(n-2)+4*a(n-3)+3*a(n-4)+2*( a(n-5)+a(n-6)+...+a(0)), a(0)=a(1)=1, a(2)=5, a(3)=13

a(n) = 2*a(n-1)+3*a(n-2)-a(n-4)-a(n-5). G.f.=(1-z)/((1+z)*(1-3*z+z^4)). - Emeric Deutsch, Oct 16 2006

A078039 Expansion of (1 - x)/(1 + x - 2*x^2 + x^3).

Original entry on oeis.org

1, -2, 4, -9, 19, -41, 88, -189, 406, -872, 1873, -4023, 8641, -18560, 39865, -85626, 183916, -395033, 848491, -1822473, 3914488, -8407925, 18059374, -38789712, 83316385, -178955183, 384377665, -825604416, 1773314929, -3808901426, 8181135700, -17572253481, 37743426307, -81069068969

Offset: 0

N. J. A. Sloane, Nov 17 2002

The repeated substitution 0 -> {0,1,2}, 1 -> {0,1,2,3}, 2 -> {0,1}, 3 -> {0,1,2}, starting on list {0} and flattening at each step { {sequence1}, {sequence2}, ...} to {sequence1, sequence2, ...} generates a list after n steps with length = a(n). - Wouter Meeussen, Mar 06 2004

Sequence is identical to its second differences negated, minus the first 3 terms. - Paul Curtz, Feb 10 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (-1,2,-1).

Cf. A002478.

[n le 3 select (-2)^(n-1) else -Self(n-1) +2*Self(n-2) -Self(n-3): n in [1..41]]; // G. C. Greubel, Jan 24 2023

LinearRecurrence[{-1,2,-1}, {1,-2,4}, 41] (* G. C. Greubel, Jan 24 2023 *)

Vec( (1-x)/(1+x-2*x^2+x^3)+O(x^99)) \\ Charles R Greathouse IV, Sep 23 2012

my(p= Mod('x,'x^3+'x^2-2*'x+1)); a(n) = vecsum(Vec(lift(p^(n+4)))); \\ Kevin Ryde, Jan 28 2023

@CachedFunction
def a(n): # a = A078039
    if(n<3): return (1,-2,4)[n]
    else: return -a(n-1) + 2*a(n-2) - a(n-3)
[a(n) for n in range(41)] # G. C. Greubel, Jan 24 2023

a(n) = -a(n-1) + 2*a(n-2) - a(n-3). - Paul Curtz, Feb 10 2008

a(n) = (-1)^n * (A002478(n) + A002478(n+1)). - Ralf Stephan, Aug 19 2013

cp's OEIS Frontend

A001333 Pell-Lucas numbers: numerators of continued fraction convergents to sqrt(2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Sage

Sage

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

A291728 p-INVERT of (1,0,1,0,0,0,0,...), where p(S) = 1 - S - S^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A219924 Number A(n,k) of tilings of a k X n rectangle using integer-sided square tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A228285 T(n,k) = Number of n X k binary arrays with top left value 1 and no two ones adjacent horizontally, vertically or nw-se diagonally.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A063967 Triangle read by rows, T(n,k) = T(n-1,k) + T(n-2,k) + T(n-1,k-1) + T(n-2,k-1) and T(0,0) = 1.

Views

Author

A366221 G.f. A(x) satisfies A(x) = 1 + x(1 + x)^2A(x)^3.