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.

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

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

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

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(n-i, k-j), 0), j=0..k), i=0..n))
    end:
T:= (n, k)-> b(k, n-k):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Apr 26 2023

Prog

(PARI)
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}
{ my(A=T(10)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Apr 12 2023

Crossrefs

Columns k=0..1 give: A000012, A000217.

T(2n,n) gives A368639.

Row sums give A368672.

Cf. A059576.

Sequence in context: A176668 A054120 A299146 * A114176 A056241 A162745

Adjacent sequences: A362239 A362240 A362241 * A362243 A362244 A362245

Keyword

nonn,tabl

Author

Keith S. Reid, Apr 12 2023

Status

approved