

A247944


2dimensional 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.


1



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



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 * A123980 A097704 A289132
Adjacent sequences: A247941 A247942 A247943 * A247945 A247946 A247947


KEYWORD

nonn,tabl


AUTHOR

Rob Arthan, Sep 27 2014


STATUS

approved



