A355509 Peaceable coexisting armies of knights: a(n) is the maximum number m such that m white knights and m black knights can coexist on an n X n chessboard without attacking each other.

0, 2, 3, 6, 10, 14, 18, 24, 32, 40, 50, 60, 72, 84, 98, 112, 128, 144, 162, 180, 200, 220, 242, 264, 288, 312, 338, 364, 392, 420, 450, 480, 512, 544, 578, 612, 648, 684, 722, 760, 800, 840, 882, 924, 968, 1012, 1058, 1104, 1152, 1200, 1250, 1300, 1352, 1404

Offset

1,2

Comments

After the first 7 terms, the first differences are terms of A052928: for n >= 8, a(n) - a(n-1) = A052928(n-1).

The increase in differences going from an even n to an odd n, but not from an odd n to an even n, is due to the differing optimal layouts for odd vs. even n values. See example section for a(7) and a(8).

Links

Table of n, a(n) for n=1..54.

Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Formula

For n > 6, a(n) = floor(((n-1)^2)/2).

G.f.: x^2*(2 - x + 2*x^3 - 2*x^4 - x^5 + 2*x^6 + 2*x^7 - 2*x^8)/((1 - x)^3*(1 + x)). - Stefano Spezia, Jul 05 2022

Example

Examples for n=2 to n=6 have been included as they do not follow the general formula.
.
A solution illustrating a(2)=2:
  +-----+
  | B B |
  | W W |
  +-----+
.
A solution illustrating a(3)=3:
  +-------+
  | . . . |
  | B B W |
  | W W B |
  +-------+
.
A solution illustrating a(4)=6:
  +---------+
  | B B . W |
  | W W . B |
  | B B . W |
  | W W . B |
  +---------+
.
A solution illustrating a(5)=10:
  +-----------+
  | W B W B W |
  | W B W B W |
  | . . . . . |
  | B W B W B |
  | B W B W B |
  +-----------+
.
A solution illustrating a(6)=14:
  +-------------+
  | B B W W B B |
  | W W B B W W |
  | B . . . . B |
  | W . . . . W |
  | B B W W B B |
  | W W B B W W |
  +-------------+
.
Examples for n=7 and n=8 are provided, as while both follow the same formula, the layout for even values of n differs from the layout for odd values of n (related to the fact that, for even values of n, the floor function rounds down a non-integer value).
.
A solution illustrating a(7)=18:
  +---------------+
  | B B B B B B B |
  | B B B B B B B |
  | B . B . B . B |
  | . . . . . . . |
  | W . W . W . W |
  | W W W W W W W |
  | W W W W W W W |
  +---------------+
.
A solution illustrating a(8)=24:
  +-----------------+
  | B B B B B B B B |
  | B B B B B B B B |
  | B B B B B B B B |
  | . . . . . . . . |
  | . . . . . . . . |
  | W W W W W W W W |
  | W W W W W W W W |
  | W W W W W W W W |
  +-----------------+

Crossrefs

Cf. A007590, A052928, A176222 (peaceable kings), A250000 (peaceable queens), A002620 (peaceable rooks).

Sequence in context: A120754 A023547 A190690 * A084396 A090035 A337611

Adjacent sequences: A355506 A355507 A355508 * A355510 A355511 A355512

Keyword

nonn,easy

Author

Aaron Khan, Jul 04 2022

Status

approved