A308114 -id:A308114 - cp's OEIS frontend

A308112 Total number of nodes summed over all lattice paths from (0,0) to (n,n) that consist of steps (h,v) with min(h,v) > 0 and gcd(h,v) = 1.

1, 2, 3, 10, 47, 186, 703, 2640, 9979, 37980, 144713, 550666, 2093215, 7951524, 30186737, 114522342, 434172249, 1644889496, 6227677911, 23563691408, 89104756279, 336752825864, 1271998719875, 4802187032270, 18120902471019, 68347041380528, 257673014416775

Offset: 0

Alois P. Heinz, May 13 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..550
Wikipedia, Counting lattice paths

Cf. A059841, A308087, A308114.

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

f[p_List] := p + {0, p[[1]]}; f[0] = 0;
b[{x_, y_}] := b[{x, y}] = If[y == 0, {1, 1},
     f[Sum[Sum[If[GCD[h, v] == 1,
     b[Sort[{x-h, y-v}]], {0, 0}], {v, 1, y}], {h, 1, x}]]];
a[n_] := b[{n, n}][[2]];
a /@ Range[0, 30] (* Jean-François Alcover, Apr 05 2021, after Alois P. Heinz *)

a(n) mod 2 = 1 - (n mod 2) = A059841(n).

a(n) ~ c * d^n * sqrt(n), where d = 3.7137893481485186502229788321701955452444... and c = 0.0685686817861124238901083560487601593693... - Vaclav Kotesovec, May 24 2019

A308113 Number of lattice paths from (0,0) to (n,n) that do not go above the diagonal x=y and consist of steps (h,v) with min(h,v) > 0 and gcd(h,v) = 1.

Original entry on oeis.org

1, 1, 1, 2, 7, 22, 68, 205, 634, 2011, 6490, 21178, 69785, 231940, 776794, 2618951, 8881373, 30274185, 103673227, 356500914, 1230497234, 4261633997, 14805279769, 51580807121, 180173390369, 630864082719, 2213834486422, 7784823272163, 27427361186479

Offset: 0

Alois P. Heinz, May 13 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..550
Wikipedia, Counting lattice paths

Cf. A308087, A308114.

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

b[x_, y_] := b[x, y] = If[y == 0, 1, Sum[Sum[If[x + v > y + h || GCD[h, v] > 1, 0, b[x - h, y - v]], {v, 1, y}], {h, 1, x}]];
a[n_] := b[n, n];
a /@ Range[0, 30] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz *)

a(n) ~ c * d^n / n^(3/2), where d = 3.7137893481485186502229788321701955452444... and c = 0.47404607017890475336081188752626598456... - Vaclav Kotesovec, May 24 2019

cp's OEIS Frontend

A308112 Total number of nodes summed over all lattice paths from (0,0) to (n,n) that consist of steps (h,v) with min(h,v) > 0 and gcd(h,v) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula