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

Author

Rob Arthan, Sep 27 2014

Keywords

• nonn
• tabl

Comments

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.

Examples

			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
		

Links

• StackExchange, Combination of smartphones' pattern password, 2014.

Crossrefs

Cf. A247943.