On cstheory.stackexchange.com, I recently asked a question about random generation of simple cycles in a grid. But that led naturally to the question: how many cycles are we choosing among, anyway? If it's a smooth number, there might be hope of a random generation algorithm that picks a bunch of small random integers and does something with them (much as one can build a random graph by independently flipping a coin for each possible edge). But if the number of cycles has large prime factors then such a direct generation algorithm seems unlikely. In OEIS I could only find the numbers of cycles in \( 2\times n \) grids and (with the help of mjqxxxx) in \( n\times n \) grids. So I wrote a little program to generate the rest, at least in the cases when one side of the grid is small.

The method is standard in enumerative combinatorics (and it's the method already used for the OEIS \( n\times n \) table): make a list of the possible states that a single column of the pattern could have, set up a recurrence for the partial patterns ending in each possible column, and then calculate the values of the recurrence. The recurrence is represented as a transfer matrix; the rows and columns of the matrix are indexed by states, and a cell is 1 if two states can be adjacent in a pattern and 0 otherwise. Then, if we start with a vector that has a one in the position indexed by a state that describes an empty column to the left of the cycle, multiply it by a power of this matrix, and look at the resulting value in the position indexed by a state that describes an empty column to the right of the cycle, we get the number of cycles as desired.

Rather than thinking of states within a single column as sets of edges, I instead represent them as sets of squares (the squares inside the cycle, forming a simply-connected polyomino). And as well as keeping track of which squares are empty or nonempty, each state has to also keep track of how the nonempty ones are connected, and the transfer matrix has to connect only those pairs of states that have compatible connectivity information, which is a bit messy to calculate. In any case, it seems to work – at least, it generates equal numbers to the ones already in OEIS.

For \( 3\times n \) grids, the numbers of different cycles for n=1, 2, 3, ... are: 6, 40, 213, 1049, 5034, 23984, 114069, 542295, 2577870, 12253948, 58249011, 276885683, 1316170990, 6256394122, 29739651711, 141366874247, 671984773580, 3194266961582, 15183887824311, 72176324719925, ...

For \( 4\times n \) grids, the numbers are: 10, 108, 1049, 9349, 80626, 692194, 5948291, 51139577, 439673502, 3779989098, 32497334055, 279386435639, 2401945965628, 20650054358200, 177533025653767, 1526290165248783, 13121849649571820, 112811405309454694, 969864273118112913, 8338134834111643373, ...

For \( 5\times n \) grids, they are: 15, 275, 5034, 80626, 1222363, 18438929, 279285399, 4237530095, 64300829449, 975566486675, 14800469958185, 224540402345213, 3406558215857382, 51681816786790684, 784078741397570677, 11895467318139343215, 180469294422664219486, 2737947622842077799930, 41538131208455762235922, 630186031186654155280020, ...

This approach uses an amount of memory proportional to the square of the number of states, and the number of states needed to generate an \( m\times n \) grid is something higher than \( 2^m \) (it would be only \( 2^m+1 \) without the connectivity information, but with that information it is larger), so even if you optimized the program to store the matrix as a bitvector and used a more efficient language than my choice (Python), it would be hard to get above \( 20\times n \) or so. Which, coincidentally or not, is where the OEIS table of square grid cycle counts leaves off.

The outcome of the original motivating question is that these are not particularly smooth numbers, by the way. For instance, the last number in the \( 5\times n \) list, 630186031186654155280020, has the large prime factor 34663698085074485989. Anyway, if anyone else wants to play with this, my code is here.




Comments:

ext_87671:
2011-03-19T21:32:32Z
BTW, classical transfer matrix method like above can be thought of as an application of Path Decomposition, and variation based on Tree Decomposition recently came up under name "tree-decomposed transfer matrix" method, http://arxiv.org/abs/1003.4847 Also, chapter 7 in "Polygons, Polyominoes and Polycubes" goes over another method of counting simple cycles in square grid, which uses symmetry to speed up calculation
11011110:
2011-03-19T21:44:06Z
Interesting. Fomin and Thilikos claim that branch-decomposition works better than tree-decomposition for some dynamic programming problems on planar graphs (in part because an optimal branch decomposition can be constructed efficiently, while for tree decomposition one often has to resort to approximations); I wonder how that relates to the transfer matrix method. On the other hand, for grid graphs it seems unlikely to make much difference.
ext_87671:
2011-03-19T22:04:53Z
I haven't looked into branch decomposition because I haven't seen any counting/generation problems solved with branch decomposition.....for square grid, indeed, I've actually compared total cost of counting independent sets in square grid using path and tree decomposition, the difference was about 50% for 5x5 grids, but for larger grids, runtime of two methods actually become more and more similar
11011110:
2011-03-28T21:00:47Z
I found some time to look at the book you mention. Beyond symmetry, there's another big speedup in their calculation: instead of transferring a whole column to the whole next column, they do it one square at a time. The advantage of doing it that way is that the transfer matrix is very sparse (two nonzeros per column) so its effect can be calculated in time proportional to the number of states rather than the square of the number of states. The increased number of times one has to do a transfer, and the increased complexity of having different transfers for different squares within the column, are both more than made up for by the reduction in the cost of each transfer.