Math: Finding x number of paths of y length

[Maryring]

So I'm having a bit of a math problem which I can't seem to find an easy solution for. I've got this diagram, with a question to find how many paths of length 4 that exists between any randomly chosen nodes. I'm sure there's a formula for it. There always seems to be a formula for it. But I can't figure it out, and I'd rather not have to manually count each possible solution as that's inefficient.

There's a total of 8 vertices and 16 edges on the graph, but not all vertices have the same amount of edges. They do average out to 4 edges for each vertice though.

If anyone knows how to solve this conundrum I'd be grateful for your help. Thanks in advance.

http://i35.photobucket.com/albums/d174/Maryring/Nodes.png (http://s35.photobucket.com/user/Maryring/media/Nodes.png.html)

[Teddy]

Hmm, if there is, I'm pretty sure the number depends on which two nodes you pick. If you pick the left topmost node and right bottommost node, there are still more paths I haven't been able find, but if you look at the two nodes connected by e8, I'm pretty the number is just 4...

I could write a computer program which calculated it for you, but that would just be the same as having a machine do the brute force solution instead of you..

[Red Fel]

Is this supposed to be like the traveling salesman problem? Isn't that supposed to be the stuff of nightmares?

[eggynack]

My thinking is that you might be able to get there by counting up the paths of length 4. I think dividing that by four would get you the probabilistic answer, cause every unique path of length four has a unique start and end point, and would thus be associated with a fourth of the nodes. Or something. That sounds easier than counting for every two nodes to be, for some reason. If you need an efficient way to get the number from a pair of nodes, I dunno. Thinking through weird decompositions right now.

[Eldan]

Is this supposed to be like the traveling salesman problem? Isn't that supposed to be the stuff of nightmares?

No, travelling salesman is how to connect all points on a map with the shortest path travelled. This is about getting all the possible paths between points. Some similarities, but not the same.

Unless I'm mistaken, the graph is symmetrical around the centre point. That should simplify it a bit. But then, I get stuck too... I have a few semi-formulas, but none that actually work...

It's been too long since I did something like this.

[shawnhcorey]

Is this supposed to be like the traveling salesman problem? Isn't that supposed to be the stuff of nightmares?


No, travelling salesman is how to connect all points on a map with the shortest path travelled. This is about getting all the possible paths between points. Some similarities, but not the same.

And like the travelling-salesman problem, it is NP-hard (https://en.wikipedia.org/wiki/NP-hardness). That means there is no formula for it. The only way to solve it is the hard way: explore every possibility until a solution is found.

[lio45]

Yeah, that's what I was about to say. The nodes are different, so the answer depends on which two nodes you happen to pick; you won't be able to find a formula for this.