The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A258109 Number of balanced parenthesis expressions of length 2n and depth 3. 6
 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 (list; graph; refs; listen; history; text; internal format)
 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 Gheorghe Coserea and 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 A271014 A272583 Adjacent sequences:  A258106 A258107 A258108 * A258110 A258111 A258112 KEYWORD nonn,walk,easy AUTHOR Gheorghe Coserea, May 20 2015 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 29 21:59 EDT 2020. Contains 337432 sequences. (Running on oeis4.)