Counting lakes
Posted: February 6th, 2009, 12:46 am
On the counting of lakes, from http://www.conwaylife.com/wiki/index.ph ... =Talk:Lake
The definitely true conclusions so far are as follows:
-counting lakes is equivalent to counting SAPs with an extra properties. All the properties are then as follows: 1) the walk must never intersect itself, except 2) the last step of the walk must bring you back to the origin, additionally 3) every step must be orthogonal (that is, in a direction that is perpendicular) to the one before. Finally, the number of steps is equal to half the number of cells in the final lake, but this isn't interesting enough to get its own number.
-notation: the number of steps is going to be k, the number of cells is c, the number of the length of the walk is n, so that "n = k/4 = c/8". I'll also sometimes use italics, and sometimes not. S_n is the number of walks with 4*n steps.
-only walks with "k mod 4 = 0" are allowed (that is, the number of steps must be divisible by 4, and the number of cells by 8)
-you get back to the origin on the last step if and only if (iff from here onward), the number of steps in each direction is k/4
-a walk of length k intersects itself if it contains a walk of length k', k' < k. The reverse also seems to be true.
So then, Nathaniel's program says that for n = {1, 2, 3, ...}, S_n = {1, 0, 1, 1, 4, 7, 31, 98, 446, 1894,...}. And yes, using sets there is a little sketchy notation-wise, but whatever.
My own conjecturing gives a few results that I'm fairly confident in:
-there are (k/2 C k/4)^2 = ((k/2)!)^2/((k/4)!)^4 walks that start and end at the origin, possibly intersecting themselves. The reasoning is that you have k/2 steps in each of the orthogonal directions, and you must assign exactly half to each of the opposite directions along those, then multiply the assignments together for the total number of combinations.
-the above formula gives you 4* too many walks because you can rotate them into one another
-the above formula gives you 2* too many walks because you can reflect them into one another
-the above formula gives you k* too many walks because you can displace them into one another (i.e. any point on the closed walk could be the starting point)
And now, on to the feature speculation!
By the binomial thingie, we have accounted for both requirements 2) and 3), so we only need to deal with avoiding self-intersection. I'm fairly sure that finding all walks of length k and then removing from them all possible walks that include previous self-avoiding walks of length less than k will give us the full count. To this end, my formula guess du jour is something like (this is more of a sketch than a conclusion):
S_(n/4) = 1/8k*((k/2)!)^2/((k/4)!)^4 - sum(S_i*(((k-i)/2)!)^2/(((k-i)/4)!)^4),i=1..k)
n/4 is used so I don't have to multiply k by 4 everywhere or amend my initial definition of S_n. The first part of the equation is obviously just the total number of walks (self-avoiding or not) adjusted for rotation/reflection/displacement. For the second part, the reasoning here is that we take all the smaller walks that we've found thus far, and we attach to each of them tails that would make the whole thing as long as the walks we're looking at now. So, now we have walks of the current length that have loops in them. Since we're counting all the walks we've found with all possible new tails (so that they still start/end at the origin of course), we should thus obtain (the number of) all walks of current walks that have loops in them, i.e. the ones that fail to self-avoid. So, having found the number of such walks, we subtract it from the number of total walks to obtain the number of ones that do self-avoid.
Of course, as I said, this is mostly a sketch. One immediate problem with it, is that the new tails we attach might themselves have loops in them, which would make us double-count a whole lot of cases. One solution I'm pondering is to stick in a bunch more recursion onto the tails we attach to make sure they are loopless in the same way we're trying to use for the walks proper. Before trying that, however, I'd like to figure out whether the rest of the theory/execution holds up.
The definitely true conclusions so far are as follows:
-counting lakes is equivalent to counting SAPs with an extra properties. All the properties are then as follows: 1) the walk must never intersect itself, except 2) the last step of the walk must bring you back to the origin, additionally 3) every step must be orthogonal (that is, in a direction that is perpendicular) to the one before. Finally, the number of steps is equal to half the number of cells in the final lake, but this isn't interesting enough to get its own number.
-notation: the number of steps is going to be k, the number of cells is c, the number of the length of the walk is n, so that "n = k/4 = c/8". I'll also sometimes use italics, and sometimes not. S_n is the number of walks with 4*n steps.
-only walks with "k mod 4 = 0" are allowed (that is, the number of steps must be divisible by 4, and the number of cells by 8)
-you get back to the origin on the last step if and only if (iff from here onward), the number of steps in each direction is k/4
-a walk of length k intersects itself if it contains a walk of length k', k' < k. The reverse also seems to be true.
So then, Nathaniel's program says that for n = {1, 2, 3, ...}, S_n = {1, 0, 1, 1, 4, 7, 31, 98, 446, 1894,...}. And yes, using sets there is a little sketchy notation-wise, but whatever.
My own conjecturing gives a few results that I'm fairly confident in:
-there are (k/2 C k/4)^2 = ((k/2)!)^2/((k/4)!)^4 walks that start and end at the origin, possibly intersecting themselves. The reasoning is that you have k/2 steps in each of the orthogonal directions, and you must assign exactly half to each of the opposite directions along those, then multiply the assignments together for the total number of combinations.
-the above formula gives you 4* too many walks because you can rotate them into one another
-the above formula gives you 2* too many walks because you can reflect them into one another
-the above formula gives you k* too many walks because you can displace them into one another (i.e. any point on the closed walk could be the starting point)
And now, on to the feature speculation!
By the binomial thingie, we have accounted for both requirements 2) and 3), so we only need to deal with avoiding self-intersection. I'm fairly sure that finding all walks of length k and then removing from them all possible walks that include previous self-avoiding walks of length less than k will give us the full count. To this end, my formula guess du jour is something like (this is more of a sketch than a conclusion):
S_(n/4) = 1/8k*((k/2)!)^2/((k/4)!)^4 - sum(S_i*(((k-i)/2)!)^2/(((k-i)/4)!)^4),i=1..k)
n/4 is used so I don't have to multiply k by 4 everywhere or amend my initial definition of S_n. The first part of the equation is obviously just the total number of walks (self-avoiding or not) adjusted for rotation/reflection/displacement. For the second part, the reasoning here is that we take all the smaller walks that we've found thus far, and we attach to each of them tails that would make the whole thing as long as the walks we're looking at now. So, now we have walks of the current length that have loops in them. Since we're counting all the walks we've found with all possible new tails (so that they still start/end at the origin of course), we should thus obtain (the number of) all walks of current walks that have loops in them, i.e. the ones that fail to self-avoid. So, having found the number of such walks, we subtract it from the number of total walks to obtain the number of ones that do self-avoid.
Of course, as I said, this is mostly a sketch. One immediate problem with it, is that the new tails we attach might themselves have loops in them, which would make us double-count a whole lot of cases. One solution I'm pondering is to stick in a bunch more recursion onto the tails we attach to make sure they are loopless in the same way we're trying to use for the walks proper. Before trying that, however, I'd like to figure out whether the rest of the theory/execution holds up.