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,1

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.

Links

Table of n, a(n) for n=2..46.

StackExchange, Combination of smartphones' pattern password, 2014.

Example

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

Crossrefs

Cf. A247943.

Sequence in context: A260261 A080495 A090776 * A346865 A123980 A097704

Adjacent sequences: A247941 A247942 A247943 * A247945 A247946 A247947

Keyword

nonn,tabl

Author

Rob Arthan, Sep 27 2014

Status

approved