On regarde les n^2 couples (i,j).
Chaque élément i de [|1,n|] est max pour 2*i-1 couples, (i,i) et les i-1 couples (i,1), (i,2)... (i,i-1) ainsi que leur symétrique (1,i), (2,i).
La somme fait donc 2*somme des i^2- somme des i
C'est à dire n(n+1)(2n+1)/3-n(n+1)/2