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

Offset: 0

Author

N. J. A. Sloane, Jun 06 2002

Keywords

• nonn

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

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

Crossrefs

Essentially the same as A005807.

Programs

Mathematica

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

Formula

a(n) = A000108(n) + A000108(n-1) (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