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.