A291593 Number of (non-null) connected induced subgraphs in the n X n rook complement graph.

1, 6, 397, 64627, 33548446, 68719441230, 562949953224709, 18446744073708514623, 2417851639229258344134994, 1267650600228229401496677070990, 2658455991569831745807614120434011325, 22300745198530623141535718272648360902487971

Offset

1,2

Comments

From Andrew Howroyd, Aug 30 2017: (Start)

The vertex sets inducing disconnected subgraphs are:

- two or more vertices taken from a single row or column,

- any vertex combined with at least one from the same row and at least one from the same column,

- four vertices forming the corners of a rectangle. (End)

Links

Andrew Howroyd, Table of n, a(n) for n = 1..50

Eric Weisstein's World of Mathematics, Connected Graph.

Eric Weisstein's World of Mathematics, Rook Complement Graph.

Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph.

Formula

a(n) = 2^(n^2) - 2*n*(2^n-n-1) - n^2*(2^(n-1)-1)^2 - binomial(n,2)^2 - 1. - Andrew Howroyd, Aug 30 2017

Mathematica

Table[2^(n^2) - 2 n (2^n - n - 1) - n^2 (2^(n - 1) - 1)^2 - Binomial[n, 2]^2 - 1, {n, 10}]

Prog

(PARI) a(n) = 2^(n^2) - 2*n*(2^n-n-1) - n^2*(2^(n-1)-1)^2 - binomial(n, 2)^2 - 1; \\ Andrew Howroyd, Aug 30 2017

Crossrefs

Cf. A290949, A362576.

Sequence in context: A058807 A350017 A000474 * A029591 A151578 A172227

Adjacent sequences: A291590 A291591 A291592 * A291594 A291595 A291596

Keyword

nonn,easy

Author

Eric W. Weisstein, Aug 27 2017

Extensions

a(6)-a(12) from Andrew Howroyd, Aug 30 2017

Status

approved