A247943 -id:A247943 - cp's OEIS frontend

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

12, 24, 56, 24, 304, 172, 0, 1400, 1696, 400, 0, 5328, 15580, 6072, 836, 0, 16032, 132264, 88320, 18608, 1496, 0, 35328, 1029232, 1225840, 403156, 44520, 2564, 0, 49536, 7286016, 16202952, 8471480, 1296952, 100264, 4080, 0, 32256, 46456296, 203422072, 172543276, 36960168, 3864332, 201992, 6212

Offset: 2

Rob Arthan, Sep 27 2014

G(3) is used for Android screen lock security patterns (see StackExchange link).
There is an edge between v = (p, q) and w = (r, s) iff p - r and q - s are coprime.
T(n, k) is nonzero for 1 <= k < n^2 and is zero for k >= n^2, because G(n) always has an acyclic path that contains all n^2 vertices and hence has length n^2 - 1, while a path in G(n) of length n^2 or more cannot be acyclic.
The row sums of this sequence form the nonzero entries on the diagonal of A247943.

			In G(3), the 4 vertices at the corners have valency 5, the vertex in the middle has valency 8 and the other 4 vertices have valency 7, therefore T(3, 2) = 4*5*4 + 8*7 + 4*7*6 = 304.
T(n, k) for n + k <= 11 is as follows:
..12.....24......24........0.........0.........0........0.....0.0
..56....304....1400.....5328.....16032.....35328....49536.32256
.172...1696...15580...132264...1029232...7286016.46456296
.400...6072...88320..1225840..16202952.203422072
.836..18608..403156..8471480.172543276
1496..44520.1296952.36960168
2564.100264.3864332
4080.201992
6212
T(4, k) is nonzero iff k <= 15 and the 15 nonzero values are: 172, 1696, 15580, 132264, 1029232, 7286016, 46456296, 263427744, 1307755352, 5567398192, 19756296608, 56073026336, 119255537392, 168794504832, 119152364256. The sum of these 15 values is A247943(4, 4). - _Rob Arthan_, Oct 19 2014

StackExchange, Combination of smartphones' pattern password, 2014.

Cf. A247943.

A360062 Triangle read by rows: T(m,n) is the number of spanning trees 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

1, 1, 16, 1, 576, 496125, 1, 41616, 1830420480, 375297659043840, 1, 5085025, 10361547386325, 166557643451782840320, 5885897714143664700439342125, 1, 945193536, 144188666818560000, 258848560805325726352932864, 1192037309255692352595217996892160000, 36939045170346949681155330481716034613142893328

Offset: 1

Pontus von Brömssen, Jan 24 2023

			Triangle begins:
  m\n| 1     2          3               4
  ---+-----------------------------------
  1  | 1
  2  | 1    16
  3  | 1   576     496125
  4  | 1 41616 1830420480 375297659043840

Pontus von Brömssen, Table of n, a(n) for n = 1..210 (rows m = 1..20)

Cf. A116469, A247943, A360063.

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

A360062 Triangle read by rows: T(m,n) is the number of spanning trees 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.

Views

Author

Keywords

Examples

Links

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs