每日一题[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!$ 倍.

 

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复