A071716 Expansion of (1+x^2*C)*C, where C = (1-(1-4*x)^(1/2))/(2*x) is g.f. for Catalan numbers, A000108.

1, 1, 3, 7, 19, 56, 174, 561, 1859, 6292, 21658, 75582, 266798, 950912, 3417340, 12369285, 45052515, 165002460, 607283490, 2244901890, 8331383610, 31030387440, 115948830660, 434542177290, 1632963760974, 6151850548776, 23229299473604, 87900903988156, 333281502666364

Offset

0,3

Comments

a(n) is the number of lattice paths of n up steps and n down steps that start at the origin with an up step and do not cross the x-axis except possibly at (2n-2,0). - David Callan, Mar 14 2004

a(n) is the number of parking functions of size n avoiding the patterns 132, 213, 231, and 321. - Lara Pudwell, Apr 10 2023

Links

Table of n, a(n) for n=0..28.

Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.

Formula

a(n) = A000108(n) + A000108(n-1) for n >= 2. (Catalan numbers). - David Callan, Mar 14 2004

D-finite with recurrence (n+1)*a(n) + (-3*n+1)*a(n-1) + 2*(-2*n+5)*a(n-2) = 0, n>=3 - R. J. Mathar, Aug 25 2013

a(n) ~ 5 * 4^(n-1) / (n^(3/2) * sqrt(Pi)). - Amiram Eldar, Oct 04 2025

Mathematica

Join[{1, 1}, Total/@Partition[CatalanNumber[Range[30]], 2, 1]] (* Harvey P. Dale, Mar 23 2012 *)

Crossrefs

Essentially the same as A005807.

Cf. A000108.

Sequence in context: A224031 A147586 A305197 * A306088 A188625 A258171

Adjacent sequences: A071713 A071714 A071715 * A071717 A071718 A071719

Keyword

nonn,easy

Author

N. J. A. Sloane, Jun 06 2002

Status

approved