%I #70 Oct 27 2023 21:47:14
%S 1,5,18,57,169,482,1341,3669,9922,26609,70929,188226,497845,1313501,
%T 3459042,9096393,23895673,62721698,164531565,431397285,1130708866,
%U 2962826465,7761964833,20331456642,53249182309,139449644717,365166860706,956185155129,2503657040137
%N Number of balanced parenthesis expressions of length 2n and depth 3.
%C a(n) is the number of Dyck paths of length 2n and height 3. For example, a(3) = 1 because there is only one such Dyck path which is UUUDDD. - _Ran Pan_, Sep 26 2015
%C a(n) is the number of rooted plane trees with n+1 nodes and height 3 (see example for correspondence). - _Gheorghe Coserea_, Feb 04 2016
%D S. S. Skiena and M. A. Revilla, Programming Challenges: The Programming Contest Training Manual, Springer, 2006, page 140.
%H Alois P. Heinz, <a href="/A258109/b258109.txt">Table of n, a(n) for n = 3..1000</a> (first 40 terms from Gheorghe Coserea)
%H Kyu-Hwan Lee, Se-jin Oh, <a href="http://arxiv.org/abs/1601.06685">Catalan triangle numbers and binomial coefficients</a>, arXiv:1601.06685 [math.CO], 2016.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-7,2).
%F a(n) = 2^(n-3) + 3 * a(n-1) - a(n-2).
%F a(n) = 5*a(n-1) - 7*a(n-2) + 2*a(n-3) for n>5. - _Colin Barker_, May 24 2015
%F G.f.: -x^3 / ((2*x-1)*(x^2-3*x+1)). - _Colin Barker_, May 24 2015
%F a(n) = A000045(2n-1) - A000079(n-1). - _Gheorghe Coserea_, Feb 04 2016
%F a(n) = 2^(-1-n)*(-5*4^n - (-5+sqrt(5))*(3+sqrt(5))^n + (3-sqrt(5))^n*(5+sqrt(5))) / 5. - _Colin Barker_, Jun 05 2017
%F a(n) = Sum_{i=1..n-1} A061667(i)*(n-1-i) - _Tim C. Flowers_, May 16 2018
%e For n=4, the a(4) = 5 solutions are
%e /\ /\
%e / \ \
%e LRLLLRRR /\/ \ \
%e ................................
%e /\ |
%e /\/ \ / \
%e LLRLLRRR / \ \
%e ................................
%e /\/\ |
%e / \ |
%e LLLRLRRR / \ / \
%e ................................
%e /\ |
%e / \/\ / \
%e LLLRRLRR / \ /
%e ................................
%e /\ /\
%e / \ /
%e LLLRRRLR / \/\ /
%p a:= proc(n) option remember; `if`(n<3, 0,
%p `if`(n=3, 1, 2^(n-3) +3*a(n-1) -a(n-2)))
%p end:
%p seq(a(n), n=3..30); # _Alois P. Heinz_, May 20 2015
%t Join[{1, 5}, LinearRecurrence[{5, -7, 2}, {18, 57, 169}, 30]] (* _Vincenzo Librandi_, Sep 26 2015 *)
%o (C)
%o typedef long long unsigned Integer;
%o Integer a(int n)
%o {
%o int i;
%o Integer pow2 = 1, a[3] = {0};
%o for (i = 3; i <= n; ++i) {
%o a[ i%3 ] = pow2 + 3 * a[ (i-1)%3 ] - a[ (i-2)%3 ];
%o pow2 = pow2 * 2;
%o }
%o return a[ (i-1)%3 ];
%o }
%o (PARI) Vec(-x^3/((2*x-1)*(x^2-3*x+1)) + O(x^100)) \\ _Colin Barker_, May 24 2015
%o (Magma) I:=[1,5,18,57,169]; [n le 5 select I[n] else 5*Self(n-1) - 7*Self(n-2) + 2*Self(n-3): n in [1..40]]; // _Vincenzo Librandi_, Sep 26 2015
%o (PARI) a(n) = fibonacci(2*n-1) - 2^(n-1) \\ _Gheorghe Coserea_, Feb 04 2016
%Y Column k=3 of A080936.
%Y Column k=2 of A287213.
%Y Cf. A000045, A000079, A262600.
%K nonn,walk,easy
%O 3,2
%A _Gheorghe Coserea_, May 20 2015