login
Maximal number of non-attacking queens on a right triangular board with n cells on each side.
9

%I #32 Mar 07 2020 13:50:20

%S 0,1,1,2,2,3,4,5,5,6,7,7,8,9,9,10,11,11,12,13,13,14,15,15,16,17,17,18,

%T 19,19,20,21,21,22,23,23,24,25,25,26,27,27,28,29,29,30,31,31,32,33,33,

%U 34,35,35,36,37,37,38,39,39,40,41,41,42,43,43,44,45,45,46,47,47

%N Maximal number of non-attacking queens on a right triangular board with n cells on each side.

%C This sequence was mentioned by _R. K. Guy_ in the first comment in A004396.

%D Paul Vanderlind, Richard K. Guy, and Loren C. Larson, The Inquisitive Problem Solver, MAA, 2002. See Problem 252, pages 67, 87, 198 and 276.

%H Colin Barker, <a href="/A274616/b274616.txt">Table of n, a(n) for n = 0..1000</a>

%H F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p52/8039">Queens in exile: non-attacking queens on infinite chess boards</a>, Electronic J. Combin., 27:1 (2020), #P1.52.

%H Gabriel Nivasch and Eyal Lev, <a href="https://www.jstor.org/stable/30044202">Nonattacking Queens on a Triangle</a>, Mathematics Magazine, Vol. 78, No. 5 (Dec., 2005), pp. 399-403.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,-1).

%F Except for n=4, this is round(2n/3).

%F From _Colin Barker_, Jul 02 2016: (Start)

%F a(n) = a(n-1) + a(n-3) - a(n-4) for n>5.

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

%F a(n) = 2*(3*n + sqrt(3)*sin((2*Pi*n)/3)) / 9. - _Colin Barker_, Mar 08 2017

%e n=3:

%e OOX

%e XO

%e O

%e n=4:

%e OOOX

%e OXO

%e OO

%e O

%e n=5:

%e OOOOX

%e OOXO

%e XOO

%e OO

%e O

%t CoefficientList[Series[x*(1 +x^2 -x^3)*(1 +x^4)/((1-x)^2*(1+x+x^2)), {x, 0, 50}], x] (* _G. C. Greubel_, Jul 03 2016 *)

%o (PARI) concat(0, Vec(x*(1+x^2-x^3)*(1+x^4)/((1-x)^2*(1+x+x^2)) + O(x^100))) \\ _Colin Barker_, Jul 02 2016

%Y Cf. A000170, A004396, A287864.

%K nonn,easy

%O 0,4

%A _Rob Pratt_ and _N. J. A. Sloane_, Jul 01 2016