Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 Re: Computer Math » Self Avoiding Walk » 2014-10-20 11:28:43

I think you're interested in calculating the number of lattice animals or polyominoes that can fit inside a square section of the square lattice, see http://en.wikipedia.org/wiki/Polyomino

The best way to count these is via transfer matrix methods, and the longest enumerations have been done by Iwan Jensen: http://www.ms.unimelb.edu.au/~iwan/animals/Animals_ser.html (He may well have even longer series that he just hasn't got around to posting on the web.)

There's also a paper on the topic here: http://arxiv.org/abs/cond-mat/0007238 , and the oeis page is: https://oeis.org/A001168

Unfortunately, these counts are for the total number of polyominoes with n squares, and so don't directly answer your question. However, the number of polyominoes inside a square is an intermediate step in the above transfer matrix calculation.

If you let me know what you need these counts for perhaps I can be of more help. Implementing a transfer matrix calculation takes a bit of time and effort, but for what it's worth the enumeration of polyominoes is on the easier end of the spectrum of problems that are studied this way.

Edit: this is a much better paper to read on the enumeration method: http://arxiv.org/abs/cond-mat/0007239

Board footer

Powered by FluxBB