A258109 Number of balanced parenthesis expressions of length 2n and depth 3.

1, 5, 18, 57, 169, 482, 1341, 3669, 9922, 26609, 70929, 188226, 497845, 1313501, 3459042, 9096393, 23895673, 62721698, 164531565, 431397285, 1130708866, 2962826465, 7761964833, 20331456642, 53249182309, 139449644717, 365166860706, 956185155129, 2503657040137

Offset: 3

Author

Gheorghe Coserea, May 20 2015

Keywords

• nonn
• walk
• easy

Comments

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

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

Examples

			For n=4, the a(4) = 5 solutions are
                /\       /\
               /  \        \
LRLLLRRR    /\/    \        \
................................
                /\        |
             /\/  \      / \
LLRLLRRR    /      \        \
................................
              /\/\        |
             /    \       |
LLLRLRRR    /      \     / \
................................
              /\          |
             /  \/\      / \
LLLRRLRR    /      \    /
................................
              /\          /\
             /  \        /
LLLRRRLR    /    \/\    /
		

References

• S. S. Skiena and M. A. Revilla, Programming Challenges: The Programming Contest Training Manual, Springer, 2006, page 140.

Links

• Alois P. Heinz, Table of n, a(n) for n = 3..1000 (first 40 terms from Gheorghe Coserea)
• Kyu-Hwan Lee, Se-jin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
• Index entries for linear recurrences with constant coefficients, signature (5,-7,2).

Crossrefs

Column k=3 of A080936.

Column k=2 of A287213.

Cf. A000045, A000079, A262600.

Programs

C

typedef long long unsigned Integer;
Integer a(int n)
{
    int i;
    Integer pow2 = 1, a[3] = {0};
    for (i = 3; i <= n; ++i) {
        a[ i%3 ] = pow2 + 3 * a[ (i-1)%3 ] - a[ (i-2)%3 ];
        pow2 = pow2 * 2;
    }
    return a[ (i-1)%3 ];
}

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

Maple

a:= proc(n) option remember; `if`(n<3, 0,
      `if`(n=3, 1, 2^(n-3) +3*a(n-1) -a(n-2)))
    end:
seq(a(n), n=3..30);  # Alois P. Heinz, May 20 2015

Mathematica

Join[{1, 5}, LinearRecurrence[{5, -7, 2}, {18, 57, 169}, 30]] (* Vincenzo Librandi, Sep 26 2015 *)

PARI

Vec(-x^3/((2*x-1)*(x^2-3*x+1)) + O(x^100)) \\ Colin Barker, May 24 2015

PARI

a(n) = fibonacci(2*n-1) - 2^(n-1)  \\ Gheorghe Coserea, Feb 04 2016

Formula

a(n) = 2^(n-3) + 3 * a(n-1) - a(n-2).

a(n) = 5*a(n-1) - 7*a(n-2) + 2*a(n-3) for n>5. - Colin Barker, May 24 2015

G.f.: -x^3 / ((2*x-1)*(x^2-3*x+1)). - Colin Barker, May 24 2015

a(n) = A000045(2n-1) - A000079(n-1). - Gheorghe Coserea, Feb 04 2016

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

a(n) = Sum_{i=1..n-1} A061667(i)*(n-1-i) - Tim C. Flowers, May 16 2018