How many patterns are there with 9 dots?

[AdrianZ]

Recently smart phones using Android have provided a new feature that you can draw a pattern to unlock the screen, so here is the question, how many patterns you can create with 9 dots? By pattern we mean a connected path between 9 dots that you don't go through the same dot more than once. Is my definition of pattern clear?
I guess that would be a nice question to be studied in combinatorics. How many such patterns can you have with n2 dots in general? (Assuming that the dots are numbered and can be distinguished).

[Edgardo]

That problem sounds interesting. Can you tell more about the requirements.

1. Does the path have to contain all dots? If yes it seems to me you are looking for the number of Hamiltonian paths.

2. Is this the 9 dot lock you are talking about?
http://www.stef.be/dev/javascript/patternlock/

[AdrianZ]

That problem sounds interesting. Can you tell more about the requirements.
well, the requirement is that you can not choose one dot for more than once.

1. Does the path have to contain all dots? If yes it seems to me you are looking for the number of Hamiltonian paths.
No, not necessarily. I'm trying to make the problem as simple as possible, actually it requires that you choose at least 4 dots but I think if we ignore that requirement it'll be a bit easier. so you can choose any number of dots you want ranging from 4 to 9 or just any number of dots you want.

2. Is this the 9 dot lock you are talking about?
http://www.stef.be/dev/javascript/patternlock/
looks close. It doesn't let me draw a pattern on it though but yea, the appearance looks the same.

[Edgardo]

Ok, I've started with easy cases.

A few definitions:
The side of the square consists of n dots.
A path consists of p dots.



p # of combinations
--------------------------
1 n*n
2 2(n-1)(2n-1)


This means:
If the path consists of 1 dot there are n*n different codes.
If the path consists of 2 dots there are 2(n-1)(2n-1) different codes.

-------------------------

In general we are searching for a function f_p(n) where p is the length of the code and the square has n dots as its side.
p ranges from 1 to n.

So here, f_1(n) = n^2 and f_2(n) = 2(n-1)(2n-1)

[Edgardo]

My answer for f_2(n) is wrong by a factor of 2. It should be f_2(n)=4(n-1)(2n-1). That is if you count e.g. the paths (5,8) and (8,5) as two different paths. This makes sense if you interpret the paths as code for your smartphone.

With 5 and 8 I mean dots in the following scheme:

0 1 2
3 4 5
6 7 8


As an example I printed the possible codes for a 9 dot lock. The codes consist of 2 dots.


>>> ================================ RESTART ================================
>>>
[0, 1]
[0, 3]
[0, 4]
number of paths starting with dot 0 is: 3
[1, 0]
[1, 2]
[1, 3]
[1, 4]
[1, 5]
number of paths starting with dot 1 is: 5
[2, 1]
[2, 4]
[2, 5]
number of paths starting with dot 2 is: 3
[3, 0]
[3, 1]
[3, 4]
[3, 7]
[3, 6]
number of paths starting with dot 3 is: 5
[4, 0]
[4, 1]
[4, 2]
[4, 3]
[4, 5]
[4, 6]
[4, 7]
[4, 8]
number of paths starting with dot 4 is: 8
[5, 2]
[5, 1]
[5, 4]
[5, 7]
[5, 8]
number of paths starting with dot 5 is: 5
[6, 3]
[6, 4]
[6, 7]
number of paths starting with dot 6 is: 3
[7, 6]
[7, 3]
[7, 4]
[7, 5]
[7, 8]
number of paths starting with dot 7 is: 5
[8, 7]
[8, 4]
[8, 5]
number of paths starting with dot 8 is: 3
solution (totals paths): 40


I also tried to calculate f_3(n), i.e. the number of possible paths consisting of 3 dots. Here is my result:

