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
]]>I want an algorithm to enumerate all possible ways to color them with black such that there is a path from every black square to every black square through edge connection.
There must be atleast one black square to fulfill this criterion.
Is a good example. (Forget the red tile)
]]>