A329451 - OEIS

%I #36 Aug 22 2021 00:16:22

%S 0,0,0,1,1,4,5,9,10,16,19,25,28,36,41,49,54,64,71,81,88,100,109,121,

%T 130,144,155,169,180,196,209,225,238,256,271,289,304,324,341,361,378,

%U 400,419,441,460,484,505,529,550,576,599,625,648,676,701,729,754,784

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

%C 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.

%H Stéphane Rézel, <a href="/A329451/b329451.txt">Table of n, a(n) for n = 0..1000</a>

%H Fabien Gigante, <a href="http://www.diophante.fr/images/stories/diophante/rubriques_J/J122FG.pdf">Solution</a> to Problem <a href="http://www.diophante.fr/problemes-par-themes/jeux-de-plateaux/46-j-jeux-de-plateaux/1218-j122-la-grande-rafle-de-la-dame">J122 La grande rafle de la dame</a>, Diophante, 2009 (in French).

%H Stéphane Rézel, <a href="http://www.diophante.fr/images/stories/diophante/janvier_2020-03/J128SR.pdf">Solution</a> to Problem <a href="http://www.diophante.fr/problemes-par-themes/jeux-de-plateaux/4604-j128-la-mega-rafle-de-la-dame">J128 La méga-rafle de la dame</a>, Diophante, 2020 (in French).

%H World Draughts Federation, <a href="http://www.fmjd.org/downloads/FMJD_Annexes_2018.pdf">Official rules for international draughts</a>.

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

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

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

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

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

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

%F 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;

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

%F From _Colin Barker_, Nov 14 2019: (Start)

%F 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)).

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

%F (End)

%e 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.

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

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

%K nonn

%O 0,6

%A _Stéphane Rézel_, Nov 14 2019