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

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

1,1

Comments

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

Links

Table of n, a(n) for n=1..30.

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).

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.: x*(2 - 5*x + 9*x^2 - 12*x^3 + 4*x^4)/((1 - x)^3*(1 - 2*x)^2).

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]

Crossrefs

Sequence in context: A263685 A334443 A301868 * A212348 A000524 A289614

Adjacent sequences: A288955 A288956 A288957 * A288959 A288960 A288961

Keyword

nonn,easy

Author

Eric W. Weisstein, Jun 20 2017

Status

approved