Convergence behaviour of the KPK endgame for the n*n-board ========================================================== by Ulrich Schimke ================= Contents -------- Summary 1.The draw criterion 2.Dividing the board into sectors 3.Sector A 4.Sector B 5.Sector C 6.Sector D 7.The overall result Appendix.Proof of the sum formulas Summary ------- Let two kings and a white pawn be randomly set on an n*n-chess board. It is proved that the probability that white wins converges to 149/192 for n infinite. The necessary formulas are proved at the end of the document to seperate them from the main idea. The idea is to count the number of possible king positions for a given pawn position which guarantees black a draw. The criterion for a draw will be simplified that makes it accessible for calculation. The justification lies in the fact that the probability for the positions where the simplification is not correct converges to 0 for n infinite. For the calculation the board will be divided into 4 sectors. The number of the positions added over all pawn positions can be described by a*n^6 + O(n^5) which leads to the needed limit. 1.The draw criteron ------------------- Consider a position where the black king is in the square of the white pawn and the distance from the black king to the pawn is less than the distance from the white king to the pawn. The "square of the pawn" hereby is the square on the (extended) chessboard whose diagonal runs from the square of the pawn to the promotian rank on the side of the black king. The "square" can be a rectangle on the real board, since the diagonal may reach the left or right border of the board before it reaches the last row. Since the position of the black king is variable in our view it is always a rectangle because we have to consider both diagonals. Graphicly spoken the king stands in the square of the pawn if he can win the running game against the white pawn alone. Distance means distance in king moves. If the King is on the square (c,d) and the pawn is on (a,b) then the distance between them is max(|a-c|,|b-d|). Proposition: The probability that the black king is in the square of the pawn and the distance from the black king to the pawn is less than the distance from the white king to the pawn converges to the same value as the probability that black reaches a draw. This proposition makes the wanted probability easier for calculation. To show it, first note that illegal positions (king adjacent to king, black in check and white to move, pawn on first or last row) have a probability that converges to 0 for n infinite. Now a closer look to the exceptions: For the rook pawn the chances for black to get a tie are much better. But the probability that a pawn is on this line converges to 0. Another exception are positions like these: white King on d2, pawn on c3, black king on d8. Although the distance from the white king to the pawn is 1 and from the black king to the pawn is 5, black has a draw even if it is white to move. But since for every k>0 the probability that the difference between the white king and black king pawn distances differ less than k converges to 0, we can ignore all positions where the difference is less than 6. And if the white king has a closer distance by 6 to the pawn than the black king he can always gain the opposition in front of the pawn and win. So the proposition is shown. For completion note that the side to move doesn't matter, because the probability of these positions where the side to move matters converges to 0 either. 2.Dividing the board into sectors --------------------------------- +-----------+ | AAAAAAAAA | We divide the chess board into 4 sectors. We have to |B AAAAAAA B| distinguish the cases because of the changing shape |BB AAAAA BB| of the square of the pawn depending on the sector |BBB AAA BBB| it is in. We will count the possible combinations |BBBB A BBBB| in which black draws the game in each of the sectors. | | |CCCC D CCCC| A is the triangle limited by the two diagonals |CCC DDD CCC| next to the promotion rank, B is the remaining |CC DDDDD CC| part in the black half. C is the mirror of B |C DDDDDDD C| reflected by the middle line, D is the mirror | DDDDDDDDD | of A. See the left 11*11-board for an example. +-----------+ It is not nessecary to think about the diagonals and the middle line itself. The probability that the pawn is on one of these squares converges to 0. We can add them to a arbitrary sector, ignore them or count them twice. Also we don't have to worry about odd or even board size. 3.Sector A ---------- b= 11 12345678901 +-----------+ 1! AAAAA ! We will use the coordinates a and b for the squares. 2! AAAA ! a denotes the rows, beginning with the promotion rank. 3! AAA ! 4! AA ! At first we will only consider the left part of a=5! A ! sector A: the squares with a<b and b<= n/2. 6! ! 7! ! Assume that the white pawn stands on one of 8! ! these squares. 9! ! 10! ! 11! ! +-----------+ b= 11 12345678901 +-----------+ 1! rrrrrrr ! The asteriks marks the position of the white pawn. 2! rqqqqqr ! If the black king is on a square with a lowercase 3! rqpppqr ! letter he is in the square of the pawn. These positions 4! rqp*pqr ! can be classified as "stripes" with equal distance a=5! RQPPPQR ! to the pawn. The 5 "p"-squares have distance 1, the 6! RQQQQQR ! 9 "q"-squares have distance 2 an so on. 7! RRRRRRR ! We indicate these stripes by m. m runs from 1 to a-1. 8! ! There are 4m+1 squares in every stripe. 9! ! 10! ! The white king has a larger distance to the 11! ! pawn if he is not in the square built by the lowercase +-----------+ and corresponding uppercase letters. The number of these possible fields for the white king is n^2-(2*m+1)*(2*m+1), where m is the number of the stripe. Hence the number of possible combinations of white and black king positions where black makes a draw for a given pawn position (a,b) in the left part of sector A is: a-1 --- \ / (4m+1) * (n^2 - (2m+1)*(2m+1)) --- m=1 To count all possibilities for all combinations where the white pawn is in sector A we have to add these values for a<b and b<=n/2 and double the result for the right symmetric part of sector A. Again we don't have to care that we count the squares on the line b = n/2 twice. So the total number of positions which black can tie with the pawn in sector A is : n/2 b-1 a-1 --- --- --- \ \ \ 2 * / / / (4m+1)*(n^2-(2m+1)*(2m+1)) --- --- --- b=1 a=1 m=1 That is 1/60 * n^6 + O(n^5) by (L1 with exchanged a and b) 4.Sector B ---------- b= 11 12345678901 +-----------+ 1! ! Again a denotes the row, beginning 2!B ! with the promotion rank. 3!BB ! 4!BBB ! At first we will only look at the left part of a=5!BBBB ! sector B: the squares with a>b and b<= n/2. 6!BBBBB ! 7! ! Assume that the white pawn stands on one of 8! ! these squares. 9! ! 10! ! 11! ! +-----------+ b= 11 12345678901 +-----------+ 1!sssssss ! The asteriks marks the position of the white pawn. 2!rrrrrrs ! Again if the black king is on a square with a 3!qqqqqrs ! lowercase letter he is in the square of the pawn. 4!qpppqrs ! The first stripes p and q are the same as in sector A: a=5!qp*pqrs ! 4m+1 squares, each of them having n^2-(2*m+1)*(2*m+1) 6!QPPPQRS ! positions of the white king guaranteeing the tie for black. 7!QQQQQRS ! 8!RRRRRRS ! But for r and s the situation changes: 9!SSSSSSS ! The square of the pawn reaches the edge. 10! ! These stripes (m running 11! ! from b to a-1) contain only 2*m+b squares with +-----------+ n^2-(2*m+1)*(m+b) assigned positions of the white king outside the rectangle built by the uppercase letters. Hence the number of possible combinations of white and black king positions where black makes a draw for a given pawn position (a,b) in the left part of sector B is: b-1 a-1 --- --- \ \ / (4m+1)*(n^2-(2m+1)*(2m+1)) + / (2m+b) * (n^2 - (m+b)*(2m+1)) --- --- m=1 m=b To count all possibilities for all combinations with the white pawn in sector B we have to add these values for a>b and a<=n/2 and double the result for the right symmetric part of sector B. Again we don't have to care that we count the squares on the line b = n/2 twice. So the total number of positions which black can tie with the pawn in sector B is: n/2 a-1 b-1 --- --- --- \ \ \ 2 * / / / (4m+1)*(n^2-(2m+1)*(2m+1)) + --- --- --- a=1 b=1 m=1 n/2 a-1 a-1 --- --- --- \ \ \ 2 * / / / (2m+b)*(n^2-(m+b)*(2m+1)) --- --- --- a=1 b=1 m=b That is 1/60*n^6 + 26/1440*n^6 + O(n^5) = 5/144*n^6 + O(n^5) by (L1) and (L2). 5.Sector C ---------- b= 11 12345678901 +-----------+ 11! ! Now a denotes the rows beginning 10! ! with whites baseline. 9! ! 8! ! At first we will only look at the left part of a=7! ! sector C: the squares with a>b and b<= n/2. 6!CCCCC ! 5!CCCC ! Assume that the white pawn stands on one of 4!CCC ! these squares. 3!CC ! 2!C ! 1! ! +-----------+ b= 11 12345678901 +-----------+ The asteriks marks the position of the white pawn. 11!vvvvvvvvvv ! Again if the black king is on a square with a 10!uuuuuuuuuv ! lowercase letter he is in the square of the pawn. 9!ttttttttuv ! The first stripes p and q are the same as in sector 8!ssssssstuv ! A and B: 4m+1 squares, each of them having a=7!rrrrrrstuv ! n^2-(2*m+1)*(2*m+1) positions of the white king 6!qqqqqrstuv ! guaranteeing the tie, m running from 1 to b-1. 5!qpppqrstuv ! 4!qp*pqrstuv ! The values for the next stipes 3!QPPPQRSTUV ! are the same as in sector B: They contain 2!QQQQQRSTUV ! 2*m+b squares with, each with 1!RRRRRRSTUV ! n^2-(2*m+1)*(m+b) tie positions of the white king +-----------+ m running from b to a-1 (in the example only s). Then beginning with m=a the situation changes: The rectangle with lower- and uppercase letters reaches the white baseline. So the formula for the positions of the white king (outside the Ēletter'-area) changes to n^2-(m+a)*(m+b) for m=a to n-a. Hence the number of possible combinations of white and black king positions where black makes a draw for a given pawn position (a,b) in the left part of sector C is: b-1 a-1 --- --- \ \ / (4m+1)*(n^2-(2m+1)*(2m+1)) + / (2m+b) * (n^2 - (m+b)*(2m+1)) + --- --- m=1 m=b n-a --- \ / (2m+b)*(n^2 - (m+b)*(m+a)) --- m=a To count all possibilities for all combinations where the white pawn is in sector C we must again add these values for a>b and a<=n/2 and double the result for the right symmetric part of sector C. So the total number of positions which black can tie with the pawn in sector C is: n/2 a-1 b-1 --- --- --- \ \ \ 2 * / / / (4m+1)*(n^2-(2m+1)*(2m+1)) + --- --- --- a=1 b=1 m=1 n/2 a-1 a-1 --- --- --- \ \ \ 2 * / / / (2m+b)*(n^2-(m+b)*(2m+1)) + --- --- --- a=1 b=1 m=b n/2 a-1 n-a --- --- --- \ \ \ 2 * / / / (2m+b)*(n^2-(m+b)*(m+a)) --- --- --- a=1 b=1 m=a That is 1/60*n^6 + 26/1440*n^6 + 94/2304*n^6 + O(n^5) = 29/384*n^6 + O(n^5) by (L1), (L2) and (L3). 6.Sector D ---------- 12345678901 +-----------+ 11! ! Again a denotes the rows beginning 10! ! with whites baseline. 9! ! 8! ! At first we will only look at the left part of a=7! ! sector D: the squares with b>a and b<=n/2. 6! ! 5! D ! Assume that the white pawn stands on one of 4! DD ! these squares. 3! DDD ! 2! DDDD ! 1! DDDDD ! +-----------+ b= 11 12345678901 +-----------+ The asteriks marks the position of the white pawn. 11!wwwwwwwwwww! Again if the black king is on a square with a 10!vvvvvvvvvvv! lowercase letter he is in the square of the pawn. 9!uuuuuuuuuuv! The first stripes p and q are the same as in sector 8!tttttttttuv! A, B and C: 4m+1 squares, each of them having a=7!sssssssstuv! n^2-(2*m+1)*(2*m+1) tie positions for the white king 6!rrrrrrrstuv! m from 1 to a-1. 5!rqqqqqrstuv! 4!rqpppqrstuv! Differing to C the rectangle with the lower- and 3!rqp*pqrstuv! uppercase letters reaches the baseline before 2!RQPPPQRSTUV! it reaches the left edge. In this area (m from a to 1!RQQQQQRSTUV! b-1) we still have 4m+1 squares for the black king +-----------+ but n^2-(2*m+1)*(m+a) tie positions for the white king. (in the example only r) Then for m = b the square of the pawn reaches the left edge. We have 2*m+b positions for the black king and n^2-(m+a)*(m+b) belonging positions of the white king, m from b to n-b (in the example s, t, u, v) For m = n-b+1 the square of the pawn reaches the right edge, too. Here we have only n squares in the stripe (see the w squares in the example) and n*(n-a-m) positions of the white king giving black the tie. m runs from n-b+1 to n-a. Hence the number of possible combinations of white and black king positions where black makes a draw for a given pawn position (a,b) in the left part of sector D is: a-1 b-1 --- --- \ \ / (4m+1)*(n^2-(2m+1)*(2m+1)) + / (4m+1)*(n^2-(m+a)*(2m+1)) + --- --- m=1 m=a n-b n-a --- --- \ \ / (2m+b)*(n^2 - (m+b)*(m+a)) + / n*(n*(n-a-m)) --- --- m=b m=n-b+1 To count all possibilities for all combinations where the white pawn is in sector D we must again add these values for b>a and b<=n/2 and double the result for the right symmetric part of sector D. So the total number of positions which black can tie with the pawn in sector D is: n/2 b-1 a-1 --- --- --- \ \ \ 2 * / / / (4m+1)*(n^2-(2m+1)*(2m+1)) + --- --- --- b=1 a=1 m=1 n/2 b-1 b-1 --- --- --- \ \ \ 2 * / / / ((4m+1)*(n^2-(m+a)*(2m+1)) + --- --- --- b=1 a=1 m=a n/2 b-1 n-b --- --- --- \ \ \ 2 * / / / (2m+b)*(n^2-(m+b)*(m+a)) + --- --- --- b=1 a=1 m=b n/2 b-1 n-a --- --- --- \ \ \ 2 * / / / n*(n*(n-a-m)) --- --- --- b=1 a=1 m=n-b+1 That is 1/60*n^6 + 7/240*n^6 + 53/1152*n^6 + 1/192*n^6 + O(n^5) = 559/5760 * n^6 + O(n^5) by (L1), (L4), (L5) and (L6). 7.The overall result -------------------- Adding the results for sector A, B, C and D we obtain the number of positions with a tie: (1/60 + 559/5760 + 5/144 + 29/384) * n^6 + O(n^5) = 43/192 * n^6 + O(n^5). Since the probabilty of a concrete position of the pieces 1/n^6, the probability for a tie is 43/192 + O(n^5)/n^6 which converges to 43/192. The probability that white wins converges correspondingly to 149/192. Appendix.Proof of the sum formulas ---------------------------------- The calculation often requires the summation of the first integers, squares or cubes. But in all cases only the coefficient of the highest degree of the resulting polynomial must be known. Here are all necessary formulas: n n --- --- \ \ / k = (n^2)/2 + O(n) / k^2 = (n^3)/3 + O(n^2) --- --- k=1 k=1 n --- \ / k^3 = (n^4)/4 + O(n^3) --- k=1 n n --- --- \ \ / k^4 = (n^5)/5 + O(n^4) / k^5 = (n^6)/6 + O(n^5) --- --- k=1 k=1 Another expression that will be used is pk(a,b,c,..) which denotes a polynomial of a, b, c, .. with max degree k. The purpose is the same as for the Big-O notation: Just to collect the terms with lower degree which doesn't matter for the convergence. They will be used in formulas like these: (b-a+1)^3 = b^3 - 3*a*b^2 + 3*a^2*b - a^3 + p2(a,b) and in generalizations of the above sum formulas: n-a --- \ / 2*k^3 = 2/4*(n-a)^4 + p3(n,a) --- k=1 An example how these terms continue: n-b --- \ / p3(n,a,b) = p4(n,b) --- a=1 At last these terms become p5(n) which is of course O(n^5). These equalities are wildly used in the lower calculations. LEMMA ----- (L1) n/2 a-1 b-1 --- --- --- \ \ \ / / / (4m+1)*(n^2-(2m+1)*(2m+1)) = 1/120*n^6 + O(n^5) --- --- --- a=1 b=1 m=1 Proof: n/2 a-1 b-1 --- --- --- \ \ \ / / / (4m+1)*(n^2-(2m+1)*(2m+1)) = --- --- --- a=1 b=1 m=1 n/2 a-1 b-1 --- --- --- \ \ \ / / / [4m*n^2 - 16m^3 + p2(m,n)] = --- --- --- a=1 b=1 m=1 n/2 a-1 --- --- \ \ / / [2*(b-1)^2*n^2 - 4*(b-1)^4 + p3(b,n)] = --- --- a=1 b=1 n/2 a-1 --- --- \ \ / / [2b^2*n^2 - 4b^4 + p3(b,n)] = --- --- a=1 b=1 n/2 --- \ / [2/3*a^3*n^2 - 4/5*a^5 + p4(a,n)] = --- a=1 2/(12*16)*n^6 - 4/(30*64)*n^6 + p5(n) = 1/120*n^6 + O(n^5) (L2) n/2 a-1 a-1 --- --- --- \ \ \ / / / (2m+b)*(n^2-(m+b)*(2m+1)) = 13/1440*n^6 + O(n^5) --- --- --- a=1 b=1 m=b Proof: n/2 a-1 a-1 --- --- --- \ \ \ / / / (2m+b)*(n^2-(m+b)*(2m+1)) = --- --- --- a=1 b=1 m=b n/2 a-1 a-1 --- --- --- \ \ \ / / / [-4m^3 - 6m^2*b + 2m*n^2 - 2m*b^2 + b*n^2 + p2(m,n,b)] = --- --- --- a=1 b=1 m=b n/2 a-1 a-b --- --- --- \ \ \ / / / [-4(m+b-1)^3 - 6(m+b-1)^2*b + 2(m+b-1)*n^2 - --- --- --- a=1 b=1 m=1 2(m+b-1)*b^2 + b*n^2 + p2(m,n,b)] = n/2 a-1 a-b --- --- --- \ \ \ / / / [-4*m^3 - 18*m^2*b - 26*m*b^2 + 2m*n^2 + --- --- --- a=1 b=1 m=1 3b*n^2 -12b^3 + p2(m,n,b)] = n/2 a-1 --- --- \ \ / / [-(a-b)^4 - 6*(a-b)^3*b - 13*(a-b)^2*b^2 + (a-b)^2*n^2 + --- --- a=1 b=1 3*(a-b)*b*n^2 - 12*(a-b)*b^3 + p3(a,b,n)] = n/2 a-1 --- --- \ \ / / [4b^4 - a^2*b^2 - 2b^2*n^2 - 2b*a^3 + a*b*n^2 + --- --- a=1 b=1 a^2*n^2 - a^4 + p3(a,b,n)] = n/2 --- \ / [4/5*a^5 - 1/3*a^5 - 2/3a^3*n^2 - --- a=1 a^5 + 1/2a^3n^2 + a^3*n^2 - a^5 + p4(a,n)] = n/2 --- \ / [-23/15*a^5 + 5/6*a^3*n^2 + p4(a,n)] = --- a=1 -23/(90*64)*n^6 + 5/(24*16)*n^6 + p5(n) = 13/1440*n^6 + O(n^5) (L3) n/2 a-1 n-a --- --- --- \ \ \ / / / (2m+b)*(n^2-(m+b)*(m+a)) = 47/2304*n^6 + O(n^5) --- --- --- a=1 b=1 m=a Proof: n/2 a-1 n-a --- --- --- \ \ \ / / / (2m+b)*(n^2-(m+b)*(m+a)) = --- --- --- a=1 b=1 m=a n/2 a-1 n-a --- --- --- \ \ \ / / / [2m*n^2 - 2m^3 - 2m^2*b - 2m^2*a - 2m*a*b + --- --- --- a=1 b=1 m=a b*n^2 - b*m^2 - m*b^2 - m*a*b - a*b^2)] = n/2 a-1 n-a --- --- --- \ \ \ / / / [-2m^3 - 3m^2*b - 2m^2*a + 2m*n^2 - --- --- --- a=1 b=1 m=a m*b^2 - 3m*a*b + b*n^2 - a*b^2] = n/2 a-1 n-2a+1 --- --- --- \ \ \ / / / [-2(m+a-1)^3 - 3(m+a-1)^2*b - 2(m+a-1)^2*a + --- --- --- a=1 b=1 m=1 2(m+a-1)*n^2 - (m+a-1)*b^2 - 3(m+a-1)*a*b + b*n^2 - a*b^2]= n/2 a-1 n-2a+1 --- --- --- \ \ \ / / / [-2*m^3 - 8m^2*a - 3*m^2*b - 10m*a^2 - m*b^2 - 9m*a*b + --- --- --- a=1 b=1 m=1 2m*n^2 - 2a*b^2 -6a^2*b + b*n^2 + 2a*n^2 - 4a^3 + p2(a,m)]= n/2 a-1 --- --- \ \ / / [-1/2*(n-2a+1)^4 - 8/3*(n-2a+1)^3*a - (n-2a+1)^3*b - --- --- a=1 b=1 5(n-2a+1)^2*a^2 - 1/2(n-2a+1)^2*b^2 - 9/2(n-2a+1)^2*a*b + (n-2a+1)^2*n^2 - 2*(n-2a^1)*a*b^2 - 6*(n-2a^1)*a^2*b + (n-2a^1)*b*n^2 + 2*(n-2a^1)*a*n^2 - 4*(n-2a^1)*a^3 + p3(n,a,b)] = n/2 a-1 --- --- \ \ / / [-1/2*b^2*n^2 + 2b^2*a^2 - 1/2b*a*n^2 + 2b*a^3 + 4/3*a^4 - --- --- a=1 b=1 a^2*n^2 - 2/3*a*n^3 + 1/2*n^4 + p3(n,a,b)] = n/2 --- \ / [-1/6*a^3*n^2 + 2/3*a^5 - 1/4*a^3*n^2 + a^5 + 4/3*a^5 - a^3*n^2 - --- a=1 2/3*a^2*n^3 + 1/2*a*n^4 + p4(a,n)] = n/2 --- \ / [3a^5 - 17/12*a^3*n^2 - 2/3*a^2*n^3 + 1/2*a*n^4 + p4(a,n)] = --- a=1 3/(6*64)*n^6 - 17/(48*16)*n^6 - 2/(9*8)*n^6 + 1/(4*4)*n^6 + p5(n) = 47/2304*n^6 + O(n^5) (L4) n/2 b-1 b-1 --- --- --- \ \ \ / / / (4m+1)*(n^2-(2m+1)*(m+a)) = 7/480*n^6 + O(n^5) --- --- --- b=1 a=1 m=a Proof: n/2 b-1 b-1 --- --- --- \ \ \ / / / (4m+1)*(n^2-(2m+1)*(m+a)) = --- --- --- b=1 a=1 m=a n/2 b-1 b-1 --- --- --- \ \ \ / / / [4m*n^2 - 8*m^3 - 8m^2*a + p2(a,m,n)] = --- --- --- b=1 a=1 m=a n/2 b-1 b-a --- --- --- \ \ \ / / / [4(m+a-1)*n^2 - 8*(m+a-1)^3 - 8(m+a-1)^2*a + p2(a,m,n)] = --- --- --- b=1 a=1 m=1 n/2 b-1 b-a --- --- --- \ \ \ / / / [-8m^3 - 32m^2*a - 40m*a^2 + 4m*n^2 + 4a*n^2 - --- --- --- b=1 a=1 m=1 16a^3 + p2(a,m,n)] = n/2 b-1 --- --- \ \ / / [-2(b-a)^4 - 32/3*(b-a)^3*a - 20*(b-a)^2*a^2 + --- --- b=1 a=1 2*(b-a)^2*n^2 + (b-a)*4a*n^2 - (b-a)*16a^3 + p3(a,b,n)] = n/2 b-1 --- --- \ \ / / [14/3*a^4 - 2a^2*n^2 - 8/3*a*b^3 - 2b^4 + 2b^2*n^2 + p3(a,b,n)]= --- --- b=1 a=1 n/2 --- \ / [14/15*b^5 - 2/3*b^3*n^2 - 4/3*b^5 - 2b^5 + 2b^3*n^2 + p4(b,n)] = --- b=1 n/2 --- \ / [-12/5*b^5 + 4/3*b^3*n^2 + p4(b,n)] = --- b=1 -12/(30*64)*n^6 + 4/(12*16)*n^6 + p5(b) = 7/480*n^6 + O(n^5) (L5) n/2 b-1 n-b --- --- --- \ \ \ / / / (2m+b)*(n^2-(m+b)*(m+a)) = 53/2304*n^6 + O(n^5) --- --- --- b=1 a=1 m=b Proof: n/2 b-1 n-b --- --- --- \ \ \ / / / (2m+b)*(n^2-(m+b)*(m+a)) = --- --- --- b=1 a=1 m=b n/2 b-1 n-b --- --- --- \ \ \ / / / [-2*m^3 - 3b*m^2 - 2a*m^2 + 2m*n^2 - 3a*b*m + --- --- --- b=1 a=1 m=b b*n^2 - a*b^2 - b^2*n] = n/2 b-1 n-2b+1 --- --- --- \ \ \ / / / [-2*(m+b-1)^3 - 3b*(m+b-1)^2 - 2a*(m+b-1)^2 + --- --- --- b=1 a=1 m=1 2*(m+b-1)*n^2 - 3a*b*(m+b-1) + b*n^2 - a*b^2 - b^2*n] = n/2 b-1 n-2b+1 --- --- --- \ \ \ / / / [-2*m^3 - 9m^2*b - 2m^2*a - 13m*b^2 - 7m*b*a + --- --- --- b=1 a=1 m=1 2m*n^2 - 6b^3 - 6b^2*a + 3b*n^2 + p2(a,b,m,n)] = n/2 b-1 --- --- \ \ / / [-1/2*(n-2b+1)^4 - 3(n-2b+1)^3*b - 2/3*(n-2b+1)^3*a - --- --- b=1 a=1 13/2*(n-2b+1)^2*b^2 - 7/2*(n-2b+1)^2*b*a + (n-2b+1)^2*n^2 - 6*(n-2b+1)*b^3 - 6*(n-2b+1)*b^2*a + 3*(n-2b+1)*b*n^2 + p3(a,b,n)]= n/2 b-1 --- --- \ \ / / [10/3*a*b^3 + 1/2*a*b*n^2 - 2/3*a*n^3 + 2b^4 - 5/2*b^2*n^2 + --- --- b=1 a=1 1/2*n^4 + p3(a,b,n)] = n/2 --- \ / [5/3*b^5 + 1/4*b^3*n^2 - 1/3*b^2*n^3 + 2b^5 - 5/2*b^3*n^2 + --- b=1 1/2*b*n^4 + p4(b,n)] = n/2 --- \ / [11/3*b^5 - 9/4*b^3*n^2 - 1/3*b^2*n^3 + 1/2*b*n^4 + p4(b,n)] = --- b=1 11/(18*64)*n^6 - 9/(16*16)*n^6 - 1/(9*8)*n^6 + 1/(4*4)*n^6 + p5(n) = 53/2304*n^6 + O(n^5) (L6) n/2 b-1 n-a --- --- --- \ \ \ / / / n*(n*(n-a-m)) = 1/384*n^6 + O(n^5) --- --- --- b=1 a=1 m=n-b+1 Proof: n/2 b-1 n-a n/2 b n-a --- --- --- --- --- --- \ \ \ \ \ \ / / / n*(n*(n-a-m)) = / / / [n^3 - a*n^2 - m*n^2] = --- --- --- --- --- --- b=1 a=1 m=n-b+1 b=1 a=1 m=n-b+1 n/2 b-1 b-a --- --- --- \ \ \ / / / [n^3 - a*n^2 - (m+n-b)*n^2] = --- --- --- b=1 a=1 m=1 n/2 b-1 b-a --- --- --- \ \ \ / / / [-m*n^2 - a*n^2 + b*n^2] = --- --- --- b=1 a=1 m=1 n/2 b-1 --- --- \ \ / / [-1/2*(b-a)^2*n^2 - a*(b-a)*n^2 + b*(b-a)*n^2 + p3(a,b,n)] = --- --- b=1 a=1 n/2 b-1 --- --- \ \ / / [1/2*a^2*n^2 - a*b*n^2 + 1/2*b^2*n^2 + p3(a,b,n)] = --- --- b=1 a=1 n/2 --- \ / [1/6*b^3*n^2 - 1/2*b^3*n^2 + 1/2*b^3*n^2 + p4(b,n)] = --- b=1 n/2 --- \ / [1/6*b^3*n^2 + p4(b,n) = 1/(24*64)*n^6 + p5(n)] = --- b=1 1/384*n^6 + O(n^5)