# The number of placement of $n$ pieces on the chessboard of $n\times n$, such that the piece $k$ cannot be placed in the $k$-th row nor $k$-th column

Considering the chessboard of $$n\times n$$, we now want to put n pieces $$1,2,\cdots, n$$ on this chessboard, and satisfy that the piece $$k$$ cannot be placed in the $$k$$-th row nor $$k$$-th column, and each grid can only place one piece at most. How many kinds of placement are there?

I calculate the answer with inclusion-exclusion principle

the Mathematica code is:

glist = RecurrenceTable[{g[
i] == (2 n - 1) g[i - 1] + (-2 i + 2) g[i - 2],
g[2] == 4 n^2 - 4 n - 1, g[1] == 2 n - 1}, g, {i, 1, 10}] //
FullSimplify // Expand
n!*Binomial[n^2, n] +
Sum[(-1)^i*Binomial[n, i]*(g /. {g -> glist[[i]]})*
Binomial[(n^2 - i), (n - i)]*(n - i)!, {i, 1, n}]
Table[answer[i] /. {n -> i}, {i, 1, 10}]


$$\{0,1,52,4737,718656,162509785,51209676372,21445634148225,11519808468594976,7721569549966334481\}$$

Someone says this question can also be solved with generating function. $$n ! \cdot\left[x^n\right](1+x)^{n^2} \cdot \exp \left(\frac{-2 n x}{1+x}+\frac{x}{(1+x)^2}\right)$$

the following mma code verified the correctness of the formula.

Flatten@Table[
i!*SeriesCoefficient[(1 + x)^{n^2}*
Exp[-2 n*x/(1 + x) + x/((1 + x)^2)], {x, 0, i}] /. {n -> i}, {i,
1, 10}]


The key word of this approach is probably:

the inclusion-exclusion principle, the Mobius equation/Mobius inversion of partition lattice, Weisner's method.

My question is: what are the detailed steps of this approach?

• "Someone says this question can also be solved with generating function." Who is someone? Where did they say? Jan 17 at 10:25
• I found this question at ZhiHu, a Chinese Q&A site like Quora. Jan 17 at 14:41