A225042 -id:A225042 - cp's OEIS frontend

A225041 Number of lattice paths from (0,0) to (n,0) that do not go below the x-axis or above the diagonal x=y and consist of steps U=(1,1), D=(1,-1), H=(1,0) and S=(0,1).

1, 1, 3, 9, 35, 145, 659, 3137, 15619, 80177, 422595, 2273633, 12447667, 69138193, 388784259, 2209440945, 12671782579, 73260414481, 426545078627, 2499059841249, 14723542302627, 87181150961361, 518554078448339, 3097007445391441, 18565515801339827

Offset: 0

Alois P. Heinz, Apr 25 2013

nonn

			a(0) = 1: the empty path.
a(1) = 1: H.
a(2) = 3: HH, UD, HSD.
a(3) = 9: HHH, UDH, HSDH, UHD, HSHD, HUD, HHSD, UDSD, HSDSD.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A001006 (without S-steps), A114296 (without U-steps), A198324 (without H-steps), A225042 (paths to (n,n)), A286760.

b:= proc(x, y) option remember; `if`(y>x, 0, `if`(x=0, 1,
       b(x-1, y)+`if`(y>0, b(x-1, y-1)+b(x, y-1), 0)+b(x-1, y+1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..25);

b[x_, y_] := b[x, y] = If[y>x, 0, If[x==0, 1, b[x-1, y]+If[y>0, b[x-1, y-1] + b[x, y-1], 0] + b[x-1, y+1]]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 29 2017, translated from Maple *)

a(n) ~ c * (3+2*sqrt(3))^n / n^(3/2), where c = 0.05641378816540215191327201376... . - Vaclav Kotesovec, Sep 07 2014

A224769 Number of lattice paths from (0,0) to (n,n) that do not go below the x-axis or above the diagonal x=y and consist of steps U=(1,1), D=(1,-1) and S=(0,1).

Original entry on oeis.org

1, 1, 2, 7, 33, 184, 1142, 7629, 53750, 394157, 2981546, 23117242, 182867360, 1470714606, 11993628444, 98967634147, 824958769631, 6937180941468, 58785077008641, 501520244718945, 4304433733010962, 37142428443486254, 322042675618484973, 2804409601249038670

Offset: 0

Alois P. Heinz, Apr 17 2013

nonn

			a(2) = 2: UDSS, UU.
a(3) = 7: UDSDSSS, UDUSS, UDSSDSS, UUDSS, UDSUS, UDSSU, UUU.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A198324 (paths to (n,0)), A225042 (with additional H-steps), A286425.

b:= proc(x, y) option remember; `if`(y>x, 0, `if`(x=0, 1,
      `if`(y>0, b(x, y-1)+b(x-1, y-1), 0)+b(x-1, y+1)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..30);

b[x_, y_] := b[x, y] = If[y > x, 0, If[x == 0, 1, If[y > 0, b[x, y - 1] + b[x - 1, y - 1], 0] + b[x - 1, y + 1]]];
a[n_] := b[n, n];
a /@ Range[0, 30] (* Jean-François Alcover, Dec 18 2020, after Alois P. Heinz *)

a(n) ~ c * d^n / n^(3/2), where d = 3/4*(71 + 8*sqrt(2))^(1/3) + 51/(4*(71 + 8*sqrt(2))^(1/3)) + 13/4 = 9.4435356015932520820011..., c = 0.00814413508604516738631686716788556507884786... . - Vaclav Kotesovec, Sep 07 2014

A224776 Number of lattice paths from (0,0) to (n,n) that do not go below the x-axis or above the diagonal x=y and consist of steps D=(1,-1), H=(1,0) and S=(0,1).

Original entry on oeis.org

1, 1, 3, 14, 83, 568, 4271, 34296, 288946, 2524676, 22695611, 208713400, 1955285936, 18601484936, 179267898087, 1746795785272, 17183086302528, 170427862676296, 1702621483524154, 17118538010217472, 173092651634957516, 1759113081143064184, 17959329720442879275

Offset: 0

Alois P. Heinz, Apr 25 2013

nonn

			a(0) = 1: the empty path.
a(1) = 1: HS.
a(2) = 3: HSHS, HHSS, HSDSS.
a(3) = 14: HSHSHS, HHSSHS, HSDSSHS, HSHHSS, HHSHSS, HSDSHSS, HHHSSS, HSDHSSS, HSHDSSS, HHSDSSS, HSDSDSSS, HSHSDSS, HHSSDSS, HSDSSDSS.

Alois P. Heinz, Table of n, a(n) for n = 0..960

Cf. A000108 (without D-steps), A114296 (paths to (n,0)), A225042 (with additional U-steps), A244593, A286764.

b:= proc(x, y) option remember; `if`(y>x, 0, `if`(x=0, 1,
       b(x-1, y)+`if`(y>0, b(x, y-1), 0)+b(x-1, y+1)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..25);

b[x_, y_] := b[x, y] = If[y > x, 0, If[x == 0, 1, b[x - 1, y] + If[y > 0, b[x, y - 1], 0] + b[x - 1, y + 1]]];
a[n_] := b[n, n];
a /@ Range[0, 25] (* Jean-François Alcover, Dec 18 2020, after Alois P. Heinz *)

a(n) ~ c * ((11+5*sqrt(5))/2)^n / n^(3/2), where c = 0.01403940208697420741365874329992235342402687... . - Vaclav Kotesovec, Sep 07 2014

A346539 a(n) is the number of paths in the Z X Z grid joining (0,0) and (n,n) each of whose steps increases the Euclidean distance to the origin and has coordinates with absolute value at most 1.

Original entry on oeis.org

1, 3, 25, 241, 2545, 28203, 322681, 3776275, 44947503, 542097295, 6607714859, 81247609095, 1006335719467, 12542292874825, 157159924565801, 1978517963096763, 25010881408459855, 317327992746937599, 4039340709637022007, 51569571332132589961, 660140626022179390983

Offset: 0

José María Grau Ribas, Sep 10 2021

nonn

All terms are odd.

Alois P. Heinz, Table of n, a(n) for n = 0..886
Alois P. Heinz, Animation of a(3) = 241 paths

Main diagonal of A346538.
Column k=2 of A347811.
Cf. A008288, A001850, A225042.

b:= proc(n, k) option remember; `if`([n, k]=[0$2], 1, add(add(
     `if`(i^2+j^2 b(n$2):
seq(a(n), n=0..23);  # Alois P. Heinz, Sep 12 2021

rodean[{m_, n_}] := Select[ Complement[ Flatten[Table[{m, n} + {s, t}, {s, -1, 1}, {t, -1, 1}], 1] // Union, {{m, n}}], #[[1]]^2 + #[[2]]^2 < m^2 + n^2 &];
$RecursionLimit=10^6; Clear[T]; T[{0, 0}]=1; T[{m_,n_}]:= T[{m,n}]= Sum[T[rodean[{m,n}][[i]]],{i,Length[rodean[{m, n}]]}]; Table[T[{n,n}],{n, 0,22}]
(* Second program: *)
b[n_, k_] := b[n, k] = If[{n, k} == {0, 0}, 1, Sum[Sum[If[i^2 + j^2 < n^2 + k^2, b@@Sort[{i, j}], 0], {j, k-1, k+1}], {i, n-1, n+1}]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Nov 03 2021, after Alois P. Heinz *)

a(n) ~ c * d^n / n^(3/2), where d = 1/6*(19009+153*sqrt(17))^(1/3) + 356/(3*(19009+153*sqrt(17))^(1/3)) + 14/3 = 13.56165398271839628518... and c = 2.3842296614800994817864695565477260682981556338086519... . - Vaclav Kotesovec, Sep 13 2021

A286765 Total number of nodes summed over all lattice paths from (0,0) to (n,n) that do not go below the x-axis or above the diagonal x=y and consist of steps U=(1,1), D=(1,-1), H=(1,0) and S=(0,1).

Original entry on oeis.org

1, 5, 36, 320, 3204, 34488, 389320, 4542784, 54298992, 660897208, 8157832672, 101824497960, 1282453483896, 16272274720064, 207749196820392, 2666235340584848, 34371222980687520, 444797703379924056, 5775424372048775480, 75210745056872493904

Offset: 0

Alois P. Heinz, May 14 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..885

Cf. A225042.

b:= proc(x, y) option remember; `if`(y<0 or y>x, 0, `if`(x=0, [1$2],
      (p-> p+[0, p[1]])(b(x-1, y)+b(x, y-1)+b(x-1, y+1)+b(x-1, y-1))))
    end:
a:= n-> b(n$2)[2]:
seq(a(n), n=0..30);

b[x_, y_] := b[x, y] = If[y < 0 || y > x, 0, If[x == 0, {1, 1}, Function[p, p + {0, p[[1]]}][b[x-1, y] + b[x, y-1] + b[x-1, y+1] + b[x-1, y-1]]]];
a[n_] := b[n, n][[2]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 06 2023, after Alois P. Heinz *)

a(n) ~ c * d^n / sqrt(n), where d = 1/6*(19009+153*sqrt(17))^(1/3) + 356/(3*(19009+153*sqrt(17))^(1/3)) + 14/3 = 13.561653982718396285180676888474... and c = 0.07613479032254374377532022793959758358787485106312078041310724993901032... - Vaclav Kotesovec, Sep 11 2021

A230662 Number of lattice paths from (0,0) to (n,n) that do not go below the x-axis or above the diagonal x=y and consist of steps u=(1,1), U=(1,2), d=(1,-1), D=(1,-2) and H=(1,0).

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 74, 218, 668, 2096, 6726, 21946, 72666, 243504, 824528, 2816854, 9698520, 33620626, 117254340, 411135452, 1448544666, 5125796448, 18209367238, 64919822556, 232206203152, 833040115596, 2996741699470, 10807658186756, 39068847237770

Offset: 0

Alois P. Heinz, Oct 28 2013

nonn

			a(0) = 1: the empty path.
a(1) = 1: u.
a(2) = 2: HU, uu.
a(3) = 4: HuU, uHU, HUu, uuu.
a(4) = 10: HHUU, udUU, HuuU, uHuU, HUHU, uuHU, HuUu, uHUu, HUuu, uuuu.
a(5) = 26:  HHuUU, uduUU, HuHUU, uHHUU, HUdUU, uudUU, HHUuU, udUuU, HuuuU, uHuuU, HUHuU, uuHuU, HuUHU, uHUHU, HUuHU, uuuHU, HHUUu, udUUu, HuuUu, uHuUu, HUHUu, uuHUu, HuUuu, uHUuu, HUuuu, uuuuu.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A225042.

b:= proc(x, y) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, add(b(x-1, y+j), j=-2..2)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..30);

b[x_, y_] := b[x, y] = If[y > x || y < 0, 0,
   If[x == 0, 1, Sum[b[x - 1, y + j], {j, -2, 2}]]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 28 2022, after Alois P. Heinz *)

a(n) ~ c * d^n / n^(3/2), where d = 47/54 + (1/54)*sqrt(2479 - (6525*15^(2/3))/(-8271 + 1496*sqrt(51))^(1/3) + 45*(15*(-8271 + 1496*sqrt(51)))^(1/3)) + (1/2)*sqrt(4958/729 + (725*5^(2/3))/(27*(3*(-8271 + 1496*sqrt(51)))^(1/3)) - (5*(5*(-8271 + 1496*sqrt(51)))^(1/3))/(27*3^(2/3)) + 318616/(729*sqrt(2479 - (6525*15^(2/3))/(-8271 + 1496*sqrt(51))^(1/3) + 45*(15*(-8271 + 1496*sqrt(51)))^(1/3)))) = 3.8344372490288055637652411266... and c = 0.2279529551507616709766813416011544206054574311958828512... - Vaclav Kotesovec, Oct 30 2013, updated Sep 11 2021

cp's OEIS Frontend

A225041 Number of lattice paths from (0,0) to (n,0) that do not go below the x-axis or above the diagonal x=y and consist of steps U=(1,1), D=(1,-1), H=(1,0) and S=(0,1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A224769 Number of lattice paths from (0,0) to (n,n) that do not go below the x-axis or above the diagonal x=y and consist of steps U=(1,1), D=(1,-1) and S=(0,1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A224776 Number of lattice paths from (0,0) to (n,n) that do not go below the x-axis or above the diagonal x=y and consist of steps D=(1,-1), H=(1,0) and S=(0,1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A346539 a(n) is the number of paths in the Z X Z grid joining (0,0) and (n,n) each of whose steps increases the Euclidean distance to the origin and has coordinates with absolute value at most 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A286765 Total number of nodes summed over all lattice paths from (0,0) to (n,n) that do not go below the x-axis or above the diagonal x=y and consist of steps U=(1,1), D=(1,-1), H=(1,0) and S=(0,1).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A230662 Number of lattice paths from (0,0) to (n,n) that do not go below the x-axis or above the diagonal x=y and consist of steps u=(1,1), U=(1,2), d=(1,-1), D=(1,-2) and H=(1,0).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula