A346538 -id:A346538 - cp's OEIS frontend

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.

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

A347814 Number of walks on square lattice from (n,0) to (0,0) using steps that decrease the Euclidean distance to the origin and that change each coordinate by at most 1.

Original entry on oeis.org

1, 1, 7, 29, 173, 937, 5527, 32309, 193663, 1166083, 7093413, 43373465, 266712433, 1646754449, 10205571945, 63442201565, 395457341485, 2470816812547, 15469821698211, 97035271087123, 609662167537831, 3836108862182671, 24169777826484697, 152468665277411533

Offset: 0

Alois P. Heinz, Sep 14 2021

All terms are odd.

Lattice points may have negative coordinates, and different walks may differ in length. All walks are self-avoiding.

Alois P. Heinz, Table of n, a(n) for n = 0..1236
Alois P. Heinz, Animation of a(4) = 173 walks
Wikipedia, Counting lattice paths
Wikipedia, Self-avoiding walk

Column (or row) k=0 of A346538.

Cf. A002426.

s:= proc(n) option remember;
     `if`(n=0, [[]], map(x-> seq([x[], i], i=-1..1), s(n-1)))
    end:
b:= proc(l) option remember; (n-> `if`(l=[0$n], 1, add((h-> `if`(
      add(i^2, i=h) b([0, n]):
seq(a(n), n=0..30);

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[0, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 03 2021, after Alois P. Heinz *)

cp's OEIS Frontend

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