|
%I #49 Feb 16 2022 23:35:19
%S 0,6,28,76,160,290,476,728,1056,1470,1980,2596,3328,4186,5180,6320,
%T 7616,9078,10716,12540,14560,16786,19228,21896,24800,27950,31356,
%U 35028,38976,43210,47740,52576,57728,63206,69020,75180,81696,88578,95836,103480,111520
%N Number of ways to place 2 queens on an n X n chessboard so that they attack each other.
%C 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.
%C In other words, number of edges in the n X n queen graph. - _Eric W. Weisstein_, Jun 19 2017
%C 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.
%C Starting with "6" = binomial transform of [6, 22, 26, 10, 0, 0, 0, ...]. - _Gary W. Adamson_, Aug 12 2009
%C Also the Harary index of the n X n king graph. - _Eric W. Weisstein_, Jun 20 2017
%H Vincenzo Librandi, <a href="/A144945/b144945.txt">Table of n, a(n) for n = 1..10000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EdgeCount.html">Edge Count</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HararyIndex.html">Harary Index</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KingGraph.html">King Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QueenGraph.html">Queen Graph</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,4,-1).
%F a(n) = (n-1)*n*(5*n-1)/3.
%F From _Bruno Berselli_, Sep 27 2011: (Start)
%F G.f.: 2*x^2*(3+2*x)/(1-x)^4.
%F a(-n) = -A174814(n).
%F a(n) = a(n-1) + 2*A005475(n-1).
%F Sum_{i=1..n} a(i) = (n-1)*n*(n+1)*(5*n+2)/12. (End)
%F 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
%F a(n) = Sum_{i=1..n-1} i*(5*i+1), with a(0)=0, a(1)=6. - _Bruno Berselli_, Feb 10 2014
%F E.g.f.: x^2*(9+5*x)*exp(x)/3. - _Robert Israel_, Nov 02 2014
%e 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.
%e 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.
%p A144945:=n->(n-1)*n*(5*n-1)/3: seq(A144945(n), n=1..50); # _Wesley Ivan Hurt_, Nov 02 2014
%t Table[n (5 n - 1) (n - 1)/3, {n, 50}] (* _Harvey P. Dale_, Oct 15 2011 *)
%t LinearRecurrence[{4, -6, 4, -1}, {0, 6, 28, 76}, 50] (* _Harvey P. Dale_, Oct 15 2011 *)
%t CoefficientList[Series[2 x (3 + 2 x)/(-1 + x)^4, {x, 0, 20}], x] (* _Eric W. Weisstein_, Dec 07 2017 *)
%o (Magma) [(n-1)*n*(5*n-1)/3: n in [1..40]]; // _Vincenzo Librandi_, Sep 28 2011
%o (PARI) a(n) = (n-1)*n*(5*n-1)/3 \\ _Charles R Greathouse IV_, Jun 19 2017
%o (PARI) first(n) = Vec(2*x^2*(3+2*x)/(1-x)^4 + O(x^(n+1)), -n) \\ _Iain Fox_, Dec 07 2017
%Y Cf. A000330, A006002.
%K nonn,easy,nice
%O 1,2
%A _Paolo Bonzini_, Sep 26 2008
%E More terms from _Harvey P. Dale_, Oct 15 2011
|
