A005807 -id:A005807 - cp's OEIS frontend

A001906 F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n-1) - a(n-2).

0, 1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, 2178309, 5702887, 14930352, 39088169, 102334155, 267914296, 701408733, 1836311903, 4807526976, 12586269025, 32951280099, 86267571272, 225851433717, 591286729879, 1548008755920

Offset: 0

N. J. A. Sloane

Apart from initial term, same as A088305.
Second column of array A102310 and of A028412.
Numbers k such that 5*k^2 + 4 is a square. - Gregory V. Richardson, Oct 13 2002
Apart from initial terms, also Pisot sequences E(3,8), P(3,8), T(3,8). See A008776 for definitions of Pisot sequences.
Binomial transform of A000045. - Paul Barry, Apr 11 2003
Number of walks of length 2n+1 in the path graph P_4 from one end to the other one. Example: a(2)=3 because in the path ABCD we have ABABCD, ABCBCD and ABCDCD. - Emeric Deutsch, Apr 02 2004
Simplest example of a second-order recurrence with the sixth term a square.
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 3. - Lekraj Beedassy, Jun 11 2004
a(n) (for n > 0) is the smallest positive integer that cannot be created by summing at most n values chosen among the previous terms (with repeats allowed). - Andrew Weimholt, Jul 20 2004
All nonnegative integer solutions of Pell equation b(n)^2 - 5*a(n)^2 = +4 together with b(n) = A005248(n), n >= 0. - Wolfdieter Lang, Aug 31 2004
a(n+1) is a Chebyshev transform of 3^n (A000244), where the sequence with g.f. G(x) is sent to the sequence with g.f. (1/(1+x^2))G(x/(1+x^2)). - Paul Barry, Oct 25 2004
a(n) is the number of distinct products of matrices A, B, C, in (A+B+C)^n where commutator [A,B] = 0 but C does not commute with A or B. - Paul D. Hanna and Max Alekseyev, Feb 01 2006
Number of binary words with exactly k-1 strictly increasing runs. Example: a(3)=F(6)=8 because we have 0|0,1|0,1|1,0|01,01|0,1|01,01|1 and 01|01. Column sums of A119900. - Emeric Deutsch, Jul 23 2006
See Table 1 on page 411 of Lukovits and Janezic paper. - Parthasarathy Nambi, Aug 22 2006
Inverse: With phi = (sqrt(5) + 1)/2, log_phi((sqrt(5) a(n) + sqrt(5 a(n)^2 + 4))/2) = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007
[1,3,8,21,55,144,...] is the Hankel transform of [1,1,4,17,75,339,1558,...](see A026378). - Philippe Deléham, Apr 13 2007
The Diophantine equation a(n) = m has a solution (for m >= 1) if and only if floor(arcsinh(sqrt(5)*m/2)/log(phi)) <> floor(arccosh(sqrt(5)*m/2)/log(phi)) where phi is the golden ratio. An equivalent condition is A130259(m) = A130260(m). - Hieronymus Fischer, May 25 2007
a(n+1) = AB^(n)(1), n >= 0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 1=`1`, 3=`10`, 8=`100`, 21=`1000`, ..., in Wythoff code.
Equals row sums of triangles A140069, A140736 and A140737. - Gary W. Adamson, May 25 2008
a(n) is also the number of idempotent order-preserving partial transformations (of an n-element chain) of width n (width(alpha) = max(Im(alpha))). Equivalently, it is the number of idempotent order-preserving full transformations (of an n-element chain). - Abdullahi Umar, Sep 08 2008
a(n) is the number of ways that a string of 0,1 and 2 of size (n-1) can be arranged with no 12-pairs. - Udita Katugampola, Sep 24 2008
Starting with offset 1 = row sums of triangle A175011. - Gary W. Adamson, Apr 03 2010
As a fraction: 1/71 = 0.01408450... or 1/9701 = 0.0001030821.... - Mark Dols, May 18 2010
Sum of the products of the elements in the compositions of n (example for n=3: the compositions are 1+1+1, 1+2, 2+1, and 3; a(3) = 1*1*1 + 1*2 + 2*1 + 3 = 8). - Dylon Hamilton, Jun 20 2010, Geoffrey Critzer, Joerg Arndt, Dec 06 2010
a(n) relates to regular polygons with even numbers of edges such that Product_{k=1..(n-2)/2} (1 + 4*cos^2 k*Pi/n) = even-indexed Fibonacci numbers with a(n) relating to the 2*n-gons. The constants as products = roots to even-indexed rows of triangle A152063. For example: a(5) = 55 satisfies the product formula relating to the 10-gon. - Gary W. Adamson, Aug 15 2010
Alternatively, product of roots to x^4 - 12x^3 + 51x^2 - 90x + 55, (10th row of triangle A152063) = (4.618...)*(3.618...)*(2.381...)*(1.381...) = 55. - Gary W. Adamson, Aug 15 2010
a(n) is the number of generalized compositions of n when there are i different types of i, (i=1,2,...). - Milan Janjic, Aug 26 2010
Starting with "1" = row sums of triangle A180339, and eigensequence of triangle A137710. - Gary W. Adamson, Aug 28 2010
a(2) = 3 is the only prime.
Number of nonisomorphic graded posets with 0 and uniform hasse graph of rank n > 0, with exactly 2 elements of each rank level above 0. (Uniform used in the sense of Retakh, Serconek, and Wilson.  Graded used in Stanley's sense that every maximal chain has the same length n.) - David Nacin, Feb 13 2012
Pisano period lengths: 1, 3, 4, 3, 10, 12, 8, 6, 12, 30, 5, 12, 14, 24, 20, 12, 18, 12, 9, 30, ... - R. J. Mathar, Aug 10 2012
Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy + 1. - Michel Lagneau, Feb 01 2014
For n >= 1, a(n) equals the number of 01-avoiding words of length n-1 on alphabet {0,1,2}. - Milan Janjic, Jan 25 2015
With a(0) = 0, for n > 1, a(n) is the smallest number not already in the sequence such that a(n)^2 - a(n-1)^2 is a Fibonacci number. - Derek Orr, Jun 08 2015
Let T be the tree generated by these rules: 0 is in T, and if p is in T, then p + 1 is in T and x*p is in T and y*p is in T. The n-th generation of T consists of A001906(n) polynomials, for n >= 0. - Clark Kimberling, Nov 24 2015
For n > 0, a(n) = exactly the maximum area of a quadrilateral with sides in order of lengths F(n), F(n), L(n), and L(n) with L(n)=A000032(n). - J. M. Bergot, Jan 20 2016
a(n) = twice the area of a triangle with vertices at (L(n+1), L(n+2)), (F(n+1), F(n+1)), and (L(n+2), L(n+1)), with L(n)=A000032(n). - J. M. Bergot, Apr 20 2016
Except for the initial 0, this is the p-INVERT of (1,1,1,1,1,...) for p(S) = 1 - S - S^2; see A291000. - Clark Kimberling, Aug 24 2017
a(n+1) is the number of spanning trees of the graph T_n, where T_n is a sequence of n triangles, where adjacent triangles share an edge. - Kevin Long, May 07 2018
a(n) is the number of ways to partition [n] such that each block is a run of consecutive numbers, and each block has a fixed point, e.g., for n=3, 12|3 with 1 and 3 as fixed points is valid, but 13|2 is not valid as 1 and 3 do not form a run. Consequently, a(n) also counts the spanning trees of the graph given by taking a path with n vertices and adding another vertex adjacent to all of them. - Kevin Long, May 11 2018
From Wolfdieter Lang, May 31 2018: (Start)
The preceding comment can be paraphrased as follows. a(n) is the row sum of the array A305309 for n >= 1. The array A305309(n, k) gives the sum of the products of the block lengths of the set partition of [n] := {1, 2, ..., n} with A048996(n, k) blocks of consecutive numbers, corresponding to the compositions obtained from the k-th partition of n in Abramowitz-Stegun order. See the comments and examples at A305309.
{a(n)} also gives the infinite sequence of nonnegative numbers k for which k * ||k*phi|| < 1/sqrt(5), where the irrational number phi = A001622 (golden section), and ||x|| is the absolute value of the difference between x and the nearest integer. See, e.g., the Havil reference, pp. 171-172. (End)
This Chebyshev sequence a(n) = S(n-1, 3) (see a formula below) is related to the bisection of Fibonacci sequences {F(a,b;n)}{n>=0} with input F(a,b;0) = a and F(a,b;1) = b, by F(a,b;2*k) = (a+b)*S(k-1, 3) - a*S(k-2, 3) and F(a,b;2*k+1) = b*S(k, 3) + (a-b)*S(k-1, 3), for k >= 0, and S(-2, 3) = -1. Proof via the o.g.f.s GFeven(a,b,t) = (a - t*(2*a-b))/(1 - 3*t + t^2) and GFodd(a,b,t) = (b + t*(a-b))/(1 - 3*t + t^2). The special case a = 0, b = 1 gives back F(2*k) = S(k-1, 3) = a(k). - _Wolfdieter Lang, Jun 07 2019
a(n) is the number of tilings of two n X 1 rectangles joined orthogonally at a common end-square (so to have 2n-1 squares in a right-angle V shape) with only 1 X 1 and 2 X 1 tiles. This is a consequence of F(2n) = F(n+1)*F(n) + F(n)*F(n-1). - Nathaniel Gregg, Oct 10 2021
These are the denominators of the upper convergents to the golden ratio, tau; they are also the numerators of the lower convergents (viz. 1/1 < 3/2 < 8/5 < 21/13 < ... < tau < ... 13/8 < 5/3 < 2/1). - Clark Kimberling, Jan 02 2022
For n > 1, a(n) is the smallest Fibonacci number of unit equilateral triangle tiles needed to make an isosceles trapezoid of height F(n) triangles. - Kiran Ananthpur Bacche, Sep 01 2024

			G.f. = x + 3*x^2 + 8*x^3 + 21*x^4 + 55*x^5 + 144*x^6 + 377*x^7 + 987*x^8 + ...
a(3) = 8 because there are exactly 8 idempotent order-preserving full transformations on a 3-element chain, namely: (1,2,3)->(1,1,1),(1,2,3)->(2,2,2),(1,2,3)->(3,3,3),(1,2,3)->(1,1,3),(1,2,3)->(2,2,3),(1,2,3)->(1,2,2),(1,2,3)->(1,3,3),(1,2,3)->(1,2,3)-mappings are coordinate-wise. - _Abdullahi Umar_, Sep 08 2008

Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 78-79. Zentralblatt MATH, Zbl 1097.11516.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 2,5,6,14,33,55.
R. J. Douglas, Tournaments that admit exactly one Hamiltonian cycle, Proc. London Math. Soc., 21 (1970), 716-730.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
A. Gerardin, Reply to Query 4389, L'Intermédiaire des Mathématiciens, 22 (1915), 23.
Julian Havil, The Irrationals, Princeton University Press, Princeton and Oxford, 2012, pp. 171-172.
Howie, J. M. Combinatorial and probabilistic results in transformation semigroups. Words, languages and combinatorics, II (Kyoto, 1992), 200--206, World Sci. Publ., River Edge, NJ, (1994).
Laradji, A. and Umar, A. Combinatorial results for semigroups of order-preserving full transformations. Semigroup Forum 72 (2006), 51-62.
I. Lukovits, A. Graovac, E. Kalman, G. Kaptay, P. Nagy, S. Nikolic, J. Sytchev and N. Trinajstich, "Nanotubes: Number of Kekulé Structures and Aromaticity", J. Chem. Inf. Comput. Sci, vol. 43 (2003), pp. 609-614. See Equation 6 on page 611.
T. Mansour, M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.
H. Mathieu, Query 3932, L'Intermédiaire des Mathématiciens, 18 (1911), 222. - N. J. A. Sloane, Mar 08 2022
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 101.
Paulo Ribenboim, Primes in Lucas sequences (Chap 4), in 'My Numbers, My Friends', Springer-Verlag 2000 NY, page 27.
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. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.

Indranil Ghosh, Table of n, a(n) for n = 0..2388 (terms 0..200 from T. D. Noe)
Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, Colored compositions, Invert operator and elegant compositions with the "black tie", Discrete Math. 335 (2014), 1--7. MR3248794.
Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, Polynomial sequences on quadratic curves, Integers, Vol. 15, 2015, #A38.
K. Andersen, L. Carbone, and D. Penta, Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields, Journal of Number Theory and Combinatorics, Vol 2, No. 3 pp 245-278, 2011. See Section 9.
Andrei Asinowski and Michaela A. Polley, Patterns in rectangulations. Part I: T-like patterns, inversion sequence classes I(010, 101, 120, 201) and I(011, 201), and rushed Dyck paths, arXiv:2501.11781 [math.CO], 2025. See p. 26.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Paul Barry, The Triple Riordan Group, arXiv:2412.05461 [math.CO], 2024. See pp. 5, 10.
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
Raghavendra Bhat, Cristian Cobeli, and Alexandru Zaharescu, Filtered rays over iterated absolute differences on layers of integers, arXiv:2309.03922 [math.NT], 2023. See page 16.
Matthew Blair, Rigoberto Flórez, and Antara Mukherjee, Honeycombs in the Pascal triangle and beyond, arXiv:2203.13205 [math.HO], 2022. See p. 5.
Zbigniew R. Bogdanowicz, Formulas for the Number of Spanning Trees in a Fan, Appl. Math. Sci. (2008) Vol. 2, No. 16, 781-786.
A. Bremner and N. Tzanakis, Lucas sequences whose 12th or 9th term is a square, arXiv:math/0405306 [math.NT], 2004.
David Broadhurst, Multiple Landen values and the tribonacci numbers, arXiv:1504.05303 [hep-th], 2015.
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
Marc Chamberland and Christopher French, Generalized Catalan Numbers and Generalized Hankel Transformations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.1.
A. Collins et al., Binary words, n-color compositions and bisection of the Fibonacci numbers, Fib. Quarterly, 51 (2013), 130-136.
Aleksandar Cvetkovic, Predrag Rajkovic and Milos Ivkovic, Catalan Numbers, the Hankel Transform and Fibonacci Numbers, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.3
Tomislav Doslic, Planar polycyclic graphs and their Tutte polynomials, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607. See Cor. 3.7(e).
Sergio Falcon, Relationships between Some k-Fibonacci Sequences, Applied Mathematics, 2014, 5, 2226-2234.
Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832. doi:10.4134/CKMS.2013.28.4.827.
Sergio Falcon, Iterated Binomial Transforms of the k-Fibonacci Sequence, British Journal of Mathematics & Computer Science, 4 (22): 2014.
R. Flórez, R. A. Higuita, and A. Mukherjee, Alternating Sums in the Hosoya Polynomial Triangle, Article 14.9.5 Journal of Integer Sequences, Vol. 17 (2014).
Achille Frigeri, A note on Fibonacci number of even index, arXiv:1705.08305 [math.NT], 2017.
M. R. Garey, On enumerating tournaments that admit exactly one Hamiltonian circuit, J. Combin. Theory, B 13 (1972), 266-269.
Dale Gerdemann, Fractal images from (3,-1) recursion, YouTube Video, Oct 30 2014.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013), 13.4.5.
A. Gougenheim, About the linear sequence of integers such that each term is the sum of the two preceding Part 1 Part 2, Fib. Quart., 9 (1971), 277-295, 298.
Y-h. Guo, Some n-Color Compositions, J. Int. Seq. 15 (2012) 12.1.2, eq (2).
Edyta Hetmaniok, Bozena Piatek, and Roman Wituła, Binomials Transformation Formulae of Scaled Fibonacci Numbers, Open Math. 15 (2017), 477-485.
A. F. Horadam, Special Properties of the Sequence W(n){a,b; p,q}, Fib. Quart., Vol. 5, No. 5 (1967), pp. 424-434. Case a=0,b=1; p=3, q=-1.
J. M. Howie, Products of idempotents in certain semigroups of transformations, Proc. Edinburgh Math. Soc. 17 (1971), 223-236.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 147 [broken link].
Milan Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
J. Jina and P. Trojovsky, On determinants of some tridiagonal matrices connected with Fibonacci numbers, International Journal of Pure and Applied Mathematics 88:4 (2013), 569-575.
Tanya Khovanova, Recursive Sequences
E. Kilic, Y. T. Ulutas, and N. Omur, A Formula for the Generating Functions of Powers of Horadam's Sequence with Two Additional Parameters, J. Int. Seq. 14 (2011) #11.5.6, Table 1, k=t=1.
Seong Ju Kim, R. Stees, and L. Taalman, Sequences of Spiral Knot Determinants, Journal of Integer Sequences, Vol. 19 (2016), #16.1.4.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
Markus Kuba and Alois Panholzer, Enumeration formulas for pattern restricted Stirling permutations, Discrete Math. 312(21) (2012), 3179--3194. MR2957938. - From _N. J. A. Sloane_, Sep 25 2012
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408-419. Eq. (44) lhs, m=5.
Ioana-Claudia Lazăr, Lucas sequences in t-uniform simplicial complexes, arXiv:1904.06555 [math.GR], 2019.
I. Lukovits and D. Janezic, Enumeration of conjugated circuits in nanotubes, J. Chem. Inf. Comput. Sci., vol. 44 (2004) pp. 410-414.
G. Narang and A. K. Agarwal, Lattice paths and n-color compositions, Discr. Math., 308 (2008), 1732-1740.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Yun-Tak Oh, Hosho Katsura, Hyun-Yong Lee, and Jung Hoon Han, Proposal of a spin-one chain model with competing dimer and trimer interactions, arXiv:1709.01344 [cond-mat.str-el], 2017.
J. Pan, Multiple Binomial Transforms and Families of Integer Sequences, J. Int. Seq. 13 (2010), 10.4.2. Absolute values of F^(-2).
C. Pita, On s-Fibonomials, J. Int. Seq. 14 (2011) # 11.3.7.
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
V. Retakh, S. Serconek, and R. Wilson, Hilbert Series of Algebras Associated to Directed Graphs and Order Homology, arXiv:1010.6295 [math.RA], 2010-2011.
John Riordan, Letter to N. J. A. Sloane, Nov. 1970
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
J. Salas and A. D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial, J. Stat. Phys. 135 (2009) 279-373, arXiv:0711.1738. Mentions this sequence.
Luigi Santocanale, On discrete idempotent paths, arXiv:1906.05590 [math.LO], 2019.
N. J. A. Sloane, Transforms
Michael Somos, In the Elliptic Realm.
Ryan Stees, Sequences of Spiral Knot Determinants, Senior Honors Projects, Paper 84, James Madison Univ., May 2016.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.
Eric Weisstein's World of Mathematics, Fibonacci Hyperbolic Functions.
Roman Witula, Binomials transformation formulae of scaled Lucas numbers, Demonstratio Math. 46 (2013), 15-27.
Roman Witula and Damian Slota, delta-Fibonacci numbers, Appl. Anal. Discr. Math 3 (2009) 310-329, MR2555042
Index entries for "core" sequences
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (3,-1).
Index entries for two-way infinite sequences

