login
a(n) = 3*a(n-1) - a(n-2) - 1 with a(0) = 1 and a(1) = 2.
19

%I #86 May 14 2024 21:33:29

%S 1,2,4,9,22,56,145,378,988,2585,6766,17712,46369,121394,317812,832041,

%T 2178310,5702888,14930353,39088170,102334156,267914297,701408734,

%U 1836311904,4807526977,12586269026,32951280100,86267571273

%N a(n) = 3*a(n-1) - a(n-2) - 1 with a(0) = 1 and a(1) = 2.

%C Number of directed column-convex polyominoes with area n+2 and having two cells in the bottom row. - _Emeric Deutsch_, Jun 14 2001

%C a(n) is the length of the list generated by the substitution: 3->3, 4->(3,4,6), 6->(3,4,6,6): {3, 4}, {3, 3, 4, 6}, {3, 3, 3, 4, 6, 3, 4, 6, 6}, {3, 3, 3, 3, 4, 6, 3, 4, 6, 6, 3, 3, 4, 6, 3, 4, 6, 6, 3, 4, 6, 6}, etc. - _Wouter Meeussen_, Nov 23 2003

%C Equals row sums of triangle A144955. - _Gary W. Adamson_, Sep 27 2008

%C Equals the INVERT transform of A034943 and the INVERTi transform of A094790. - _Gary W. Adamson_, Apr 01 2011

%H Vincenzo Librandi, <a href="/A055588/b055588.txt">Table of n, a(n) for n = 0..1000</a>

%H E. Barcucci, R. Pinzani and R. Sprugnoli, <a href="http://dx.doi.org/10.1007/3-540-56610-4_71">Directed column-convex polyominoes by recurrence relations</a>, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.

%H Jean-Luc Baril, Pamela E. Harris, and José L. Ramírez, <a href="https://arxiv.org/abs/2405.05357">Flattened Catalan Words</a>, arXiv:2405.05357 [math.CO], 2024. See p. 20.

%H Sergi Elizalde, <a href="https://arxiv.org/abs/2008.05669">Symmetric peaks and symmetric valleys in Dyck paths</a>, arXiv:2008.05669 [math.CO], 2020.

%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a>, 2011. [Cached copy]

%H Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.

%H M. M. Mogbonju, I. A. Ogunleke, and O. A. Ojo, <a href="https://www.ijsr.net/archive/v3i12/T0NUMTQ4NTg=.pdf">Graphical Representation Of Conjugacy Classes In The Order-Preserving Full Transformation Semigroup</a>, International Journal of Scientific Research and Engineering Studies (IJSRES), Volume 1(5) (2014), ISSN: 2349-8862.

%H László Németh, <a href="http://arxiv.org/abs/1511.02067">Hyperbolic Pascal pyramid</a>, arXiv:1511.02067 [math.CO], 2015 (1st line of Table 1 is 3*a(n-2)).

%H László Németh, <a href="https://arxiv.org/abs/1701.06022">Pascal pyramid in the space H^2 x R</a>, arXiv:1701.06022 [math.CO], 2017 (1st line of Table 1 is a(n-2)).

%H Yan X Zhang, <a href="http://arxiv.org/abs/1508.00318">Four Variations on Graded Posets</a>, arXiv:1508.00318 [math.CO], 2015.

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

%F a(n) = (((3 + sqrt(5))/2)^n - ((3 - sqrt(5))/2)^n)/sqrt(5) + 1.

%F a(n) = Sum_{m=0..n} A055587(n, m) = 1 + A001906(n).

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

%F From _Paul Barry_, Oct 07 2004: (Start)

%F a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3);

%F a(n) = Sum_{k=0..floor(n/3)} binomial(n-k, 2*k)2^(n-3*k). (End)

%F From _Paul Barry_, Oct 26 2004: (Start)

%F a(n) = A001906(n) + 1.

%F a(n) = Sum_{k=0..n} Fibonacci(2*k+2)*(2*0^(n-k) - 1).

%F a(n) = A008346(2*n). (End)

%F a(n) = Sum_{k=0..2*n+1} ((-1)^(k+1))*Fibonacci(k). - _Michel Lagneau_, Feb 03 2014

%F E.g.f.: cosh(x) + sinh(x) + 2*exp(3*x/2)*sinh(sqrt(5)*x/2)/sqrt(5). - _Stefano Spezia_, May 14 2024

%p g:=z/(1-3*z+z^2): gser:=series(g, z=0, 43): seq(abs(coeff(gser, z, n)+1), n=0..27); # _Zerinvary Lajos_, Mar 22 2009

%t Table[Fibonacci[2n] +1, {n, 0, 40}] (* or *) LinearRecurrence[{4, -4, 1}, {1, 2, 4}, 40] (* _Vincenzo Librandi_, Sep 30 2017 *)

%o (Sage) [lucas_number1(n,3,1)+1 for n in range(40)] # _Zerinvary Lajos_, Jul 06 2008

%o (Magma) [Fibonacci(2*n)+1: n in [0..40]]; // _Vincenzo Librandi_, Sep 30 2017

%o (PARI) vector(40, n, n--; fibonacci(2*n)+1) \\ _G. C. Greubel_, Jun 06 2019

%o (GAP) List([0..40], n-> Fibonacci(2*n)+1 ) # _G. C. Greubel_, Jun 06 2019

%Y Cf. A001906, A008346, A034943, A055587, A094790, A144955.

%Y Partial sums of A001519.

%Y Apart from the first term, same as A052925.

%K nonn,easy

%O 0,2

%A _Wolfdieter Lang_, May 30 2000; _Barry E. Williams_, Jun 04 2000