Math Is Fun Forum

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