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

Author

Paolo Bonzini, Sep 26 2008

Keywords

• nonn
• easy
• nice

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

Examples

			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.
		

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

Crossrefs

Cf. A000330, A006002.

Programs

Magma

[(n-1)*n*(5*n-1)/3: n in [1..40]]; // Vincenzo Librandi, Sep 28 2011

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

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

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

Extensions

More terms from Harvey P. Dale, Oct 15 2011