A225691 Number of Dyck paths of semilength n avoiding the pattern U^4 D^4 U D.

1, 1, 2, 5, 14, 41, 110, 245, 450, 739, 1126, 1625, 2250, 3015, 3934, 5021, 6290, 7755, 9430, 11329, 13466, 15855, 18510, 21445, 24674, 28211, 32070, 36265, 40810, 45719, 51006, 56685, 62770, 69275, 76214, 83601, 91450, 99775, 108590, 117909, 127746, 138115, 149030, 160505, 172554

Offset

0,3

Links

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

Axel Bacher, Antonio Bernini, Luca Ferrari, Benjamin Gunby, Renzo Pinzani and Julian West, The Dyck pattern poset Discrete Math. 321 (2014), 12--23. MR3154009.

A. Bernini, L. Ferrari, R. Pinzani and J. West, The Dyck pattern poset, arXiv preprint arXiv:1303.3785, 2013

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Formula

a(n) = (14*n^3-84*n^2+124*n-84)/6 for n >= 6.

a(n) = 4*a(n-1)-6*a(n-2)+4*a(n-3)-a(n-4) for n>6. - Colin Barker, Jul 10 2015

G.f.: (10*x^9-20*x^8+12*x^6+8*x^5+3*x^4-x^3+4*x^2-3*x+1) / (x-1)^4. - Colin Barker, Jul 10 2015

Mathematica

LinearRecurrence[{4, -6, 4, -1}, {1, 1, 2, 5, 14, 41, 110, 245, 450, 739}, 50] (* Harvey P. Dale, Apr 10 2019 *)

Prog

(PARI) Vec((10*x^9-20*x^8+12*x^6+8*x^5+3*x^4-x^3+4*x^2-3*x+1)/(x-1)^4 + O(x^100)) \\ Colin Barker, Jul 10 2015

Crossrefs

A row of A238095.

Sequence in context: A163189 A243881 A358416 * A116846 A080558 A116844

Adjacent sequences: A225688 A225689 A225690 * A225692 A225693 A225694

Keyword

nonn,easy

Author

N. J. A. Sloane, May 27 2013

Status

approved