login
a(n) = C(n+1) + n*C(n) where C = A000108 (Catalan numbers).
4

%I #39 Apr 11 2023 08:43:38

%S 1,3,9,29,98,342,1221,4433,16302,60554,226746,854658,3239044,12332140,

%T 47137005,180780345,695367510,2681600130,10364759790,40142121030,

%U 155748675420,605274171060,2355676013730,9180275261274,35819645937228

%N a(n) = C(n+1) + n*C(n) where C = A000108 (Catalan numbers).

%C Number of ascents of length 2 starting at an even level in all Dyck paths of semilength n+2. Example: a(1)=3 because all Dyck paths of semilength 3 are UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and UUUDDD, where U=(1,1), D=(1,-1), having altogether 3 ascents of length 2 that start at an even level (shown between parentheses). - _Emeric Deutsch_, Nov 29 2005

%C a(n) is the number of parking functions of size n+1 avoiding the patterns 132, 231, and 321. - _Lara Pudwell_, Apr 10 2023

%H G. C. Greubel and Vincenzo Librandi, <a href="/A077587/b077587.txt">Table of n, a(n) for n = 0..1000</a>(terms 0..200 from Vincenzo Librandi)

%H Ayomikun Adeniran and Lara Pudwell, <a href="https://doi.org/10.54550/ECA2023V3S3R17">Pattern avoidance in parking functions</a>, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.

%H A. Asinowski and G. Rote, <a href="http://arxiv.org/abs/1502.04925">Point sets with many non-crossing matchings</a>, arXiv:1502.04925 [cs.CG], 2015.

%F a(n) = binomial(2n+1, n+1) - binomial(2n, n+2).

%F a(n) = (3*(3*n+2)*a(n-1) - 2*(11*n-7)*a(n-2) + 4*(2*n-5)*a(n-3))/(n+2), n>2.

%F G.f.: A(x) = (1 - 3*x - (1-5*x+2*x^2)/sqrt(1-4*x) )/(2*x^2) satisfies 0 = (x^2+4*x-1) + (12*x^2-7*x+1)*A + (4*x^3-x^2)*A^2.

%F E.g.f.: A(x) = (1+x)B(x)' where B(x) = e.g.f. of A000108.

%F a(n) = Sum_{k=0..n} binomial(n,k)*A057977(k)*2^(n-k); here the A057977 are understood as the extended Catalan numbers (see also A063549). Related to Touchard's identity. - _Peter Luschny_, Jul 14 2016

%F a(n) ~ 4^n/sqrt(Pi*n). - _Ilya Gutkovskiy_, Jul 14 2016

%F Asymptotic starts a(n) ~ (4^n/sqrt(Pi*n))*(1 + (23/2^3)/n - (1199/2^7)/n^2 +(22685/2^10)/n^3 - (1562421/2^15)/n^4 + ... ). - _Peter Luschny_, Jul 14 2016

%p egf := x -> exp(2*x)*(1+1/x)*BesselI(1, 2*x);

%p seq(n!*coeff(series(egf(x), x, n+2), x, n), n=0..24); # _Peter Luschny_, Apr 14 2014

%t Table[(CatalanNumber[n + 1] + n CatalanNumber[n]), {n, 0, 40}] (* _Vincenzo Librandi_, Apr 15 2014 *)

%o (PARI) a(n)=if(n<0,0,(n^2+6*n+2)*(2*n)!/n!/(n+2)!)

%o (PARI) a(n)=if(n<0,0,polcoeff((4+x+1/x-(x+1/x)^2)*(1+x)^(2*n),n)/2)

%Y Cf. A000108, A057977, A114462.

%K nonn,easy

%O 0,2

%A _Michael Somos_, Nov 09 2002