login
Number of Dyck paths of length 2n with exactly 1 hill.
5

%I #32 Jun 28 2017 07:51:08

%S 0,1,0,2,4,13,40,130,432,1466,5056,17672,62460,222853,801592,2903626,

%T 10582816,38781310,142805056,528134764,1960825672,7305767602,

%U 27307800400,102371942932,384806950624,1450038737668,5476570993440,20727983587220,78606637060012

%N Number of Dyck paths of length 2n with exactly 1 hill.

%C Convolution of A000957(n) with itself gives a(n-1).

%H Alois P. Heinz, <a href="/A065601/b065601.txt">Table of n, a(n) for n = 0..500</a>

%H Naiomi Cameron, J. E. McLeod, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/McLeod/mcleod3.html">Returns and Hills on Generalized Dyck Paths</a>, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.

%H E. Deutsch, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00371-9">Dyck path enumeration</a>, Discrete Math., 204, 1999, 167-202.

%H E. Deutsch and L. Shapiro, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00121-2">A survey of the Fine numbers</a>, Discrete Math., 241 (2001), 241-265.

%H S. Kitaev, J. Remmel and M. Tiefenbruck, <a href="http://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I</a>, arXiv preprint arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012

%H Sergey Kitaev, Jeffrey Remmel, Mark Tiefenbruck, <a href="http://www.emis.de/journals/INTEGERS/papers/p16/p16.Abstract.html">Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II</a>, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (<a href="http://arxiv.org/abs/1302.2274">arXiv:1302.2274</a>)

%F Reference gives g.f.'s.

%F Conjecture: 2*(n+1)*a(n) +(-3*n+2)*a(n-1) +2*(-9*n+19)*a(n-2) +4*(-2*n+3)*a(n-3)=0. - _R. J. Mathar_, Dec 10 2013

%F a(n) ~ 2^(2*n+3) / (27 * sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Feb 12 2014

%p b:= proc(x, y, h, z) option remember;

%p `if`(x<0 or y<x, 0, `if`(x=0 and y=0, `if`(h, 0, 1),

%p b(x-1, y, h, is(x=y))+ `if`(h and z, b(x, y-1, false$2),

%p `if`(z, 0, b(x, y-1, h, false)))))

%p end:

%p a:= n-> b(n$2, true$2):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, May 10 2012

%p # second Maple program:

%p series(((1-sqrt(1-4*x))/(3-sqrt(1-4*x)))^2/x, x=0, 30); # _Mark van Hoeij_, Apr 18 2013

%t CoefficientList[Series[((1-Sqrt[1-4*x])/(3-Sqrt[1-4*x]))^2/x, {x, 0, 20}], x] (* _Vaclav Kotesovec_, Feb 12 2014 *)

%t Table[Sum[(-1)^j*(j+1)*(j+2)*Binomial[2*n-1-j,n],{j,0,n-1}]/(n+1),{n,0,30}] (* _Vaclav Kotesovec_, May 18 2015 *)

%Y 2nd column of A065600. Cf. A000957.

%K nonn,easy

%O 0,4

%A _N. J. A. Sloane_, Dec 02 2001

%E More terms from _Emeric Deutsch_, Dec 03 2001