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,2

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

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).

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

Example

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

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 *)

Prog

(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 ];
}
(PARI) Vec(-x^3/((2*x-1)*(x^2-3*x+1)) + O(x^100)) \\ Colin Barker, May 24 2015
(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
(PARI) a(n) = fibonacci(2*n-1) - 2^(n-1)  \\ Gheorghe Coserea, Feb 04 2016

Crossrefs

Column k=3 of A080936.

Column k=2 of A287213.

Cf. A000045, A000079, A262600.

Sequence in context: A325923 A335720 A093374 * A000745 A343802 A271014

Adjacent sequences: A258106 A258107 A258108 * A258110 A258111 A258112

Keyword

nonn,walk,easy

Author

Gheorghe Coserea, May 20 2015

Status

approved