Fibonacci A000045 = union of this sequence and A001519.
Cf. A000041, A000032, A001622, A048996, A052529, A055991, A078812, A305309, A058038 (pairwise products), A153386.
Inverse sequences A130259 and A130260.
Cf. A033888, A033890, A249450, A344212.

a001906 n = a001906_list !! n
a001906_list =
   0 : 1 : zipWith (-) (map (* 3) $ tail a001906_list) a001906_list
-- Reinhard Zumkeller, Oct 03 2011

[Fibonacci(2*n): n in [0..30]]; // Vincenzo Librandi, Sep 10 2014

with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S, card > 0), S=Sequence(U, card > 1), U=Sequence(Z, card >0)}, unlabeled]: seq(count(SeqSeqSeqL, size=n+1), n=0..28); # Zerinvary Lajos, Apr 04 2009
H := (n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4):
a := n -> `if`(n = 0, 0, H(2*n, 1, 1/2)):
seq(simplify(a(n)), n=0..30); # Peter Luschny, Sep 03 2019
A001906 := proc(n)
    combinat[fibonacci](2*n) ;
end proc:
seq(A001906(n),n=0..20) ; # R. J. Mathar, Jan 11 2024

f[n_] := Fibonacci[2n]; Array[f, 28, 0] (* or *)
LinearRecurrence[{3, -1}, {0, 1}, 28] (* Robert G. Wilson v, Jul 13 2011 *)
Take[Fibonacci[Range[0,60]],{1,-1,2}] (* Harvey P. Dale, May 23 2012 *)
Table[ ChebyshevU[n-1, 3/2], {n, 0, 30}] (* Jean-François Alcover, Jan 25 2013, after Michael Somos *)
CoefficientList[Series[(x)/(1 - 3x + x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Sep 10 2014 *)

makelist(fib(2*n),n,0,30); /* Martin Ettl, Oct 21 2012 */

numlib::fibonacci(2*n) $ n = 0..35; // Zerinvary Lajos, May 09 2008

{a(n) = fibonacci(2*n)}; /* Michael Somos, Dec 06 2002 */

{a(n) = subst( poltchebi(n+1)*4 - poltchebi(n)*6, x, 3/2)/5}; /* Michael Somos, Dec 06 2002 */

{a(n) = polchebyshev( n-1, 2, 3/2)}; /* Michael Somos Jun 18 2011 */

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

def a(n, adict={0:0, 1:1}):
    if n in adict:
        return adict[n]
    adict[n]=3*a(n-1) - a(n-2)
    return adict[n] # David Nacin, Mar 04 2012

[lucas_number1(n,3,1) for n in range(27)] # Zerinvary Lajos, Jun 25 2008

[fibonacci(2*n) for n in range(0, 28)] # Zerinvary Lajos, May 15 2009

G.f.: x / (1 - 3*x + x^2). -  Simon Plouffe in his 1992 dissertation
a(n) = 3*a(n-1) - a(n-2) = A000045(2*n).
a(n) = -a(-n).
a(n) = A060921(n-1, 0), n >= 1.
a(n) = sqrt((A005248(n)^2 - 4)/5).
a(n) = A007598(n) - A007598(n-2), n > 1.
a(n) = (ap^n - am^n)/(ap-am), with ap := (3+sqrt(5))/2, am := (3-sqrt(5))/2.
Invert transform of natural numbers: a(n) = Sum_{k=1..n} k*a(n-k), a(0) = 1. - Vladeta Jovovic, Apr 27 2001
a(n) = S(n-1, 3) with S(n, x) = U(n, x/2) Chebyshev's polynomials of the 2nd kind, see A049310.
a(n) = Sum_{k=0..n} binomial(n, k)*F(k). - Benoit Cloitre, Sep 03 2002
Limit_{n->infinity} a(n)/a(n-1) = 1 + phi = (3 + sqrt(5))/2. This sequence includes all of the elements of A033888 combined with A033890.
a(0)=0, a(1)=1, a(2)=3, a(n)*a(n-2) + 1 = a(n-1)^2. - Benoit Cloitre, Dec 06 2002
a(n) = n + Sum_{k=0..n-1} Sum_{i=0..k} a(i) = n + A054452(n). - Benoit Cloitre, Jan 26 2003
a(n) = Sum_{k=1..n} binomial(n+k-1, n-k). - Vladeta Jovovic, Mar 23 2003
E.g.f.: (2/sqrt(5))*exp(3*x/2)*sinh(sqrt(5)*x/2). - Paul Barry, Apr 11 2003
Second diagonal of array defined by T(i, 1) = T(1, j) = 1, T(i, j) = Max(T(i-1, j) + T(i-1, j-1); T(i-1, j-1) + T(i, j-1)). - Benoit Cloitre, Aug 05 2003
a(n) = F(n)*L(n) = A000045(n)*A000032(n). - Lekraj Beedassy, Nov 17 2003
F(2n+2) = 1, 3, 8, ... is the binomial transform of F(n+2). - Paul Barry, Apr 24 2004
Partial sums of A001519(n). - Lekraj Beedassy, Jun 11 2004
a(n) = Sum_{i=0..n-1} binomial(2*n-1-i, i)*5^(n-i-1)*(-1)^i. - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
a(n) = Sum_{k=0..n} binomial(n+k, n-k-1) = Sum_{k=0..n} binomial(n+k, 2k+1).
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*(-1)^k*3^(n-2*k). - Paul Barry, Oct 25 2004
a(n) = (n*L(n) - F(n))/5 = Sum_{k=0..n-1} (-1)^n*L(2*n-2*k-1).
The i-th term of the sequence is the entry (1, 2) in the i-th power of the 2 X 2 matrix M = ((1, 1), (1, 2)). - Simone Severini, Oct 15 2005
Computation suggests that this sequence is the Hankel transform of A005807. The Hankel transform of {a(n)} is Det[{{a(1), ..., a(n)}, {a(2), ..., a(n+1)}, ..., {a(n), ..., a(2n-1)}}]. - John W. Layman, Jul 21 2000
a(n+1) = (A005248(n+1) - A001519(n))/2. - Creighton Dement, Aug 15 2004
a(n+1) = Sum_{i=0..n} Sum_{j=0..n} binomial(n-i, j)*binomial(n-j, i). - N. J. A. Sloane, Feb 20 2005
a(n) = (2/sqrt(5))*sinh(2*n*psi), where psi:=log(phi) and phi=(1+sqrt(5))/2. - Hieronymus Fischer, Apr 24 2007
a(n) = ((phi+1)^n - A001519(n))/phi with phi=(1+sqrt(5))/2. - Reinhard Zumkeller, Nov 22 2007
Row sums of triangle A135871. - Gary W. Adamson, Dec 02 2007
a(n)^2 = Sum_{k=1..n} a(2*k-1). This is a property of any sequence S(n) such that S(n) = B*S(n-1) - S(n-2) with S(0) = 0 and S(1) = 1 including {0,1,2,3,...} where B = 2. - Kenneth J Ramsey, Mar 23 2008
a(n) = 1/sqrt(5)*(phi^(2*n+2) - phi^(-2*n-2)), where phi = (1+sqrt(5))/2, the golden ratio. - Udita Katugampola (SIU), Sep 24 2008
If p[i] = i 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, May 02 2010
If p[i] = Stirling2(i,2) and if A is the 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-1) = det(A). - Milan Janjic, May 08 2010
a(n) = F(2*n+10) mod F(2*n+5).
a(n) = 1 + a(n-1) + Sum_{i=1..n-1} a(i), with a(0)=0. - Gary W. Adamson, Feb 19 2011
a(n) is equal to the permanent of the (n-1) X (n-1) Hessenberg matrix with 3's along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else. - John M. Campbell, Jun 09 2011
a(n), n > 1 is equal to the determinant of an (n-x) X (n-1) tridiagonal matrix with 3's in the main diagonal, 1's in the super and subdiagonals, and the rest 0's. - Gary W. Adamson, Jun 27 2011
a(n) = b such that Integral_{x=0..Pi/2} sin(n*x)/(3/2-cos(x)) dx = c + b*log(3). - Francesco Daddi, Aug 01 2011
a(n+1) = Sum_{k=0..n} A101950(n,k)*2^k. - Philippe Deléham, Feb 10 2012
G.f.: A(x) = x/(1-3*x+x^2) = G(0)/sqrt(5); where G(k)= 1 -(a^k)/(1 - b*x/(b*x - 2*(a^k)/G(k+1))), a = (7-3*sqrt(5))/2, b = 3+sqrt(5), if |x|<(3-sqrt(5))/2 = 0.3819660...; (continued fraction 3 kind, 3-step ). - Sergei N. Gladkovskii, Jun 25 2012
a(n) = 2^n*b(n;1/2) = -b(n;-1), where b(n;d), n=0,1,...,d, denote the delta-Fibonacci numbers defined in comments to A000045 (see also Witula's et al. papers). - Roman Witula, Jul 12 2012
Product_{n>=1} (1 + 1/a(n)) = 1 + sqrt(5). - Peter Bala, Dec 23 2012
Product_{n>=2} (1 - 1/a(n)) = (1/6)*(1 + sqrt(5)). - Peter Bala, Dec 23 2012
G.f.: x/(1-2*x) + x^2/(1-2*x)/(Q(0)-x) where Q(k) = 1 - x/(x*k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Feb 23 2013
G.f.: G(0)/2 - 1, where G(k) = 1 + 1/( 1 - x/(x + (1-x)^2/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 16 2013
G.f.: x*G(0)/(2-3*x), where G(k) = 1 + 1/( 1 - x*(5*k-9)/(x*(5*k-4) - 6/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 17 2013
Sum_{n>=1} 1/(a(n) + 1/a(n)) = 1. Compare with A001519, A049660 and A049670. - Peter Bala, Nov 29 2013
a(n) = U(n-1,3/2) where U(n-1,x) is Chebyshev polynomial of the second kind. - Milan Janjic, Jan 25 2015
The o.g.f. A(x) satisfies A(x) + A(-x) + 6*A(x)*A(-x) = 0. The o.g.f. for A004187 equals -A(sqrt(x))*A(-sqrt(x)). - Peter Bala, Apr 02 2015
For n > 1, a(n) = (3*F(n+1)^2 + 2*F(n-2)*F(n+1) - F(n-2)^2)/4. - J. M. Bergot, Feb 16 2016
For n > 3, a(n) = floor(MA) - 4 for n even and floor(MA) + 5 for n odd.  MA is the maximum area of a quadrilateral with lengths of sides in order L(n), L(n), F(n-3), F(n+3), with L(n)=A000032(n). The ratio of the longer diagonal to the shorter approaches 5/3. - J. M. Bergot, Feb 16 2016
a(n+1) = Sum_{j=0..n} Sum_{k=0..j} binomial(n-j,k)*binomial(j,k)*2^(j-k). - Tony Foster III, Sep 18 2017
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i,k-i). - Wesley Ivan Hurt, Sep 21 2017
a(n) = Sum_{k=1..A000041(n)} A305309(n, k), n >= 1. Also row sums of triangle A078812.- Wolfdieter Lang, May 31 2018
a(n) = H(2*n, 1, 1/2) for n > 0 where H(n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4). - Peter Luschny, Sep 03 2019
Sum_{n>=1} 1/a(n) = A153386. - Amiram Eldar, Oct 04 2020
a(n) = A249450(n) + 2. - Leo Tavares, Oct 10 2021
a(n) = -2/(sqrt(5)*tan(2*arctan(phi^(2*n)))), where phi = A001622 is the golden ratio. - Diego Rattaggi, Nov 21 2021
a(n) = sinh(2*n*arcsinh(1/2))/sqrt(5/4). - Peter Luschny, May 21 2022
From Amiram Eldar, Dec 02 2024: (Start)
Product_{n>=1} (1 - (-1)^n/a(n)) = 1 + 1/sqrt(5) (A344212).
Product_{n>=2} (1 + (-1)^n/a(n)) = (5/6) * (1 + 1/sqrt(5)). (End)
a(n) = Sum_{k>=0} Fibonacci(2*n*k)/(Lucas(2*n)^(k+1)). - Diego Rattaggi, Jan 12 2025
Sum_{n>=0} a(n)/3^n = 3. - Diego Rattaggi, Jan 20 2025

A001654 Golden rectangle numbers: F(n) * F(n+1), where F(n) = A000045(n) (Fibonacci numbers).

Original entry on oeis.org

0, 1, 2, 6, 15, 40, 104, 273, 714, 1870, 4895, 12816, 33552, 87841, 229970, 602070, 1576239, 4126648, 10803704, 28284465, 74049690, 193864606, 507544127, 1328767776, 3478759200, 9107509825, 23843770274, 62423800998, 163427632719, 427859097160, 1120149658760

Offset: 0

N. J. A. Sloane

a(n)/A007598(n) ~= golden ratio, especially for larger n. - Robert Happelberg (roberthappelberg(AT)yahoo.com), Jul 25 2005
Let phi be the golden ratio (cf. A001622). Then 1/phi = phi - 1 = Sum_{n>=1} (-1)^(n-1)/a(n), an alternating infinite series consisting solely of unit fractions. - Franz Vrabec, Sep 14 2005
a(n+2) is the Hankel transform of A005807 aerated. - Paul Barry, Nov 04 2008
A more exact name would be: Golden convergents to rectangle numbers. These rectangles are not actually golden (ratio of sides is not phi) but are golden convergents (sides are numerator and denominator of convergents in the continued fraction expansion of phi, whence ratio of sides converges to phi). - Daniel Forgues, Nov 29 2009
The Kn4 sums (see A180662 for definition) of the "Races with Ties" triangle A035317 lead to this sequence. - Johannes W. Meijer, Jul 20 2011
Numbers m such that m(5m+2)+1 or m(5m-2)+1 is a square. - Bruno Berselli, Oct 22 2012
In pairs, these numbers are important in finding binomial coefficients that appear in at least six places in Pascal's triangle. For instance, the pair (m,n) = (40, 104) finds the numbers binomial(n-1,m) = binomial(n,m-1). Two additional numbers are found on the other side of the triangle. The final two numbers appear in row binomial(n-1,m). See A003015. - T. D. Noe, Mar 13 2013
For n>1, a(n) is one-half the area of the trapezoid created by the four points (F(n),L(n)), (L(n),F(n)), (F(n+1), L(n+1)), (L(n+1), F(n+1)) where F(n) = A000045(n) and L(n) = A000032(n). - J. M. Bergot, May 14 2014
[Note on how to calculate: take the two points (a,b) and (c,d) with aa(n) = A067962(n-1) / A067962(n-2), n > 1. - Reinhard Zumkeller, Sep 24 2015
Can be obtained (up to signs) by setting x = F(n)/F(n+1) in g.f. for Fibonacci numbers - see Pongsriiam. - N. J. A. Sloane, Mar 23 2017

			G.f. = x + 2*x^2 + 6*x^3 + 15*x^4 + 40*x^5 + 104*x^6 + 273*x^7 + 714*x^8 + ...

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 9.
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).

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
R. C. Alperin, A nonlinear recurrence and its relations to Chebyshev polynomials, Fib. Q., Vol. 58, No. 2 (2020), 140-142.
Paul Barry, Symmetric Third-Order Recurring Sequences, Chebyshev Polynomials, and Riordan Arrays, JIS 12 (2009) 09.8.6.
A. Brousseau, A sequence of power formulas, Fib. Quart., 6 (1968), 81-83.
Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972. See p. 17.
Ömer Egecioglu, Elif Saygi, and Zülfükar Saygi, The Mostar index of Fibonacci and Lucas cubes, arXiv:2101.04740 [math.CO], 2021. Mentions this sequence.
Shalosh B. Ekhad and Doron Zeilberger, Automatic Counting of Tilings of Skinny Plane Regions, arXiv preprint arXiv:1206.4864 [math.CO], 2012.
Sergio Falcon, On the Sequences of Products of Two k-Fibonacci Numbers, American Review of Mathematics and Statistics, March 2014, Vol. 2, No. 1, pp. 111-120.
Dale Gerdemann, Golden Ratio Base Digit Patterns for Columns of the Fibonomial Triangle, "Another interesting pattern is for Golden Rectangle Numbers A001654. I made a short video illustrating this pattern, along with other columns of the Fibonomial Triangle A010048".
Jonny Griffiths and Martin Griffiths, Fibonacci-related sequences via iterated QRT maps, Fib. Q., 51 (2013), 218-227.
James P. Jones and Péter Kiss, Representation of integers as terms of a linear recurrence with maximal index, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae, 25. (1998) pp. 21-37. See Lemma 4.1 p. 34.
Ronald Orozco López, Generating Functions of Generalized Simplicial Polytopic Numbers and (s,t)-Derivatives of Partial Theta Function, arXiv:2408.08943 [math.CO], 2024. See p. 11.
Ronald Orozco López, Simplicial d-Polytopic Numbers Defined on Generalized Fibonacci Polynomials, arXiv:2501.11490 [math.CO], 2025. See p. 6.
C. Pita, On s-Fibonomials, J. Int. Seq. 14 (2011) # 11.3.7.
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
Prapanpong Pongsriiam, Integral Values of the Generating Functions of Fibonacci and Lucas Numbers, College Math. J., 48 (No. 2 2017), pp 97ff.
M. Renault, Dissertation
Wikipedia, Illustration of 273 as a golden rectangle number.
Robert G. Wilson v, Letter to N. J. A. Sloane, circa 1993
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (2,2,-1).

Cf. A001655, A001656, A001657, A001658, A010048, A067962.
Cf. A005968, A005969, A098531, A098532, A098533, A119283, A128697.
Cf. A000071, A079472, A080145, A239798, A290565.
Bisection of A006498, A070550, A080239.
First differences of A064831.
Partial sums of A007598.

a001654 n = a001654_list !! n
a001654_list = zipWith (*) (tail a000045_list) a000045_list
-- Reinhard Zumkeller, Jun 08 2013

I:=[0,1,2]; [n le 3 select I[n] else 2*Self(n-1) + 2*Self(n-2) - Self(n-3): n in [1..30]]; // G. C. Greubel, Jan 17 2018

with(combinat): A001654:=n->fibonacci(n)*fibonacci(n+1):
seq(A001654(n), n=0..28); # Zerinvary Lajos, Oct 07 2007

LinearRecurrence[{2,2,-1}, {0,1,2}, 100] (* Vladimir Joseph Stephan Orlovsky, Jul 03 2011 *)
Times@@@Partition[Fibonacci[Range[0,30]],2,1] (* Harvey P. Dale, Aug 18 2011 *)
Accumulate[Fibonacci[Range[0, 30]]^2] (* Paolo Xausa, May 31 2024 *)

A001654(n)=fibonacci(n)*fibonacci(n+1);

b(n, k)=prod(j=1, k, fibonacci(n+j)/fibonacci(j));
vector(30, n, b(n-1, 2))  \\ Joerg Arndt, May 08 2016

from sympy import fibonacci as F
def a(n): return F(n)*F(n + 1)
[a(n) for n in range(101)] # Indranil Ghosh, Aug 03 2017

from math import prod
from gmpy2 import fib2
def A001654(n): return prod(fib2(n+1)) # Chai Wah Wu, May 19 2022

a(n) = A010048(n+1, 2) = Fibonomial(n+1, 2).
a(n) = A006498(2*n-1).
a(n) = a(n - 1) + A007598(n) = a(n - 1) + A000045(n)^2 = Sum_{j <= n} Fibonacci(j)^2. - Henry Bottomley, Feb 09 2001 [corrected by Ridouane Oudra, Apr 12 2025]
For n > 0, 1 - 1/a(n+1) = Sum_{k=1..n} 1/(F(k)*F(k+2)) where F(k) is the k-th Fibonacci number. - Benoit Cloitre, Aug 31 2002.
G.f.: x/(1-2*x-2*x^2+x^3) = x/((1+x)*(1-3*x+x^2)). (Simon Plouffe in his 1992 dissertation; see Comments to A055870),
a(n) = 3*a(n-1) - a(n-2) - (-1)^n = -a(-1-n).
Let M = the 3 X 3 matrix [1 2 1 / 1 1 0 / 1 0 0]; then a(n) = the center term in M^n *[1 0 0]. E.g., a(5) = 40 since M^5 * [1 0 0] = [64 40 25]. - Gary W. Adamson, Oct 10 2004
a(n) = Sum{k=0..n} Fibonacci(k)^2. The proof is easy. Start from a square (1*1). On the right side, draw another square (1*1). On the above side draw a square ((1+1)*(1+1)). On the left side, draw a square ((1+2)*(1+2)) and so on. You get a rectangle (F(n)*F(1+n)) which contains all the squares of side F(1), F(2), ..., F(n). - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Jun 19 2007
With phi = (1+sqrt(5))/2, a(n) = round((phi^(2*n+1))/5) = floor((1/2) + (phi^(2*n+1))/5), n >= 0. - Daniel Forgues, Nov 29 2009
a(n) = 2*a(n-1) + 2*a(n-2) - a(n-3), a(1)=1, a(2)=2, a(3)=6. - Sture Sjöstedt, Feb 06 2010
a(n) = (A002878(n) - (-1)^n)/5. - R. J. Mathar, Jul 22 2010
a(n) = 1/|F(n+1)/F(n) - F(n)/F(n-1)| where F(n) = Fibonacci numbers A000045. b(n) = F(n+1)/F(n) - F(n)/F(n-1): 1/1, -1/2, 1/6, -1/15, 1/40, -1/104, ...; c(n) = 1/b(n) = a(n)*(-1)^(n+1): 1, -2, 6, -15, 40, -104, ... (n=1,2,...). - Thomas Ordowski, Nov 04 2010
a(n) = (Fibonacci(n+2)^2 - Fibonacci(n-1)^2)/4. - Gary Detlefs, Dec 03 2010
Let d(n) = n mod 2, a(0)=0 and a(1)=1. For n > 1, a(n) = d(n) + 2*a(n-1) + Sum_{k=0..n-2} a(k). - L. Edson Jeffery, Mar 20 2011
From Tim Monahan, Jul 11 2011: (Start)
a(n+1) = ((2+sqrt(5))*((3+sqrt(5))/2)^n+(2-sqrt(5))*((3-sqrt(5))/2)^n+(-1)^n)/5.
a(n) = ((1+sqrt(5))*((3+sqrt(5))/2)^n+(1-sqrt(5))*((3-sqrt(5))/2)^n-2*(-1)^n)/10. (End)
From Wolfdieter Lang, Jul 21 2012: (Start)
a(n) = (2*A059840(n+2) - A027941(n))/3, n >= 0, with A059840(n+2) = Sum_{k=0..n} F(k)*F(k+2) and A027941(n) = A001519(n+1) - 1, n >= 0, where A001519(n+1) = F(2*n+1). (End)
a(n) = (-1)^n * Sum_{k=0..n} (-1)^k*F(2*k), n >= 0. - Wolfdieter Lang, Aug 11 2012
a(-1-n) = -a(n) for all n in Z. - Michael Somos, Sep 19 2014
0 = a(n)*(+a(n+1) - a(n+2)) + a(n+1)*(-2*a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Sep 19 2014
a(n) = (L(2*n+1) - (-1)^n)/5 with L(k) = A000032(k). - J. M. Bergot, Apr 15 2016
E.g.f.: ((3 + sqrt(5))*exp((5+sqrt(5))*x/2) - 2*exp((2*x)/(3+sqrt(5))+x) - 1 - sqrt(5))*exp(-x)/(5*(1 + sqrt(5))). - Ilya Gutkovskiy, Apr 15 2016
From Klaus Purath, Apr 24 2019: (Start)
a(n) = A061646(n) - Fibonacci(n-1)^2.
a(n) = (A061646(n+1) - A061646(n))/2. (End)
a(n) = A226205(n+1) + (-1)^(n+1). - Flávio V. Fernandes, Apr 23 2020
Sum_{n>=1} 1/a(n) = A290565. - Amiram Eldar, Oct 06 2020
Product_{n>=2} (1 + (-1)^n/a(n)) = phi^2/2 (A239798). - Amiram Eldar, Dec 02 2024
G.f.: x * exp( Sum_{k>=1} F(3*k)/F(k) * x^k/k ), where F(n) = A000045(n). - Seiichi Manyama, May 07 2025

Extended by Wolfdieter Lang, Jun 27 2000

A213275 Number A(n,k) of words w where each letter of the k-ary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 6, 3, 1, 1, 1, 24, 15, 7, 1, 1, 1, 120, 105, 106, 19, 1, 1, 1, 720, 945, 2575, 1075, 56, 1, 1, 1, 5040, 10395, 87595, 115955, 13326, 174, 1, 1, 1, 40320, 135135, 3864040, 19558470, 7364321, 188196, 561, 1, 1

Offset: 0

Alois P. Heinz, Jun 08 2012

The words counted by A(n,k) have length n*k.

			A(0,k) = A(n,0) = 1: the empty word.
A(n,1) = 1: (a)^n for alphabet {a}.
A(1,2) = 2: ab, ba for alphabet {a,b}.
A(1,3) = 6: abc, acb, bac, bca, cab, cba for alphabet {a,b,c}.
A(2,2) = 3: aabb, abab, baab.
A(2,3) = 15: aabbcc, aabcbc, aacbbc, ababcc, abacbc, abcabc, acabbc, acbabc, baabcc, baacbc, bacabc, bcaabc, caabbc, cababc, cbaabc.
A(3,2) = 7: aaabbb, aababb, aabbab, abaabb, ababab, baaabb, baabab.
Square array A(n,k) begins:
  1, 1,   1,      1,         1,             1,                 1, ...
  1, 1,   2,      6,        24,           120,               720, ...
  1, 1,   3,     15,       105,           945,             10395, ...
  1, 1,   7,    106,      2575,         87595,           3864040, ...
  1, 1,  19,   1075,    115955,      19558470,        4622269345, ...
  1, 1,  56,  13326,   7364321,    7236515981,    10915151070941, ...
  1, 1, 174, 188196, 586368681, 3745777177366, 40684710729862072, ...

Alois P. Heinz, Antidiagonals n = 0..20, flattened

Rows n=0-10 give: A000012, A000142, A001147, A213863, A213864, A213865, A213866, A213867, A213868, A213869, A213870.
Columns k=0+1, 2-10 give: A000012, A005807(n-1) for n>0, A213873, A213874, A213875, A213876, A213877, A213878, A213871, A213872.
Main diagonal gives A213862.
Cf. A213276.

A:= (n, k)-> b([n$k]):
b:= proc(l) option remember;
      `if`({l[]} minus {0}={}, 1, add(`if`(g(l, i),
       b(subsop(i=l[i]-1, l)), 0), i=1..nops(l)))
    end:
g:= proc(l, i) local j;
      if l[i]<1     then return false
    elif l[i]>1     then for j from i+1 to nops(l) do
      if l[i]<=l[j] then return false
    elif l[j]>0     then break
      fi od fi; true
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

a[n_, k_] := b[Array[n&, k]];
b[l_] := b[l] = If[l ~Complement~ {0} == {}, 1, Sum[If[g[l, i], b[ReplacePart[l, i -> l[[i]] - 1]], 0], {i, 1, Length[l]}]];
g[l_, i_] := Module[{j},
     If[l[[i]] < 1, Return[False],
     If[l[[i]] > 1, For[j = i+1, j <= Length[l], j++,
     If[l[[i]] <= l[[j]], Return[False],
     If[l[[j]] > 0, Break[]]]]]]; True];
Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 16 2013, translated from Maple *)

A274052 Number of factor-free Dyck words with slope 5/2 and length 7n.

Original entry on oeis.org

1, 3, 13, 94, 810, 7667, 76998, 805560, 8684533, 95800850, 1076159466, 12268026894, 141565916433, 1650395185407, 19409211522550, 229984643863260, 2743097412254490, 32907239462485422, 396793477697214450, 4806417317271974580, 58460150525944945840, 713685698665966837135, 8742060290902752902340

Offset: 0

Michael D. Weiner, Jun 08 2016

nonn

a(n) is the number of lattice paths (allowing only north and east steps) starting at (0,0) and ending at (2n,5n) that stay below the line y = 5/2x and also do not contain a proper subpath of smaller size.

			a(2) = 13 since there are 13 lattice paths (allowing only north and east steps) starting at (0,0) and ending at (4,10) that stay below the line y=5/2x and also do not contain a proper subpath of small size; e.g., EEENNNENNNNNNN is a factor-free Dyck word but ENNEENENNNNNNN contains the factor ENENNNN.

Cyril Banderier and Michael Wallner, Lattice paths of slope 2/5, 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO).
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On rational Dyck paths and the enumeration of factor-free Dyck words, arXiv:1606.02183 [math.CO], 2016.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On factor-free Dyck words with half-integer slope, arXiv:1804.11244 [math.CO], 2018.
P. Duchon, On the enumeration and generation of generalized Dyck words, Discrete Mathematics, 225 (2000), 121-135.

Factor-free Dyck words: A005807 (slope 3/2), A274244 (slope 7/2), A274256 (slope 9/2), A274257 (slope 4/3), A274259 (slope 7/3).

Cf. A293946, A322631.

Conjectural o.g.f.: Let E(x) = exp( Sum_{n >= 1} binomial(7*n, 2*n)*x^n/n ). Then A(x) = ( x/series reversion of x*E(x) )^(1/7) = 1 + 3*x + 13*x^2 + 94*x^3 + ... . Equivalently, [x^n]( A(x)^(7*n) ) = binomial(7*n, 2*n) for n = 0,1,2,... . - Peter Bala, Jan 01 2020

A089865 Permutation of natural numbers induced by Catalan Automorphism *A089865 acting on the parenthesizations/binary trees encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 11, 12, 13, 14, 15, 19, 20, 21, 16, 22, 17, 18, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 51, 52, 53, 54, 55, 56, 57, 58, 59, 42, 43, 60, 61, 62, 44, 63, 45, 46, 47, 64, 48, 49, 50, 65, 66, 67, 68, 69

Offset: 0

Antti Karttunen, Dec 20 2003

nonn

This bijection of binary trees is obtained when we apply bijection *A074679 to the left subtree and keep the right subtree intact.
....B...C.......A...B
.....\./.........\./
..A...x....-->....x...C.................A..().........()..A....
...\./.............\./...................\./....-->....\./.....
....x...D...........x...D.................x...C.........x...C..
.....\./.............\./...................\./...........\./...
......x...............x.....................x.............x....
...............................................................
Compare to A154121.
See "Catalan Automorphisms" OEIS-Wiki page for a detailed explanation how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Row 4207 of A089840. Inverse of A089866. a(n) = A069770(A154121(A069770(n))).

Number of cycles: A089844. Number of fixed-points: A005807 (prepended with two 1's). Max. cycle size: A089410. LCM of cycle sizes: A089845 (in each range limited by A014137 and A014138).

Further comments and constructive version of Scheme-implementation added by Antti Karttunen, Jun 04 2011

A071716 Expansion of (1+x^2C)C, where C = (1-(1-4x)^(1/2))/(2x) is g.f. for Catalan numbers, A000108.

Original entry on oeis.org

1, 1, 3, 7, 19, 56, 174, 561, 1859, 6292, 21658, 75582, 266798, 950912, 3417340, 12369285, 45052515, 165002460, 607283490, 2244901890, 8331383610, 31030387440, 115948830660, 434542177290, 1632963760974, 6151850548776

Offset: 0

N. J. A. Sloane, Jun 06 2002

nonn

a(n) is the number of lattice paths of n up steps and n down steps that start at the origin with an up step and do not cross the x-axis except possibly at (2n-2,0). - David Callan, Mar 14 2004

a(n) is the number of parking functions of size n avoiding the patterns 132, 213, 231, and 321. - Lara Pudwell, Apr 10 2023

Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.

Essentially the same as A005807.

Join[{1,1},Total/@Partition[CatalanNumber[Range[30]],2,1]] (* Harvey P. Dale, Mar 23 2012 *)

a(n) = A000108(n) + A000108(n-1) (Catalan numbers). - David Callan, Mar 14 2004

D-finite with recurrence (n+1)*a(n) +(-3*n+1)*a(n-1) +2*(-2*n+5)*a(n-2)=0, n>=3 - R. J. Mathar, Aug 25 2013

A089866 Permutation of natural numbers induced by Catalan Automorphism *A089866 acting on the parenthesizations/binary trees encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 11, 12, 13, 14, 15, 19, 21, 22, 16, 17, 18, 20, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 51, 52, 56, 58, 59, 60, 62, 63, 64, 42, 43, 44, 45, 46, 47, 48, 49, 50, 53, 54, 55, 57, 61, 65, 66, 67, 68, 69

Offset: 0

Antti Karttunen, Dec 20 2003

nonn

This bijection of binary trees is obtained when we apply bijection *A074680 to the left subtree and keep the right subtree intact.
.A...B...............B...C
..\./.................\./
...x...C....-->....A...x.................()..B.........B...()....
....\./.............\./...................\./....-->....\./.....
.....x...D...........x...D.................x...C.........x...C..
......\./.............\./...................\./...........\./...
.......x...............x.....................x.............x....
................................................................
Compare to A154122.
See "Catalan bijections" OEIS-Wiki page for a detailed explanation how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan bijections
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Row 4299 of A089840. Inverse of A089865. a(n) = A069770(A154122(A069770(n))).

Number of cycles: A089844. Number of fixed-points: A005807 (prepended with two 1's). Max. cycle size: A089410. LCM of cycle sizes: A089845 (in each range limited by A014137 and A014138).

Further comments and constructive version of Scheme-implementation added by Antti Karttunen, Jun 04 2011

A274244 Number of factor-free Dyck words with slope 7/2 and length 9n.

Original entry on oeis.org

1, 4, 34, 494, 8615, 165550, 3380923, 71999763, 1580990725, 35537491360, 813691565184, 18911247654404, 444978958424224, 10579389908116344, 253756528273411250, 6133110915783398175, 149219383150626519874, 3651756292682801022384, 89830021324956206790496, 2219945238901447637080235, 55088272581138888326634644

Offset: 0

Michael D. Weiner, Jun 15 2016

nonn

a(n) is the number of lattice paths (allowing only north and east steps) starting at (0,0) and ending at (2n,7n) that stay below the line y=7/2x and also do not contain a proper subpath of smaller size.

			a(2) = 34 since there are 34 lattice paths (allowing only north and east steps) starting at (0,0) and ending at (4,14) that stay below the line y=7/2x and also do not contain a proper subpath of small size; e.g., EEENNNNENNNNNNNNNN is a factor-free Dyck word but EEENNENNNNNNNNNNNN contains the factor ENNENNNNN.

Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On rational Dyck paths and the enumeration of factor-free Dyck words, arXiv:1606.02183 [math.CO], 2016.
P. Duchon, On the enumeration and generation of generalized Dyck words, Discrete Mathematics, 225 (2000), 121-135.

Factor-free Dyck words: A005807 (slope 3/2), A274052 (slope 5/2), A274256 (slope 9/2), A274257 (slope 4/3), A274259 (slope 7/3).

Cf. A060941.

Conjectural o.g.f.: Let E(x) = exp( Sum_{n >= 1} binomial(9*n, 2*n)*x^n/n ). Then A(x) = ( x/series reversion of x*E(x) )^(1/9) = 1 + 4*x + 34*x^2 + 494*x^3 + ... . Equivalently, [x^n]( A(x)^(9*n) ) = binomial(9*n, 2*n) for n = 0,1,2,... . - Peter Bala, Jan 01 2020

A274256 Number of factor-free Dyck words with slope 9/2 and length 11n.

Original entry on oeis.org

1, 5, 70, 1696, 49493, 1593861, 54591225, 1950653202, 71889214644, 2712628146949, 104277713515456, 4069334248174800, 160785480249706192, 6419443865094494044, 258585021917711797850, 10496205397574996367474, 428899108081734423242550, 17628723180468295514015268, 728347675604866545590505024

Offset: 0

Michael D. Weiner, Jun 16 2016

nonn

a(n) is the number of lattice paths (allowing only north and east steps) starting at (0,0) and ending at (2n,9n) that stay below the line y=9/2x and also do not contain a proper subpath of smaller size.

			a(2) = 70 since there are 70 lattice paths (allowing only north and east steps) starting at (0,0) and ending at (4,18) that stay below the line y=9/2x and also do not contain a proper subpath of small size; e.g., ENNENNENNNNNNENNNNNNNN is a factor-free Dyck word but ENEENENNNNNNNNNNNNNNNN contains the factor ENENNNNNNNN.

Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On rational Dyck paths and the enumeration of factor-free Dyck words, arXiv:1606.02183 [math.CO], 2016.
P. Duchon, On the enumeration and generation of generalized Dyck words, Discrete Mathematics, 225 (2000), 121-135.

Factor-free Dyck words: A005807 (slope 3/2), A274052 (slope 5/2), A274244 (slope 7/2), A274257 (slope 4/3), A274258 (slope 5/3), A274259 (slope 7/3).

Conjectural o.g.f.: Let E(x) = exp( Sum_{n >= 1} binomial(11*n,2*n)*x^n/n ). Then A(x) = ( x/series reversion of x*E(x) )^(1/11) = 1 + 5*x + 70*x^2 + 1696*x^3 + ... . Equivalently, [x^n]( A(x)^(11*n) ) = binomial(11*n, 2*n) for n = 0,1,2,... . - Peter Bala, Jan 01 2020

A167422 Expansion of (1+x)*c(x), c(x) the g.f. of A000108.

Original entry on oeis.org

1, 2, 3, 7, 19, 56, 174, 561, 1859, 6292, 21658, 75582, 266798, 950912, 3417340, 12369285, 45052515, 165002460, 607283490, 2244901890, 8331383610, 31030387440, 115948830660, 434542177290, 1632963760974, 6151850548776

Offset: 0

Paul Barry, Nov 03 2009

Hankel transform is A167423.

Apparently a(n) = A071716(n) if n>1. - R. J. Mathar, Nov 12 2009

G. C. Greubel, Table of n, a(n) for n = 0..500
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2

Cf. A000108, A001450, A005807, A071716, A167423, A182959.

A167422List := proc(m) local A, P, n; A := [1, 2]; P := [1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), A[-1]]);
A := [op(A), P[-1]] od; A end: A167422List(26); # Peter Luschny, Mar 24 2022

Table[If[n < 2, n + 1, Binomial[2 n, n]/(n + 1) + Binomial[2 (n - 1), n - 1]/n], {n, 0, 25}] (* Michael De Vlieger, Oct 05 2015 *)
CoefficientList[Series[(1 + t)*(1 - Sqrt[1 - 4*t])/(2*t), {t, 0, 50}], t] (* G. C. Greubel, Jun 12 2016 *)

a(n) = if (n<2, n+1, binomial(2*n, n)/(n+1) + binomial(2*(n-1), n-1)/n);
vector(50, n, a(n-1)) \\ Altug Alkan, Oct 04 2015

a(n) = Sum_{k=0..n} A000108(k)*C(1,n-k).
a(0)= 1, a(n) = A005807(n-1) for n>0. - Philippe Deléham, Nov 25 2009
(n+1)*a(n) +(-3*n+1)*a(n-1) +2*(-2*n+5)*a(n-2)=0, for n>2. - R. J. Mathar, Feb 10 2015
-(n+1)*(5*n-6)*a(n) +2*(5*n-1)*(2*n-3)*a(n-1)=0. - R. J. Mathar, Feb 10 2015
The o.g.f. A(x) satisfies [x^n] A(x)^(5*n) = binomial(5*n,2*n) = A001450(n). Cf. A182959. - Peter Bala, Oct 04 2015

Showing 1-10 of 21 results. Next

cp's OEIS Frontend

A001906 F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n-1) - a(n-2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

MuPAD

PARI

PARI

PARI

PARI

Python

Sage

Sage

Formula

A001654 Golden rectangle numbers: F(n) * F(n+1), where F(n) = A000045(n) (Fibonacci numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A213275 Number A(n,k) of words w where each letter of the k-ary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A274052 Number of factor-free Dyck words with slope 5/2 and length 7n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A089865 Permutation of natural numbers induced by Catalan Automorphism *A089865 acting on the parenthesizations/binary trees encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A071716 Expansion of (1+x^2*C)*C, where C = (1-(1-4*x)^(1/2))/(2*x) is g.f. for Catalan numbers, A000108.

Views

Author

Keywords

Comments

Links

Crossrefs

A071716 Expansion of (1+x^2C)C, where C = (1-(1-4x)^(1/2))/(2x) is g.f. for Catalan numbers, A000108.