For n \geq 3 I get: f_3(n)=8(11 - 18n + 7n^2).
This formula does not apply for n=2 since less path configurations are possible (e.g. you don't have the horizontal path (0,1,2) in a n*n =2*2 dot-square).

For a n*n=3*3 dot-square the formula gives: f_3(3)=160
I also wrote a Python program to check this result:


>>> ================================ RESTART ================================
>>>
[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 1, 5]
[0, 3, 1]
[0, 3, 4]
[0, 3, 7]
[0, 3, 6]
[0, 4, 1]
[0, 4, 2]
[0, 4, 3]
[0, 4, 5]
[0, 4, 6]
[0, 4, 7]
[0, 4, 8]
number of paths starting with dot 0 is: 15
[1, 0, 3]
[1, 0, 4]
[1, 2, 4]
[1, 2, 5]
[1, 3, 0]
[1, 3, 4]
[1, 3, 7]
[1, 3, 6]
[1, 4, 0]
[1, 4, 2]
[1, 4, 3]
[1, 4, 5]
[1, 4, 6]
[1, 4, 7]
[1, 4, 8]
[1, 5, 2]
[1, 5, 4]
[1, 5, 7]
[1, 5, 8]
number of paths starting with dot 1 is: 19
[2, 1, 0]
[2, 1, 3]
[2, 1, 4]
[2, 1, 5]
[2, 4, 0]
[2, 4, 1]
[2, 4, 3]
[2, 4, 5]
[2, 4, 6]
[2, 4, 7]
[2, 4, 8]
[2, 5, 1]
[2, 5, 4]
[2, 5, 7]
[2, 5, 8]
number of paths starting with dot 2 is: 15
[3, 0, 1]
[3, 0, 4]
[3, 1, 0]
[3, 1, 2]
[3, 1, 4]
[3, 1, 5]
[3, 4, 0]
[3, 4, 1]
[3, 4, 2]
[3, 4, 5]
[3, 4, 6]
[3, 4, 7]
[3, 4, 8]
[3, 7, 6]
[3, 7, 4]
[3, 7, 5]
[3, 7, 8]
[3, 6, 4]
[3, 6, 7]
number of paths starting with dot 3 is: 19
[4, 0, 1]
[4, 0, 3]
[4, 1, 0]
[4, 1, 2]
[4, 1, 3]
[4, 1, 5]
[4, 2, 1]
[4, 2, 5]
[4, 3, 0]
[4, 3, 1]
[4, 3, 7]
[4, 3, 6]
[4, 5, 2]
[4, 5, 1]
[4, 5, 7]
[4, 5, 8]
[4, 6, 3]
[4, 6, 7]
[4, 7, 6]
[4, 7, 3]
[4, 7, 5]
[4, 7, 8]
[4, 8, 7]
[4, 8, 5]
number of paths starting with dot 4 is: 24
[5, 2, 1]
[5, 2, 4]
[5, 1, 0]
[5, 1, 2]
[5, 1, 3]
[5, 1, 4]
[5, 4, 0]
[5, 4, 1]
[5, 4, 2]
[5, 4, 3]
[5, 4, 6]
[5, 4, 7]
[5, 4, 8]
[5, 7, 6]
[5, 7, 3]
[5, 7, 4]
[5, 7, 8]
[5, 8, 7]
[5, 8, 4]
number of paths starting with dot 5 is: 19
[6, 3, 0]
[6, 3, 1]
[6, 3, 4]
[6, 3, 7]
[6, 4, 0]
[6, 4, 1]
[6, 4, 2]
[6, 4, 3]
[6, 4, 5]
[6, 4, 7]
[6, 4, 8]
[6, 7, 3]
[6, 7, 4]
[6, 7, 5]
[6, 7, 8]
number of paths starting with dot 6 is: 15
[7, 6, 3]
[7, 6, 4]
[7, 3, 0]
[7, 3, 1]
[7, 3, 4]
[7, 3, 6]
[7, 4, 0]
[7, 4, 1]
[7, 4, 2]
[7, 4, 3]
[7, 4, 5]
[7, 4, 6]
[7, 4, 8]
[7, 5, 2]
[7, 5, 1]
[7, 5, 4]
[7, 5, 8]
[7, 8, 4]
[7, 8, 5]
number of paths starting with dot 7 is: 19
[8, 7, 6]
[8, 7, 3]
[8, 7, 4]
[8, 7, 5]
[8, 4, 0]
[8, 4, 1]
[8, 4, 2]
[8, 4, 3]
[8, 4, 5]
[8, 4, 6]
[8, 4, 7]
[8, 5, 2]
[8, 5, 1]
[8, 5, 4]
[8, 5, 7]
number of paths starting with dot 8 is: 15
solution (totals paths): 160
>>>


So, for a 9 dot lock the probability of guessing the correct code is 1/160.

[checkitagain]

Recently smart phones using Android have provided a new feature that you can draw a pattern to unlock the screen, so here is the question, how many patterns you can create with 9 dots? By pattern we mean a connected path between 9 dots that you don't go through the same dot more than once. Is my definition of pattern clear?
How many such patterns can you have with n2 dots in general? (Assuming that the dots are numbered and can be distinguished).

** I don't know what the feature looks like on a smart phone to begin with.

This question assumes that the 9 distinct dots are in a "square form/shape"
in a square lattice, so that, for instance, 0 --> 4 --> 8 is the same as
pattern as 0 --> 8.


But if no three points (or more) were to be collinear, then these two examples
would be different paths/patterns.

[Edgardo]

The square looks like this:

0 1 2
3 4 5
6 7 8


I wrote a Python-program and got the following results:


path with 1 dot => 9 combinations
path with 2 dots => 40 combinations
path with 3 dots => 160 combinations
path with 4 dots => 656 combinations
path with 5 dots => 2776 combinations
path with 6 dots => 11776 combinations
path with 7 dots => 50488 combinations
path with 8 dots => 217408 combinations
path with 9 dots => 941368 combinations


Note: I counted paths such as (0 1 4) and (4 1 0) as two different paths
If you don't differ between those two you have only half the combinations, see below:


path with 1 dot => 9 combinations
path with 2 dots => 20 combinations
path with 3 dots => 80 combinations
path with 4 dots => 328 combinations
path with 5 dots => 1388 combinations
path with 6 dots => 5888 combinations
path with 7 dots => 25244 combinations
path with 8 dots => 108704 combinations
path with 9 dots => 470684 combinations



----

The results above are for the 9-dot-square. In general we are searching for a function f_p(n) where
- p is the number of dots in the path
- a side of a square consists of n dots

For n=3 we get the 9-dot-square.


So far I have found:

f_1(n) = n^2
This is the number of paths consisting of 1 dot.
A path of length 1 is just a dot, and since there are n^2 dots we have n^2 possible paths. Example for n=3:
The number of paths (with 1 dot) in the 9-dot-square is:
f_1(3) = 3^2 = 9

---

f_2(n) = 4(n-1)(2n-1)
This is the number of paths consisting of 2 dots. Such a path corresponds to an edge, so I've just counted the edges. Example for n=3:
f_2(3) = 4(3-1)(6-1) = 40
Note that there are only 20 edges but I counted them twice (see above).

---

f_3(n) = 8(11 - 18n + 7n^2)
This is the number of paths consisting of 3 dots. Here, I counted the different patterns that can be built from a 3-dot-path. Example for n=3:
f_3(3) = 8(11 -18\cdot 3 + 7\cdot 3^2)= 160

[AdrianZ]

The square looks like this:

0 1 2
3 4 5
6 7 8


I wrote a Python-program and got the following results:


path with 1 dot => 9 combinations
path with 2 dots => 40 combinations
path with 3 dots => 160 combinations
path with 4 dots => 656 combinations
path with 5 dots => 2776 combinations
path with 6 dots => 11776 combinations
path with 7 dots => 50488 combinations
path with 8 dots => 217408 combinations
path with 9 dots => 941368 combinations


Note: I counted paths such as (0 1 4) and (4 1 0) as two different paths
If you don't differ between those two you have only half the combinations, see below:


path with 1 dot => 9 combinations
path with 2 dots => 20 combinations
path with 3 dots => 80 combinations
path with 4 dots => 328 combinations
path with 5 dots => 1388 combinations
path with 6 dots => 5888 combinations
path with 7 dots => 25244 combinations
path with 8 dots => 108704 combinations
path with 9 dots => 470684 combinations



----

The results above are for the 9-dot-square. In general we are searching for a function f_p(n) where
- p is the number of dots in the path
- a side of a square consists of n dots

For n=3 we get the 9-dot-square.


So far I have found:

f_1(n) = n^2
This is the number of paths consisting of 1 dot.
A path of length 1 is just a dot, and since there are n^2 dots we have n^2 possible paths. Example for n=3:
The number of paths (with 1 dot) in the 9-dot-square is:
f_1(3) = 3^2 = 9

---

f_2(n) = 4(n-1)(2n-1)
This is the number of paths consisting of 2 dots. Such a path corresponds to an edge, so I've just counted the edges. Example for n=3:
f_2(3) = 4(3-1)(6-1) = 40
Note that there are only 20 edges but I counted them twice (see above).

---

f_3(n) = 8(11 - 18n + 7n^2)
This is the number of paths consisting of 3 dots. Here, I counted the different patterns that can be built from a 3-dot-path. Example for n=3:
f_3(3) = 8(11 -18\cdot 3 + 7\cdot 3^2)= 160

That's good. to be honest I'm creating a new language to formalize everything in an axiomatic flavor. I'll soon share my definitions with you. My main idea is that the number of paths depend on the position of the dot. We got 3 types of dots as far as I've seen.
I'm trying to find a formula like fp(n) as you said.
Can you share the source code of your Python program with me? I've come up with the same results for the cases where the length of the path is 0,1,2 (when we choose 3 dots the path is 2, if we connect k dots the length is k-1 in my definition. so if we choose a single dot the path is zero). but to move forward I should write a program, I can't continue counting with writing down the possibilities on paper.

[Edgardo]

I have attached the Python program. Usage:
Run the file 9dot_main.py in the Python-Shell, e.g. by pressing F5 in idle. In the Python-Shell you can type for example:


superFun(5,3)


This calculates the number of codes consisting of 5 dots for a 3x3 dot square.