

A362242


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


3



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, 1, 28, 135, 266, 266, 135, 28, 1, 1, 36, 222, 566, 757, 566, 222, 36, 1, 1, 45, 346, 1100, 1876, 1876, 1100, 346, 45, 1, 1, 55, 515, 1997, 4197, 5321, 4197, 1997, 515, 55, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

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).


LINKS



EXAMPLE

Triangle begins:
1;
1, 1;
1, 3, 1;
1, 6, 6, 1;
1, 10, 17, 10, 1;
1, 15, 39, 39, 15, 1;
...
There are three paths across a one by one lattice. There are six across a two by one lattice.


MAPLE

b:= proc(n, k) option remember; `if`(min(n, k)=0, 1, add(add(
`if`(igcd(i, j)=1, b(ni, kj), 0), j=0..k), i=0..n))
end:
T:= (n, k)> b(k, nk):


PROG

(PARI)
T(n)={my(v=vector(n)); v[1]=[1]; for(n=2, #v, v[n]=vector(n, k, sum(i=0, k1, sum(j=0, nk, if(gcd(i, j)==1, v[nij][ki] ) )))); v}
{ my(A=T(10)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Apr 12 2023


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



