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.

%I A308112 #19 Apr 05 2021 09:17:37
%S A308112 1,2,3,10,47,186,703,2640,9979,37980,144713,550666,2093215,7951524,
%T A308112 30186737,114522342,434172249,1644889496,6227677911,23563691408,
%U A308112 89104756279,336752825864,1271998719875,4802187032270,18120902471019,68347041380528,257673014416775
%N 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.
%H A308112 Alois P. Heinz, <a href="/A308112/b308112.txt">Table of n, a(n) for n = 0..550</a>
%H A308112 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>
%F A308112 a(n) mod 2 = 1 - (n mod 2) = A059841(n).
%F A308112 a(n) ~ c * d^n * sqrt(n), where d = 3.7137893481485186502229788321701955452444... and c = 0.0685686817861124238901083560487601593693... - _Vaclav Kotesovec_, May 24 2019
%p A308112 b:= proc(x, y) option remember; `if`(y=0, [1$2],
%p A308112       (p-> p +[0, p[1]])(add(add(`if`(igcd(h, v)=1,
%p A308112        b(sort([x-h, y-v])[]), 0), v=1..y), h=1..x)))
%p A308112     end:
%p A308112 a:= n-> b(n$2)[2]:
%p A308112 seq(a(n), n=0..30);
%t A308112 f[p_List] := p + {0, p[[1]]}; f[0] = 0;
%t A308112 b[{x_, y_}] := b[{x, y}] = If[y == 0, {1, 1},
%t A308112      f[Sum[Sum[If[GCD[h, v] == 1,
%t A308112      b[Sort[{x-h, y-v}]], {0, 0}], {v, 1, y}], {h, 1, x}]]];
%t A308112 a[n_] := b[{n, n}][[2]];
%t A308112 a /@ Range[0, 30] (* _Jean-François Alcover_, Apr 05 2021, after _Alois P. Heinz_ *)
%Y A308112 Cf. A059841, A308087, A308114.
%K A308112 nonn
%O A308112 0,2
%A A308112 _Alois P. Heinz_, May 13 2019