login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:48 EDT 2024. Contains 370951 sequences. (Running on oeis4.)