

A145835


Number of compositions of the n X n grid graph


2



1, 12, 1434, 1691690, 19719299768, 2271230282824746, 2584855762327078145444, 29068227444022728740767607050, 3230042572278849047360048508956727420, 3546545075986984198328715750838554116235343894
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The number of compositions of the n X n grid graph is the number of partitions of an n X n square into regions of orthogonally connected unit squares.


LINKS

Table of n, a(n) for n=1..10.
A. Knopfmacher and M. E. Mays, Graph compositions I: Basic enumeration, Integers, 1 (2001), #A4
J. N. Ridley and M. E. Mays, Compositions of unions of graphs, Fib. Quart., 42 (2004), 222230.
Frank Simon, Algebraic Methods for Computing the Reliability of Networks, Dissertation, Doctor Rerum Naturalium (Dr. rer. nat.), Fakultät Mathematik und Naturwissenschaften der Technischen Universität Dresden, 2012.  From N. J. A. Sloane, Jan 04 2013


EXAMPLE

For n=2 the a(2)=12 partitions of a 2x2 square are: 1 partition into a single 2x2 region; 4 partitions into a 3square 'L' shape and an isolated corner; 2 partitions into 2 1x2 bricks; 4 partitions into a 1x2 brick and 2 isolated squares; and 1 partition into 4 isolated squares.


CROSSREFS

Cf. A110476.
Sequence in context: A171484 A230519 A235535 * A008992 A260448 A271514
Adjacent sequences: A145832 A145833 A145834 * A145836 A145837 A145838


KEYWORD

hard,nonn


AUTHOR

Brian Kell, Oct 21 2008


EXTENSIONS

Terms for n=7,8,9 from Frank Simon, Oct 25 2011
a(10) from Frank Simon's thesis added by N. J. A. Sloane, Jan 04 2013


STATUS

approved



