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