How many possible paths?
December 15, 2022 9:48 AM   Subscribe

I am trying to calculate the number of unique paths through a grid that loop back to only one starting point. I think of this as an extension of the old telephone game. If I tell one person, and they tell the next person, what are all the possible paths for the message to travel through the group and return to me?

I started trying to solve this with a 2x2 grid with the points labeled 1, 2, 3 and 4. I am number 1 and there are three other people.

1 2
3 4

I got the path 1 to 2 and then back to 1 (noted here as 12 since we always return to me), plus the paths 13, 14, 123, 124, 132, 134, 142 and 143 . So 9 paths.

But, it gets WAY more complicated with a 3x3 grid (points labeled 1 - 9).

1 2 3
4 5 6
7 8 9

There are the 9 original 2-point paths.

Then the three point paths: 123, 124, 125...132. 134, 135...etc. (56 of them, I think.)

The four point paths: 1234, 1235...1324, 1345, 1346 etc. (336 of them, I think).

The five point paths, the six point paths, etc. through to the nine point paths.

How many possible paths are there through an n x n sized grid?
What is the generalized formula for this?
posted by gnossos to Science & Nature (6 answers total) 2 users marked this as a favorite
 
If you can do a path "1 3" in the 3×3 grid, skipping 2, then does it matter it's on a grid? If you arranged them in a circle would the paths available be exactly the same?

If so, then you're picking how many subsets you can pick out of 8, since you always include 1- which is 2^8. Subtract 1 if you don't want to include the path with 1 element. If you always have n² elements the formula is 2^(n²-1)-1

The logic is that each time you increase the number of elements by 1, you double the number of paths.
posted by BungaDunga at 10:00 AM on December 15, 2022


Oh, wait, 143 and 134 are different paths (duh), so it's not combinations we're counting, we want to count permutations, so you need to count permutations, not combinations. Don't have the time to work this out unfortunately, hopefully someone else will come along.
posted by BungaDunga at 10:16 AM on December 15, 2022


I was introduced to the Drunken Walk in a programming class.
posted by theora55 at 10:38 AM on December 15, 2022


It looks like any point on the grid can link to any other point, without their having to be directly or diagonally adjacent, is that correct?

Also, is there a reason you've omitted 1234, 1243, 1324, 1342, 1423, and 1432 from the 2x2 example?

If that was an unintentional omission, and my first assumption was correct, you're basically looking for an ordered list of k unique numbers, chosen from the set {1..n^2}\1 (i.e., the set of integers between (inclusively) 1 and n squared that aren't 1, equivalently, the set of integers between 2 and n squared, inclusive), and you want the sum of that for all k between 1 and n squared. The summands are given by the partial permutation formula mPk (with m = n^2-1 for your n x n grid). This checks with your cases for 3x3 since 8P2 is 56 and 8P3 is 336.

To find the totals in python:
>>> for n in range(2, 10): print(n, sum(math.perm(n*n-1, k) for k in range(1, n*n)))
2 15
3 109600
4 3554627472075
5 1686553615927922354187744
6 28088408347805994933529600180306266460975
7 33744521175215207580610849391551744205299790387485206653398080
8 5389288156715688797574170724637602641365768984616696724053991331785579414134712244547835
9 194545954561539067326581042506243811231423891946873480598031074615399345559765318585225493549256921092507319165187339200
where the "2 15" case corresponds to the 9 examples you found for the 2x2 case plus the 6 length-4 possibilities.
posted by 7segment at 10:47 AM on December 15, 2022 [2 favorites]


Best answer: I'm not sure I understand the question correctly, but you count permutations with a the formula P(n, r) = n! / (n - r)! (n is the total number of items, r is the number of items being selected), so you should be able to sum that up for values of r from 2 to the total number of items. You also need to subtract one from each of those, since the starting item is fixed. So, your 2x2 example is:

3!/(3-1)! = 3 (number of length 2 paths)
3!/(3-2)! = 6 (number of length 3 paths)
3!/(3-3)! = 6 (number of length 4 paths)

for a sum of 15

for 3x3:
8!/(8-1)! = 8
8!/(8-2)! = 56
8!/(8-3)! = 336
8!/(8-4)! = 1680
8!/(8-5)! = 6720
8!/(8-6)! = 20160
8!/(8-7)! = 40320
8!/(8-8)! = 40320

for a sum of 109600

Which I think is just a different way of saying the same thing 7segment is.
posted by wesleyac at 11:08 AM on December 15, 2022 [3 favorites]


There's an entry in the Online Encyclopedia of Integer Sequences for a very similar sequence. The sequence in the link isn't exactly the same -- it's based on the number of people instead of the size of the grid, and it counts the null path 1, so it's 1 larger than your sequence, but the 9th entry, 109601, matches wesleyac and 7segment's calculations for the 3x3 grid.

The entry also gives a recurrence for the sequence: it satisfies a(n+1)=n*a(n) + 1. So, you have
a(1) = 1 path for 1 person
a(2) = 1*1 + 1 = 2 paths for two people (1, 12)
a(3) = 2*2 + 1 = 5 for 3 (1, 12, 13, 123, 132)
a(4) = 3*5 + 1 = 16
a(5) = 4*16 +1 = 65
and so on.
posted by ectabo at 12:11 PM on December 15, 2022 [2 favorites]


« Older What to do with these golden handcuffs (YANMFP)   |   Meet in the middle: St. Louis, Chicago, and Omaha... Newer »
This thread is closed to new comments.