A272435 Number of n-ominoes in n X n grid (i.e., rookwise connected sets of n cells in a square array with n rows and n columns).

1, 4, 22, 113, 571, 2816, 13616, 64678, 302574, 1397318, 6382660, 28882214, 129640058, 577812724, 2559491834, 11276000877, 49437494408, 215815377168

Offset: 1

Author

Don Knuth, Apr 29 2016

Keywords

• nonn
• more

Comments

Higher corrected values are supported by exhibiting a(n) distinct n-ominoes in the n-square for n=10 and n=11 (see LINKS below). - James Stein, Dec 11 2017

a(n) is the number of connected induced subgraphs with n vertices in the n X n grid graph. - Andrew Howroyd, Apr 27 2020

Examples

			The 22 arrangements for n=3 include three horizontal rows, three vertical rows, and four ways to place each rotation of the L-tromino.
		

References

• This sequence will some day be mentioned in an exercise in section 7.2.2 of The Art of Computer Programming.

Links

• James Stein, 1397318 gzipped 10-ominoes
• James Stein, 6382660 gzipped 11-ominoes
• Eric Weisstein's World of Mathematics, Grid Graph

Crossrefs

Cf. A001168, A059525, A162676.

Extensions

a(10)-a(12) corrected, and a(13)-a(14) added by James Stein, Dec 11 2017

a(15)-a(16) from Andrew Howroyd, Apr 27 2020

a(17)-a(18) from Giovanni Resta, May 01 2020