login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #29 Oct 31 2014 20:53:42

%S 12,24,56,24,304,172,0,1400,1696,400,0,5328,15580,6072,836,0,16032,

%T 132264,88320,18608,1496,0,35328,1029232,1225840,403156,44520,2564,0,

%U 49536,7286016,16202952,8471480,1296952,100264,4080,0,32256,46456296,203422072,172543276,36960168,3864332,201992,6212

%N 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.

%C G(3) is used for Android screen lock security patterns (see StackExchange link).

%C There is an edge between v = (p, q) and w = (r, s) iff p - r and q - s are coprime.

%C 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.

%C The row sums of this sequence form the nonzero entries on the diagonal of A247943.

%H StackExchange, <a href="http://math.stackexchange.com/questions/37167/combination-of-smartphones-pattern-password">Combination of smartphones' pattern password</a>, 2014.

%e 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.

%e T(n, k) for n + k <= 11 is as follows:

%e ..12.....24......24........0.........0.........0........0.....0.0

%e ..56....304....1400.....5328.....16032.....35328....49536.32256

%e .172...1696...15580...132264...1029232...7286016.46456296

%e .400...6072...88320..1225840..16202952.203422072

%e .836..18608..403156..8471480.172543276

%e 1496..44520.1296952.36960168

%e 2564.100264.3864332

%e 4080.201992

%e 6212

%e 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

%Y Cf. A247943.

%K nonn,tabl

%O 2,1

%A _Rob Arthan_, Sep 27 2014