

A144945


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


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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*(n1)/2; number of ways to place two queens on the same diagonal (either SWNE or NESW) = A000330 shifted by one: c(n) = n(n1)*(2*n1)/6; total: a(n) = 2*b(n)+2*c(n) = n*(5*n1)*(n1)/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) = (n1)*n*(5*n1)/3.
From Bruno Berselli, Sep 27 2011: (Start)
G.f.: 2*x^2*(3+2*x)/(1x)^4.
a(n) = A174814(n).
a(n) = a(n1) + 2*A005475(n1).
Sum_{i=1..n} a(i) = (n1)*n*(n+1)*(5*n+2)/12. (End)
a(n) = 4*a(n1)  6*a(n2) + 4*a(n3)  a(n4) 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..n1} 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 SWNE 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 NWSE diagonal, giving a total of 9+9+5+5 = 28.


MAPLE

A144945:=n>(n1)*n*(5*n1)/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) [(n1)*n*(5*n1)/3: n in [1..40]]; // Vincenzo Librandi, Sep 28 2011
(PARI) a(n) = (n1)*n*(5*n1)/3 \\ Charles R Greathouse IV, Jun 19 2017
(PARI) first(n) = Vec(2*x^2*(3+2*x)/(1x)^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



