A329451 Maximum number of pieces that can be captured during one move on an n X n board according to the international draughts capture rules.

0, 0, 0, 1, 1, 4, 5, 9, 10, 16, 19, 25, 28, 36, 41, 49, 54, 64, 71, 81, 88, 100, 109, 121, 130, 144, 155, 169, 180, 196, 209, 225, 238, 256, 271, 289, 304, 324, 341, 361, 378, 400, 419, 441, 460, 484, 505, 529, 550, 576, 599, 625, 648, 676, 701, 729, 754, 784

Offset: 0

Author

Stéphane Rézel, Nov 14 2019

Keywords

• nonn

Comments

Captures are made diagonally, forward and backward. Kings have the long-range capturing capability. During the multiple capture, a piece may pass over the same empty square several times, but no opposing piece can be jumped twice. Captured pieces can only be lifted from the board after the end of the multiple capture.

Examples

			It is possible to capture in a single move 19 opposing pieces on a 10 X 10 board, but not one more, so a(10) = 19.
		

Links

• Stéphane Rézel, Table of n, a(n) for n = 0..1000
• Fabien Gigante, Solution to Problem J122 La grande rafle de la dame, Diophante, 2009 (in French).
• Stéphane Rézel, Solution to Problem J128 La méga-rafle de la dame, Diophante, 2020 (in French).
• World Draughts Federation, Official rules for international draughts.
• Index entries for linear recurrences with constant coefficients, signature (2,-1,0,1,-2,1).

Crossrefs

Cf. A000290, A059193, A125202, A000982 (active squares).

Programs

PARI

a(n) = if(n<5, floor(n/3), (n^2 - 2*n + if(n%2, 1, 2*(n%4) - 8))/4)

Formula

a(2*t+1) = t^2 = A000290(t).

a(4*t+6) = 4*t^2 + 10*t + 5 = A125202(t+2).

a(4*t+8) = 4*t^2 + 14*t + 10 = A059193(t+2).

a(0) = a(2) = 0; a(4) = 1.

Recurrence: For t >= 1, a(2*t+1) = a(2*t-1) + 2*t - 1;

For t >= 1, a(4*t+3) = a(4*t+2) + 2*t + 2; a(4*t+2) = a(4*t+1) + 2*t - 1;

For t >= 2, a(4*t+1) = a(4*t) + 2*t + 2; a(4*t) = a(4*t-1) + 2*t - 3.

From Colin Barker, Nov 14 2019: (Start)

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

a(n) = 2*a(n-1) - a(n-2) + a(n-4) - 2*a(n-5) + a(n-6) for n>10.

(End)