每日一题[3221]递推计数

将一些小于 $10$ 的正整数填入如下 $4 \times 4$ 的方格中，使得每行和每列中的数的乘积都等于 $10$，共有_______种不同的填法．

答案    $216$．

解析    问题即将 $4$ 个 $2$ 和 $4$ 个 $5$ 填入 $4\times 4$ 的表格中，使得每行每列均包含一个 $2$ 和一个 $5$，其他位置都填 $1$． 将问题一般化，设需要填写的表格是 $n\times n$ 的，对应的填法有 $a_n$ 种，则 $a_1=0$，$a_2=2$．对于 $n$ 的情形，先填 $2$，有 $n!$ 种方法，然后在第一行中填入 $5$，有 $n-1$ 种方法，考虑与这个 $5$ 同行以及同列的 $2$ 对应的列和行的交叉位置 $P$，如果 $P$ 填入 $5$，则剩下的图形有 $\dfrac{a_{n-2}}{(n-2)!}$ 种填法（去掉两行两列）；如果不填 $5$，则剩下的图形有 $\dfrac{a_{n-1}}{(n-1)!}$ 种填法（去掉一行一列，$P$ 填入 $2$），从而有

$$a_n=n!\cdot (n-1)\cdot \left(\dfrac{a_{n-2}}{(n-2)!}+\dfrac{a_{n-1}}{(n-1)!}\right).$$

计算可得

$$\begin{array}{c|c|c|c|c|c}\hline n&1&2&3&4&5\\ \hline a_n&0&2&12&216&5280 \\ \hline\end{array}$$ 从而所求填法数为 $216$．

备注    递推过程与欧拉错排问题相似，第 $1,2,\cdots,n$ 行中 $2,5$ 的位置（列号）分别为两个 $1,2,\cdots,n$ 的排列，且这两个排列互为错排，因此所求填法数即 $n$ 的错排数的 $n!$ 倍．