Generalized Hertzsprung Problem

146 Views Asked by At

The Hertzsprung Problem goes as follows: In how many can we place exactly $n$ non-attacking kings on a $n \times n$ chessboard such that there is exactly $1$ king in each row and column where $n \in \mathbb{N}$.

It turns out that there exists a nice closed for the same (though painful to evaluate for any $n \geqslant 5$) which is

$$n!+\sum_{k=1}^n {(-1)^k}(n-k)!\sum_{i=1}^k 2^{i} \binom{k-1}{i-1}\binom{n-k+1}{i}$$

which can be obtained using simple Principle of inclusion-exclusion and stars and bars argument.

However what if I want to place exactly $2$ kings in each row and column on a $n \times n$ chessboard such that no two kings attack each other on the chessboard? In how many ways can I do this? I tried this for a long time and was able to find a tedious closed form using some restricted permutations but I'm not satisfied with it. Does anyone have any idea if there exists a nice closed form for this? If yes, then which argument did you use?

I call this Generalized Hertzsprung problem: In how many ways can we place non-attacking kings on a $n \times n$ chessboard such that there are exactly $m$ kings in each row and column?

Note that here $m, n \in \mathbb{N}$ such that $m < n$.

Any advice on how to approach the generalized version? Your help would be highly appreciated.

Thanks.