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,2

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

References

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

Links

Table of n, a(n) for n=1..18.

James Stein, 1397318 gzipped 10-ominoes

James Stein, 6382660 gzipped 11-ominoes

Eric Weisstein's World of Mathematics, Grid Graph

Example

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

Crossrefs

Cf. A001168, A059525, A162676.

Sequence in context: A192470 A274799 A290591 * A106835 A293966 A305554

Adjacent sequences: A272432 A272433 A272434 * A272436 A272437 A272438

Keyword

nonn,more

Author

Don Knuth, Apr 29 2016

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

Status

approved