A288958 Number of cliques in the n X n rook graph.

1, 2, 9, 34, 105, 286, 721, 1730, 4017, 9118, 20361, 44914, 98137, 212798, 458529, 982786, 2096865, 4456126, 9436825, 19922546, 41942601, 88079902, 184548849, 385875394, 805305745, 1677720926, 3489660201, 7247756530, 15032384697, 31138511998, 64424508481

Offset: 0

Author

Eric W. Weisstein, Jun 20 2017

Keywords

• nonn
• easy

Comments

Also the number of independent vertex sets in the n X n rook complement graph. - Eric W. Weisstein, Sep 11 2017

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000
• Eric Weisstein's World of Mathematics, Clique
• Eric Weisstein's World of Mathematics, Independent Vertex Set
• Eric Weisstein's World of Mathematics, Rook Complement Graph
• Eric Weisstein's World of Mathematics, Rook Graph
• Index entries for linear recurrences with constant coefficients, signature (7,-19,25,-16,4).

Crossrefs

Main diagonal of A384120.

Programs

Mathematica

LinearRecurrence[{7, -19, 25, -16, 4}, {2, 9, 34, 105, 286}, 20]
Table[1 + 2 n (2^n - 1) - n^2, {n, 20}]
CoefficientList[Series[(2 - 5 x + 9 x^2 - 12 x^3 + 4 x^4)/((1 - x)^3 (1 - 2 x)^2), {x, 0, 20}], x]

Formula

a(n) = 1 + 2*n*(2^n - 1) - n^2.

a(n) = 7*a(n-1) - 19*a(n-2) + 25*a(n-3) - 16*a(n-4) + 4*a(n-5).

G.f.: (1 - 5*x + 14*x^2 - 16*x^3 + 4*x^4)/((1 - x)^3*(1 - 2*x)^2).

Extensions

a(0) = 1 prepended by Andrew Howroyd, May 22 2025