login
Number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k>=0.
4

%I #25 Sep 01 2022 04:58:44

%S 1,2,8,39,212,1230,7458,46689,299463,1957723,12996879,87383754,

%T 593794311,4071599216,28136612051,195756911831,1370068168916,

%U 9639404836227,68138551870047,483682445360748,3446462104490724,24642148415136556,176743014104068411

%N Number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k>=0.

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

%H Alois P. Heinz, <a href="/A218321/a218321.txt">Maple program for A218321</a>

%F G.f.: (sqrt(x^4+4*x^3+2*x^2-8*x+1)+x^2+1-sqrt(2*(x^4+2*x^3-6*x^2-4*x+1+(x^2+1)*sqrt(x^4+4*x^3+2*x^2-8*x+1))))/(4*x^2). - _Mark van Hoeij_, Apr 17 2013

%e a(2) = 8: [(0,0),(1,0),(1,1),(2,1),(2,2)], [(0,0),(1,0),(1,1),(2,2)], [(0,0),(1,0),(2,0),(2,1),(2,2)], [(0,0),(1,0),(2,1),(2,2)], [(0,0),(1,0),(2,2)], [(0,0),(1,1),(2,1),(2,2)], [(0,0),(1,1),(2,2)], [(0,0),(2,1),(2,2)].

%p b:= proc(x, y) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,

%p add(b(x-i, y-1), i=0..x) +add(b(x-1, y-j), j=0..y) -b(x-1,y-1)))

%p end:

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

%p seq(a(n), n=0..30);

%p # second Maple program gives series:

%p series(RootOf(x^4*T^4-(x^2+1)*x^2*T^3-(x^2-2*x-2)*x*T^2-(x^2+1)*T+1, T), x=0, 31); # _Mark van Hoeij_, Apr 17 2013

%t b[x_, y_] := b[x, y] = If[y < 0 || y > x, 0, If[x == 0, 1, Sum[b[x - i, y - 1], {i, 0, x}] + Sum[b[x - 1, y - j], {j, 0, y}] - b[x - 1, y - 1]]];

%t a[n_] := b[n, n];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Sep 01 2022, after _Alois P. Heinz_ *)

%Y Cf. A082582, A168592, A263316.

%K nonn

%O 0,2

%A _Alois P. Heinz_, Oct 25 2012