How many patterns are there with 9 dots?

  • Context: Undergrad 
  • Thread starter Thread starter AdrianZ
  • Start date Start date
  • Tags Tags
    Patterns
Click For Summary

Discussion Overview

The discussion revolves around the combinatorial problem of determining the number of unique patterns that can be created using 9 dots arranged in a square grid. Participants explore various requirements and definitions of what constitutes a valid pattern, including whether all dots must be used and how paths are counted.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • Some participants clarify that a pattern is defined as a connected path between dots without revisiting any dot.
  • There is a suggestion that the problem relates to Hamiltonian paths, although it is noted that not all dots need to be included in a valid pattern.
  • One participant proposes that at least 4 dots should be chosen, but later suggests that this requirement could be relaxed.
  • Several formulas for counting patterns are presented, including specific calculations for paths of varying lengths (1 to 9 dots).
  • One participant corrects their earlier formula for the number of combinations for paths of 2 dots, indicating a factor of 2 was initially overlooked.
  • Another participant provides a Python program's output, detailing the number of combinations for paths of different lengths, with variations depending on whether paths are considered distinct based on order.
  • There is a discussion about the implications of collinearity among points and how it affects the counting of patterns.

Areas of Agreement / Disagreement

Participants express varying interpretations of the problem's requirements, particularly regarding the necessity of using all dots and the treatment of path order. There is no consensus on a single approach or formula, and multiple competing views remain throughout the discussion.

Contextual Notes

Some limitations in the discussion include unresolved assumptions about the definition of a pattern, the treatment of collinear points, and the specific conditions under which paths are counted as distinct.

AdrianZ
Messages
318
Reaction score
0
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).
 
Physics news on Phys.org
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/
 
Edgardo said:
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.
 
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.
Code: 
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)
 
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:
Code: 
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.

Code: 
>>> ================================ 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:

Code: 
>>> ================================ 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.
 
Last edited:
AdrianZ said:
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.
 
The square looks like this:
Code: 
0 1 2
3 4 5
6 7 8

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

Code: 
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:

Code: 
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
 
Edgardo said:
The square looks like this:
Code: 
0 1 2
3 4 5
6 7 8

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

Code: 
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:

Code: 
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.
 
Last edited:
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:

Code: 
superFun(5,3)

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

Attachments

Last edited:

Similar threads

Undergrad A Sequence T based on the Rule of Three
  • · Replies 15 ·
Replies
15
Views
2K
Making a Custom QR code plaque
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Cat Chasing Red Dot Faster Than c: Results & Analysis
  • · Replies 13 ·
Replies
13
Views
3K
Undergrad Hossenfelder: Delayed Choice Quantum Eraser, Debunked?
  • · Replies 3 ·
Replies
3
Views
5K
Undergrad How To Experimentally Confirm the Wigner-Von Neumann Interpretation
  • · Replies 52 ·
2
Replies
52
Views
7K
Undergrad Interference Patterns & Photon Paths: Exploring the Double Slit Experiment
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Lagrangian total time derivative for the velocity
  • · Replies 21 ·
Replies
21
Views
2K
High School Double slit experiment with electrons
  • · Replies 17 ·
Replies
17
Views
4K
Combinatorics: Counting quadrilaterals in triangle pattern
  • · Replies 2 ·
Replies
2
Views
3K
Graduate Measurement problem and many worlds
  • · Replies 3 ·
Replies
3
Views
2K