A295903 Number of (not necessarily maximal) cliques in the n X n queen graph.

2, 16, 94, 293, 742, 1642, 3458, 7087, 14506, 29804, 61750, 128761, 269822, 566830, 1191898, 2505443, 5261218, 11032048, 23094830, 48265261, 100699222, 209756786, 436255474, 906024343, 1879110362, 3892384372, 8053142758, 16643086817, 34359837166, 70867070134

Offset

1,1

Links

Robert Israel, Table of n, a(n) for n = 1..3305

Eric Weisstein's World of Mathematics, Clique

Eric Weisstein's World of Mathematics, Queen Graph

Index entries for linear recurrences with constant coefficients, signature (6, -11, 0, 21, -18, -5, 12, -4).

Formula

a(n) = 3*2^(n + 1) + n*((-1)^(n + 1) + 2^(n + 2) + n*(9*n - 26) - 2)/2 - 5.

a(n) = 6*a(n-1) - 11*a(n-2) + 21*a(n-4) - 18*a(n-5) - 5*a(n-6) + 12*a(n-7) - 4*a(n-8).

G.f.: x*(2 + 4*x + 20*x^2 - 95*x^3 - 24*x^4 + 113*x^5 + 92*x^6 - 4*x^7)/((-1 + x)^4*(-1 + x + 2*x^2)^2).

Maple

f:=n-> 3*2^(n + 1) + n*((-1)^(n + 1) + 2^(n + 2) + n*(9*n - 26) - 2)/2 - 5:
map(f, [$1..40]); # Robert Israel, Nov 30 2017

Mathematica

Table[3 2^(n + 1) + n ((-1)^(n + 1) + 2^(n + 2) + n (9 n - 26) - 2)/2 - 5, {n, 20}]
LinearRecurrence[{6, -11, 0, 21, -18, -5, 12, -4}, {2, 16, 94, 293,
  742, 1642, 3458, 7087}, 20]
CoefficientList[Series[(2 + 4 x + 20 x^2 - 95 x^3 - 24 x^4 + 113 x^5 + 92 x^6 - 4 x^7)/((-1 + x)^4 (-1 + x + 2 x^2)^2), {x, 0, 20}], x]

Crossrefs

Sequence in context: A207413 A271273 A220882 * A362767 A141243 A163229

Adjacent sequences: A295900 A295901 A295902 * A295904 A295905 A295906

Keyword

nonn

Author

Eric W. Weisstein, Nov 29 2017

Status

approved