|
|
A268208
|
|
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".
|
|
0
|
|
|
1, 3, 12, 52, 236, 1108, 5340, 26276, 131484, 667108, 3424108, 17748564, 92776716, 488527284, 2588907708, 13797337668, 73901315644, 397609958596, 2147904635340, 11645489540468, 63349140877356, 345651184335892, 1891209255293852
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
In Pan and Remmel's link, "vertical" crossing is defined via paired pattern P_1 and P_2.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (x-1)*(-1+3*x+sqrt(1-6*x+x^2))/(x^2*(3-x+sqrt(1-6*x+x^2))).
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
a(n) ~ 2^(5/4) * (1 + sqrt(2))^(2*n+1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jan 20 2021
a(n) = hypergeom([3/2, -n, n + 1], [1/2, 3], -1). - Peter Luschny, Jan 20 2021
|
|
EXAMPLE
|
For example, ENDNE crosses y=x vertically. DDNE does not cross y=x. NEDEN crosses y=x horizontally.
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.
|
|
MAPLE
|
a := n -> hypergeom([3/2, -n, n + 1], [1/2, 3], -1):
|
|
PROG
|
(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
(Maxima)
a(n):=sum(((binomial(2*m+2, m))*(binomial(m+n, n-m)))/(m+1), m, 0, n); /* Vladimir Kruchinin, Jan 20 2021 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|