A262245 Number of connected subgraphs of the 12 X 12 grid graph induced by a vertex subset of size n.

1, 144, 264, 724, 2097, 6388, 20168, 65416, 216286, 725208, 2457738, 8398428, 28882214, 99811780, 346190276, 1203840960, 4193106473, 14616481492, 50950086836, 177468099920, 617261864317, 2142475178740, 7416625966122, 25592444012160, 87988338886088

Offset

0,2

Comments

A sequence of this type is known as the "spectrum" in the network reliability literature (see Gertsbakh 2009).

This sequence was computed using the transfer matrix method.

Links

Rohan Shah, Table of n, a(n) for n = 0..144

N. Clisby, I. Jensen, A new transfer-matrix algorithm for exact enumerations: self-avoiding polygons on the square lattice, Journal of Physics A: Mathematical and Theoretical 45(11) 2012.

I. B. Gertsbakh and Y. Shpungin, Models of Network Reliability: Analysis, Combinatorics, and Monte Carlo, Boca Raton, FL, USA: CRC Press, Inc., 2009.

D. J. Klein, G. E. Hite, T. G. Schmalz, Transfer-matrix method for subgraph enumeration: Applications to polypyrene fusenes, Journal of Computational Chemistry 7(4):443-456 1986.

Rohan Shah, Transfer matrix code (written in C++) used to generate this sequence.

Example

a(0) = a(|V|) = 1 as (V, E) is connected.
a(1) = a(|V| - 1) = |V| as (V, E) is connected.
a(142) = binomial(144,2) - 4.

Crossrefs

Sequence in context: A064563 A008436 A250773 * A134341 A125841 A320457

Adjacent sequences: A262242 A262243 A262244 * A262246 A262247 A262248

Keyword

nonn,full,fini

Author

Rohan Shah, Sep 15 2015

Status

approved