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

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, 19, 19, 20, 21, 21, 22, 23, 23, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 31, 31, 32, 33, 33, 34, 35, 35, 36, 37, 37, 38, 39, 39, 40, 41, 41, 42, 43, 43, 44, 45, 45, 46, 47, 47

Offset: 0

Author

Rob Pratt and N. J. A. Sloane, Jul 01 2016

Keywords

• nonn
• easy

Comments

This sequence was mentioned by R. K. Guy in the first comment in A004396.

Examples

			n=3:
OOX
XO
O
n=4:
OOOX
OXO
OO
O
n=5:
OOOOX
OOXO
XOO
OO
O
		

References

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

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, Queens in exile: non-attacking queens on infinite chess boards, Electronic J. Combin., 27:1 (2020), #P1.52.
• Gabriel Nivasch and Eyal Lev, Nonattacking Queens on a Triangle, Mathematics Magazine, Vol. 78, No. 5 (Dec., 2005), pp. 399-403.
• Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).

Crossrefs

Cf. A000170, A004396, A287864.

Programs

Mathematica

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

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

Formula

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

From Colin Barker, Jul 02 2016: (Start)

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

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

a(n) = 2*(3*n + sqrt(3)*sin((2*Pi*n)/3)) / 9. - Colin Barker, Mar 08 2017