A218321 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.

1, 2, 8, 39, 212, 1230, 7458, 46689, 299463, 1957723, 12996879, 87383754, 593794311, 4071599216, 28136612051, 195756911831, 1370068168916, 9639404836227, 68138551870047, 483682445360748, 3446462104490724, 24642148415136556, 176743014104068411

Offset: 0

Author

Alois P. Heinz, Oct 25 2012

Keywords

• nonn

Examples

			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)].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..500
• Alois P. Heinz, Maple program for A218321

Crossrefs

Cf. A082582, A168592, A263316.

Programs

Maple

b:= proc(x, y) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
      add(b(x-i, y-1), i=0..x) +add(b(x-1, y-j), j=0..y) -b(x-1,y-1)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..30);
# second Maple program gives series:
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

Mathematica

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]]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Sep 01 2022, after Alois P. Heinz *)

Formula

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