login
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
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
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
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