Manhattan Distances of All Arrangements of Pieces
Each pair of cells contributes its Manhattan distance once for every placement of the other k - 2 pieces, so sum the pair distances and multiply by C(mn - 2, k - 2).
Each pair of cells contributes its Manhattan distance once for every placement of the other k - 2 pieces, so sum the pair distances and multiply by C(mn - 2, k - 2).