A091135 Number of Dyck paths of semilength n+4, having exactly two long ascents (i.e., ascents of length at least two).

2, 15, 69, 252, 804, 2349, 6455, 16962, 43086, 106587, 258153, 614520, 1441928, 3342489, 7667883, 17432766, 39321810, 88080615, 196083965, 434110740, 956301612, 2097152325, 4580180319, 9965666682, 21609054614, 46707769779

Offset

0,1

Comments

Also number of ordered trees with n+4 edges, having exactly two branch nodes (i.e., vertices of outdegree at least two).

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (9,-33,63,-66,36,-8).

Formula

a(n) = (n^2 + 9*n + 20)/2 + 2^(n+1)*(n^2 + 3*n - 4).

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

a(n) = 9*a(n-1) - 33*a(n-2) + 63*a(n-3) - 66*a(n-4) + 36*a(n-5) - 8*a(n-6) for n>5. - Colin Barker, Apr 09 2019

Example

a(0)=2 because the only Dyck paths of semilength 4 that have exactly two long ascents are UUDDUUDD and UUDUUDDD (here U=(1,1) and D=(1,-1)).

Mathematica

LinearRecurrence[{9, -33, 63, -66, 36, -8}, {2, 15, 69, 252, 804, 2349}, 30] (* Harvey P. Dale, Jul 01 2020 *)

Prog

(PARI) Vec((2 - 3*x) / ((1 - x)^3*(1 - 2*x)^3) + O(x^40)) \\ Colin Barker, Apr 09 2019

Crossrefs

Cf. A000108.

Sequence in context: A055206 A216614 A146757 * A056037 A125903 A268644

Adjacent sequences: A091132 A091133 A091134 * A091136 A091137 A091138

Keyword

nonn,easy

Author

Emeric Deutsch, Feb 22 2004

Status

approved