cp's OEIS Frontend

A362242 Triangle read by rows: T(n,k) is the number of lattice paths from (0,0) to (k,n-k) using steps (i,j) with i,j>=0 and gcd(i,j)=1.

%I A362242 #31 Mar 16 2025 09:27:06
%S A362242 1,1,1,1,3,1,1,6,6,1,1,10,17,10,1,1,15,39,39,15,1,1,21,76,111,76,21,1,
%T A362242 1,28,135,266,266,135,28,1,1,36,222,566,757,566,222,36,1,1,45,346,
%U A362242 1100,1876,1876,1100,346,45,1,1,55,515,1997,4197,5321,4197,1997,515,55,1
%N A362242 Triangle read by rows: T(n,k) is the number of lattice paths from (0,0) to (k,n-k) using steps (i,j) with i,j>=0 and gcd(i,j)=1.
%C A362242 These are the lattice paths that move in straight lines between grid points. No distinction is made between a path passing through a grid point and a path stopping at the grid point. For example the path (0,0)->(2,2) is considered the same as (0,0)->(1,1)->(2,2).
%H A362242 Andrew Howroyd, <a href="/A362242/b362242.txt">Table of n, a(n) for n = 0..1325</a> (rows 0..50)
%e A362242 Triangle begins:
%e A362242   1;
%e A362242   1,  1;
%e A362242   1,  3,  1;
%e A362242   1,  6,  6,  1;
%e A362242   1, 10, 17, 10,  1;
%e A362242   1, 15, 39, 39, 15, 1;
%e A362242   ...
%e A362242 There are three paths across a one by one lattice. There are six across a two by one lattice.
%p A362242 b:= proc(n, k) option remember; `if`(min(n, k)=0, 1, add(add(
%p A362242       `if`(igcd(i, j)=1, b(n-i, k-j), 0), j=0..k), i=0..n))
%p A362242     end:
%p A362242 T:= (n, k)-> b(k, n-k):
%p A362242 seq(seq(T(n, k), k=0..n), n=0..10);  # _Alois P. Heinz_, Apr 26 2023
%t A362242 b[n_, k_] := b[n, k] = If[Min[n, k] == 0, 1, Sum[Sum[If[GCD[i, j] == 1, b[n - i, k - j], 0], {j, 0, k}], {i, 0, n}]]; T[n_, k_] := b[k, n - k]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* _Jean-François Alcover_, Mar 16 2025, after _Alois P. Heinz_ *)
%o A362242 (PARI)
%o A362242 T(n)={my(v=vector(n)); v[1]=[1]; for(n=2, #v, v[n]=vector(n, k, sum(i=0, k-1, sum(j=0,n-k, if(gcd(i,j)==1, v[n-i-j][k-i] ) )))); v}
%o A362242 { my(A=T(10)); for(i=1, #A, print(A[i])) } \\ _Andrew Howroyd_, Apr 12 2023
%Y A362242 Columns k=0..1 give: A000012, A000217.
%Y A362242 T(2n,n) gives A368639.
%Y A362242 Row sums give A368672.
%Y A362242 Cf. A059576.
%K A362242 nonn,tabl
%O A362242 0,5
%A A362242 _Keith S. Reid_, Apr 12 2023