login
Expansion of g.f. x*(1+x+x^2)/(1-x-x^2).
18

%I #86 Feb 16 2024 06:29:15

%S 1,2,4,6,10,16,26,42,68,110,178,288,466,754,1220,1974,3194,5168,8362,

%T 13530,21892,35422,57314,92736,150050,242786,392836,635622,1028458,

%U 1664080,2692538,4356618,7049156,11405774,18454930,29860704,48315634,78176338

%N Expansion of g.f. x*(1+x+x^2)/(1-x-x^2).

%C Previous name was: A007318 * A128587.

%C a(n)/a(n-1) tends to phi, 1.618... = A001622.

%C Regardless of initial two terms, any linearly recurring sequence with signature (1,1) will yield an a(n)/a(n+1) ratio tending to phi (the Golden Ratio). - _Harvey P. Dale_, Mar 29 2017

%C Apart from the initial term, double the Fibonacci numbers. O.g.f.: x*(1+x+x^2)/(1-x-x^2). a(n) gives the number of binary strings of length n-1 avoiding the substrings 000 and 111. a(n) also gives the number of binary strings of length n-1 avoiding the substrings 010 and 101. - _Peter Bala_, Jan 22 2008

%C Row lengths of triangle A232642. - _Reinhard Zumkeller_, May 14 2015

%H Reinhard Zumkeller, <a href="/A128588/b128588.txt">Table of n, a(n) for n = 1..2500</a>

%H J.-P. Allouche and T. Johnson, <a href="http://www.math.jussieu.fr/~allouche/johnson2.pdf"> Narayana's Cows and Delayed Morphisms</a>.

%H Andrei Asinowski and Cyril Banderier, <a href="https://doi.org/10.4230/LIPIcs.AofA.2020.1">On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution</a>, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.

%H Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, <a href="http://arxiv.org/abs/1601.07723">Non-overlapping matrices</a>, arXiv:1601.07723 [cs.DM], 2016. See 1st column of Table 2 p. 11.

%H Jean-Luc Baril, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, <a href="https://arxiv.org/abs/2402.04851">Grand zigzag knight's paths</a>, arXiv:2402.04851 [math.CO], 2024.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, 2009, page 52.

%H B. Winterfjord, <a href="http://www.math.chalmers.se/~einar/exjobb/winterfjord.pdf">Binary strings and substring avoidance</a>.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,1).

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

%F Binomial transform of A128587; a(n+2) = a(n+1) + a(n), n>3.

%F a(n) = A068922(n-1), n>2. - _R. J. Mathar_, Jun 14 2008

%F For n > 1: a(n+1) = a(n) + if a(n) odd then max{a(n),a(n-1)} else min{a(n),a(n-1)}, see also A038754. - _Reinhard Zumkeller_, Oct 19 2015

%F E.g.f.: 4*exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5) - x. - _Stefano Spezia_, Feb 19 2023

%p a:= n-> `if`(n<2, n, 2*(<<0|1>, <1|1>>^n)[1,2]):

%p seq(a(n), n=1..50); # _Alois P. Heinz_, Apr 28 2018

%t nn=40; a=(1-x^3)/(1-x); b=x*(1-x^2)/(1-x); CoefficientList[Series[a^2 /(1-b^2), {x,0,nn}], x] (* _Geoffrey Critzer_, Sep 01 2012 *)

%t LinearRecurrence[{1,1}, {1,2,4}, 40] (* _Harvey P. Dale_, Mar 29 2017 *)

%t Join[{1}, 2*Fibonacci[Range[2,40]]] (* _G. C. Greubel_, Jul 10 2019 *)

%o (Haskell)

%o a128588 n = a128588_list !! (n-1)

%o a128588_list = 1 : cows where

%o cows = 2 : 4 : zipWith (+) cows (tail cows)

%o -- _Reinhard Zumkeller_, May 14 2015

%o (PARI) {a(n) = if( n<2, n==1, 2 * fibonacci(n))}; /* _Michael Somos_, Jul 18 2015 */

%o (Magma) [1] cat [2*Fibonacci(n): n in [2..40]]; // _G. C. Greubel_, Jul 10 2019

%o (Sage) [1]+[2*fibonacci(n) for n in (2..40)] # _G. C. Greubel_, Jul 10 2019

%o (GAP) Concatenation([1], List([2..40], n-> 2*Fibonacci(n))); # _G. C. Greubel_, Jul 10 2019

%Y Cf. A000045, A001622, A128587, A128586, A007318.

%Y Cf. A006355, A055389.

%Y Cf. A014217, A069403, A153819.

%Y Cf. A232642, A242593.

%Y Cf. A038754, A068922.

%Y Main diagonal of A303696.

%K nonn,easy

%O 1,2

%A _Gary W. Adamson_, Mar 11 2007

%E New name from _Joerg Arndt_, Feb 16 2024