login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 19:09 EST 2019. Contains 329323 sequences. (Running on oeis4.)