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
answer[n_] :=
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?
