Number of ways to place $4$ kings on an $n \times n$ chessboard

Question

I have an $n \times n$ chessboard and $4$ kings on it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example:

1. In the case where the $4$ kings are non-attacking, there exists a formula that counts the total arrangements with the corresponding restriction:

$\frac{1}{24} \left(n^8-54 n^6+72 n^5+995 n^4-2472 n^3-5094 n^2+21480 n-17112\right)$

2. However, the problem arises when I try to count the arrangements where the $4$ kings form a cluster:

00k0
00k0
00k0
00k0

0000
kk00
0kk0
0000

0000
0kk0
000k
00k0

As you can see, there are some cases where all $4$ kings are adjacent, forming a cluster. Thus, my goal is to calculate in how many arrangements this condition is satisfied.

Also, there are $3$ more cases I would like to count:

3. A cluster of $3$ kings ($3$ adjacent kings) and another king who is non-attacking to any of the cluster pieces:

0k00
00kk
0000
0k00

00k0
0k00
k00k
0000

4. Two clusters formed by $2$ attacking kings: (Note that both clusters must be non-adjacent, since it would form a cluster of size $4$, and would have to be counted in case $2$)

0kk0
0000
0k00
00k0

k000
k000
00kk
0000

5. A 2-king cluster and $2$ clusters of $1$ king. This case can be derived with the solution of all the above cases and the total amount of ways to place $4$ kings on the chessboard, which is $\binom{n^2}{4}$.

Answer 1

Here is a formula for case 2.

Strategy: for each polyplet of size 4 (polyomino connected at edges or corners) (up to rotation and symmetry), count the number of translations of that polyplet in the chessboard (that will depends only on the dimension of the smallest rectangle inscribing the pattern) times the number of non-equivalent rotation/symmetry of the polyplet.

For the polyplet ####, the bounding box is $1\times 4$, so there is $(n-1+1)(n-4+1) = n(n-3)$ placement possible. There are two non-equivalent transformations (under rotation and symmetry) of the polyplet.

We give for 21 remaining 4-polyplets the size of the bounding box and the number of non-equivalent transformation (see here for a list of the polyplets):

##       ##       ##       ###      ###      ###      ## #     ##       # #      #  #
##       # #       ##        #       #          #       #        ##      # #      ##
2x2,1    2x3,8    2x3,4    2x3,8    2x3,4    2x4,8    2x4,8    2x4,4    2x4,4    2x4,4

##       ##       ##       #         #       #        # #      ##       #        #
  #        #       #        ##      # #       ##       #         #       ##       # #
  #       #         #       #        #       #          #         #        #       #
3x3,4    3x3,8    3x3,8    3x3,4    3x3,1    3x3,4    3x3,4    3x4,8    3x4,4    3x4,8

#
 # 
  #
   #
4x4, 2

Recapping, we have:

$1\times 4: 2$ configurations

$2\times 2: 1$ configuration

$2\times 3: 24$ configurations

$2\times 4: 28$ configurations

$3\times 3: 33$ configurations

$3\times 4: 20$ configurations

$4\times 4: 2$ configurations

Thus, we get the total count (assuming $n\geq 4$): $$2n(n-3) + (n-1)(n-1) + 24(n-1)(n-2)+28(n-1)(n-3)+33(n-2)(n-2)+20(n-2)(n-3)+2(n-3)(n-3) = 110 n^2 - 436 n + 403$$ This matches the values you computed.