A247944 -id:A247944 - cp's OEIS frontend

A247943 2-dimensional array T(n, k) listed by antidiagonals giving the number of acyclic paths in the graph G(n, k) whose vertices are the integer lattice points (p, q) with 0 <= p < n and 0 <= q < k and with an edge between v and w iff the line segment [v, w] contains no other integer lattice points.

0, 2, 2, 6, 60, 6, 12, 1058, 1058, 12, 20, 25080, 140240, 25080, 20, 30, 822594, 58673472, 58673472, 822594, 30, 42, 36195620, 28938943114, 490225231968, 28938943114, 36195620, 42, 56, 2069486450

Offset: 1

Rob Arthan, Sep 27 2014

There is an edge between v = (p, q) and w = (r, s) iff p - r and q - s are coprime.
G(3, 3) is used for Android screen lock security patterns (see StackExchange link).
The nonzero entries on the diagonal of this sequence comprise the row sums of A247944.

			G(2,2) is the complete graph on 4 vertices, hence T(2, 2) = 4*3 + 4*3*2 + 4*3*2*1 = 60.
T(n, k) for n + k <= 8 is as follows:
.0........2...........6...........12..........20.......30..42
.2.......60........1058........25080......822594.36195620
.6.....1058......140240.....58673472.28938943114
12....25080....58673472.490225231968
20...822594.28938943114
30.36195620
42

StackExchange, Combination of smartphones' pattern password, 2014

Cf. A247944.

A360063 Triangle read by rows: T(m,n) is the number of Hamiltonian cycles in the graph whose nodes are the integer lattice points (x,y) with 0 <= x < m and 0 <= y < n, and with an edge between two nodes if there is no other integer lattice point on the line segment between them; 1 <= n <= m.

Original entry on oeis.org

0, 0, 3, 0, 24, 1152, 0, 354, 436416, 2595450592, 0, 8138, 129422880

Offset: 1

Pontus von Brömssen, Jan 24 2023

The graph represents tree-to-tree visibility in Euclid's orchard. It also appears in A247943, A247944, and A360062. Is there an established name for it?

			Triangle begins:
  m\n| 1    2         3          4  5
  ---+-------------------------------
  1  | 0
  2  | 0    3
  3  | 0   24      1152
  4  | 0  354    436416 2595450592
  5  | 0 8138 129422880          ?  ?

Wikipedia, Euclid's orchard.

Cf. A247943, A247944, A321172, A360062.

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs