

A272435


Number of nominoes 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Higher corrected values are supported by exhibiting a(n) distinct nominoes in the nsquare 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 10ominoes
James Stein, 6382660 gzipped 11ominoes
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 Ltromino.


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



