A268208 - OEIS

%I #37 Jul 31 2024 09:47:02

%S 1,3,12,52,236,1108,5340,26276,131484,667108,3424108,17748564,

%T 92776716,488527284,2588907708,13797337668,73901315644,397609958596,

%U 2147904635340,11645489540468,63349140877356,345651184335892,1891209255293852

%N Number of paths from (0,0) to (n,n) using only steps North, Northeast and East (i.e., steps E(1,0), D(1,1), and N(0,1)) that do not cross y=x "vertically".

%C In Pan and Remmel's link, "vertical" crossing is defined via paired pattern P_1 and P_2.

%H Ran Pan and Jeffrey B. Remmel, <a href="http://arxiv.org/abs/1601.07988">Paired patterns in lattice paths</a>, arXiv:1601.07988 [math.CO], 2016.

%H Luis Verde-Star, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Verde/verde4.html">A Matrix Approach to Generalized Delannoy and Schröder Arrays</a>, J. Int. Seq., Vol. 24 (2021), Article 21.4.1.

%F G.f.: (x-1)*(-1+3*x+sqrt(1-6*x+x^2))/(x^2*(3-x+sqrt(1-6*x+x^2))).

%F D-finite with recurrence (n+2)*a(n) +(-7*n-2)*a(n-1) +(7*n-16)*a(n-2) +(-n+4)*a(n-3)=0. - _R. J. Mathar_, Jun 07 2016

%F a(n) = Sum_{m=0..n} C(2*m+2,m)*C(m+n,n-m)/(m+1). - _Vladimir Kruchinin_ Jan 20 2021

%F a(n) ~ 2^(5/4) * (1 + sqrt(2))^(2*n+1) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Jan 20 2021

%F a(n) = hypergeom([3/2, -n, n + 1], [1/2, 3], -1). - _Peter Luschny_, Jan 20 2021

%e For example, ENDNE crosses y=x vertically. DDNE does not cross y=x. NEDEN crosses y=x horizontally.

%e For n=2, there are 13 paths from (0,0) to (2,2) and only one of them crosses y=x vertically, namely ENNE. Therefore, a(2) = 12.

%p a := n -> hypergeom([3/2, -n, n + 1], [1/2, 3], -1):

%p seq(simplify(a(n)), n=0..22); # _Peter Luschny_, Jan 20 2021

%o (PARI) my(x = 'x + O('x^30)); Vec((x-1)*(-1+3*x+sqrt(1-6*x+x^2))/(x^2*(3-x+sqrt(1-6*x+x^2)))) \\ _Michel Marcus_, Feb 02 2016

%o (Maxima)

%o a(n):=sum(((binomial(2*m+2,m))*(binomial(m+n,n-m)))/(m+1),m,0,n); /* _Vladimir Kruchinin_, Jan 20 2021 */

%Y Cf. A001850, A001003, A006318.

%K nonn,easy

%O 0,2

%A _Ran Pan_, Jan 28 2016