A144945 Number of ways to place 2 queens on an n X n chessboard so that they attack each other.

0, 6, 28, 76, 160, 290, 476, 728, 1056, 1470, 1980, 2596, 3328, 4186, 5180, 6320, 7616, 9078, 10716, 12540, 14560, 16786, 19228, 21896, 24800, 27950, 31356, 35028, 38976, 43210, 47740, 52576, 57728, 63206, 69020, 75180, 81696, 88578, 95836, 103480, 111520

Offset

1,2

Comments

a(n) gives the number of edges on a graph with n X n nodes where each node corresponds to a square on an n X n chessboard and there is an edge between two nodes if two queens placed on the corresponding squares attack each other.

In other words, number of edges in the n X n queen graph. - Eric W. Weisstein, Jun 19 2017

Number of ways to place two queens on the same row or column = A006002: b(n) = n*C(n,2) = n^2*(n-1)/2; number of ways to place two queens on the same diagonal (either SW-NE or NE-SW) = A000330 shifted by one: c(n) = n(n-1)*(2*n-1)/6; total: a(n) = 2*b(n)+2*c(n) = n*(5*n-1)*(n-1)/3.

Starting with "6" = binomial transform of [6, 22, 26, 10, 0, 0, 0, ...]. - Gary W. Adamson, Aug 12 2009

Also the Harary index of the n X n king graph. - Eric W. Weisstein, Jun 20 2017

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..10000

Eric Weisstein's World of Mathematics, Edge Count

Eric Weisstein's World of Mathematics, Harary Index

Eric Weisstein's World of Mathematics, King Graph

Eric Weisstein's World of Mathematics, Queen Graph

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Formula

a(n) = (n-1)*n*(5*n-1)/3.

From Bruno Berselli, Sep 27 2011: (Start)

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

a(-n) = -A174814(n).

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

Sum_{i=1..n} a(i) = (n-1)*n*(n+1)*(5*n+2)/12. (End)

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) for n>4; a(1)=0, a(2)=6, a(3)=28, a(4)=76. - Harvey P. Dale, Oct 15 2011

a(n) = Sum_{i=1..n-1} i*(5*i+1), with a(0)=0, a(1)=6. - Bruno Berselli, Feb 10 2014

E.g.f.: x^2*(9+5*x)*exp(x)/3. - Robert Israel, Nov 02 2014

Example

Example: For n=2 there are two rows, two columns and two diagonals. Each of these can be filled with two queens, giving a(2)=6.
For n=3 there are C(3,2) = 3 ways to place two queens on the same rows or column, giving C(3,2)*3 = 9 ways to place two queens on the same rows and 9 ways to place two queens on the same column. There are three nontrivial SW-NE diagonals, two of length two (each giving 1 way to place two attacking queens) and one of length three (giving 3 ways to place two attacking queens): total 3+1+1=5. There are also 5 ways to place two queens on the same NW-SE diagonal, giving a total of 9+9+5+5 = 28.

Maple

A144945:=n->(n-1)*n*(5*n-1)/3: seq(A144945(n), n=1..50); # Wesley Ivan Hurt, Nov 02 2014

Mathematica

Table[n (5 n - 1) (n - 1)/3, {n, 50}] (* Harvey P. Dale, Oct 15 2011 *)
LinearRecurrence[{4, -6, 4, -1}, {0, 6, 28, 76}, 50] (* Harvey P. Dale, Oct 15 2011 *)
CoefficientList[Series[2 x (3 + 2 x)/(-1 + x)^4, {x, 0, 20}], x] (* Eric W. Weisstein, Dec 07 2017 *)

Prog

(Magma) [(n-1)*n*(5*n-1)/3: n in [1..40]]; // Vincenzo Librandi, Sep 28 2011
(PARI) a(n) = (n-1)*n*(5*n-1)/3 \\ Charles R Greathouse IV, Jun 19 2017
(PARI) first(n) = Vec(2*x^2*(3+2*x)/(1-x)^4 + O(x^(n+1)), -n) \\ Iain Fox, Dec 07 2017

Crossrefs

Cf. A000330, A006002.

Sequence in context: A326134 A343512 A326484 * A308585 A202956 A279915

Adjacent sequences: A144942 A144943 A144944 * A144946 A144947 A144948

Keyword

nonn,easy,nice

Author

Paolo Bonzini, Sep 26 2008

Extensions

More terms from Harvey P. Dale, Oct 15 2011

Status

approved