Ugh, I've been using Twitter too much! I just wanted to star that.
How many combinations of this pattern are there?
- Thread starter izoneiz
- Start date
Ugh, I've been using Twitter too much! I just wanted to star that.
Soldato
- Joined
- 15 Feb 2011
- Posts
- 10,234
- Location
- Slough
i've figured out how to do t=2 , but i can see this being a rather complicated function for anything bigger than two points because i'd have to work out how to exclude cycles.
for a path of length 2 i thought i;d start in the middle, looking at how many paths could reach the middle point and how many possible paths were remaining once the middle point was reached.
for:
P = Number of Paths
T = Path length = 2
N = Number of points along one edge of the square
P = num(paths can reach one corner) * (num paths from one corner - 1) * num corners
+ num(paths can reach one edge) * (num paths from one edge - 1) * num edge points
+ num(paths can reach one centre point) * (num paths from one centre point - 1) * num centre points
the number of paths that can reach one point is the same as the number of paths going out of it. for corners this is 3, for edges its 5 and for centre points its 8
so we get P = 3*2*num corners + 5*4*num edges + 8*7*num centre points
P = 6*4 + 20*4(n-2) + 56*((n-2)^2)
P = 24 + 80N - 160 + 56N^2 - 224N + 224
P = 56N^2 -144N + 88
and obviously if N<=1, P = 0
anyone got any bright ideas for t = 3?
for a path of length 2 i thought i;d start in the middle, looking at how many paths could reach the middle point and how many possible paths were remaining once the middle point was reached.
for:
P = Number of Paths
T = Path length = 2
N = Number of points along one edge of the square
P = num(paths can reach one corner) * (num paths from one corner - 1) * num corners
+ num(paths can reach one edge) * (num paths from one edge - 1) * num edge points
+ num(paths can reach one centre point) * (num paths from one centre point - 1) * num centre points
the number of paths that can reach one point is the same as the number of paths going out of it. for corners this is 3, for edges its 5 and for centre points its 8
so we get P = 3*2*num corners + 5*4*num edges + 8*7*num centre points
P = 6*4 + 20*4(n-2) + 56*((n-2)^2)
P = 24 + 80N - 160 + 56N^2 - 224N + 224
P = 56N^2 -144N + 88
and obviously if N<=1, P = 0
anyone got any bright ideas for t = 3?
I had a go but got very stuck. n obviously cannot be 0 and no paths are possible if n = 1.
The first grid size where you can have paths is n = 2. Looking at possible paths for this grid size, the formula I came up with is P=6(2^t)
Which gives 1t = 12, 2t = 24, 3t = 48
Those path numbers appear to be accurate for n = 2 (ie a 2 by 2 board) but I've no idea how to factor n into a formula. n equal to 0 or 1 needs to always result in P = 0 then n = 2 needs to suddenly jump into the formula above. I also haven't looked at all at how things look at n = 3 and beyond.
The first grid size where you can have paths is n = 2. Looking at possible paths for this grid size, the formula I came up with is P=6(2^t)
Which gives 1t = 12, 2t = 24, 3t = 48
Those path numbers appear to be accurate for n = 2 (ie a 2 by 2 board) but I've no idea how to factor n into a formula. n equal to 0 or 1 needs to always result in P = 0 then n = 2 needs to suddenly jump into the formula above. I also haven't looked at all at how things look at n = 3 and beyond.
Last edited:
Soldato
- Joined
- 15 Feb 2011
- Posts
- 10,234
- Location
- Slough
i've just realised that all my talk of cycles is complete rubbish. you can go in a complete circle, but you cant go round any of the path the second time
luckily that doesnt affect my current posts, but it means i've got to change my way of thinking a bit
luckily that doesnt affect my current posts, but it means i've got to change my way of thinking a bit
Associate
- Joined
- 12 May 2005
- Posts
- 1,782
Initial observation suggests the number of possibilities is exponentially large.
We can visit nodes up to 8 times and can cross paths up to 2 times.
Number of nodes = n * n
Number of vertices = 8*inside nodes + 3*corner nodes + 5*edge nodes edit: no good they overlap
The total number of possible paths length t will be derived from the number of nodes and the number of vertices.
I would start by finding a formula for the number of vertices using n. n = 1 v = 0. n = 2 v = 6 n = 3 v = 20... n = 4 v = 42?
We can visit nodes up to 8 times and can cross paths up to 2 times.
Number of nodes = n * n
Number of vertices = 8*inside nodes + 3*corner nodes + 5*edge nodes edit: no good they overlap
The total number of possible paths length t will be derived from the number of nodes and the number of vertices.
I would start by finding a formula for the number of vertices using n. n = 1 v = 0. n = 2 v = 6 n = 3 v = 20... n = 4 v = 42?
Last edited:
Yes, the grid is always square.
Could one of you bright buttons have a stab at how many combinations we're talking about for say: n = 4, t = 4? An educated guess. I want to know if we're talking hundreds or tens of thousands or perhaps more?
I'm going to email my faculty at uni and have the PhDs look at it.