每日一题[2549]三维卡特兰

将 $1,2,3,\cdots,9$ 这 $9$ 个数全部填入 $3\times 3$ 的方格内,每个格内填一个数,则使得每行中的数从左至右递增,每列中的数从上至下递减的不同填法共有(       )种.

A.$12$

B.$24$

C.$42$

D.$48$

答案    C.

解析    用 $A,B,C$ 分别记为将数放在第一列、第二列和第三列,问题等价于将 $3$ 个 $A$,$3$ 个 $B$,$3$ 个 $C$ 排成一列,其中在任何一个中间状态已经排好的 $A$ 的数量不小于 $B$ 的数量,且 $B$ 的数量不小于 $C$ 的数量.如 $AABCABBCC$ 即为\[\begin{array}{|c|c|c|}\hline 5&7&9\\ \hline 2&6&8\\ \hline 1&3&4\\ \hline \end{array}\]这可以看作是一个三维的卡特兰数问题,可以通过\[f(x,y,z)=f(x-1,y,z)+f(x,y-1,z)+f(x,y,z-1),\]以及当 $x<y$ 或 $y<z$ 时,$f(x,y,z)=0$,$f(0,0,0)=1$ 来递推计算.当 $z=0$ 时,有\[\begin{array}{c|cccc}\hline y\backslash x&0&1&2&3\\ \hline 0&1&1&1&1\\ \hline 1&0&1&2&3\\ \hline 2&0&0&2&5\\ \hline 3&0&0&0&5\\ \hline \end{array}\]当 $z=1$ 时,有\[\begin{array}{c|cccc}\hline y\backslash x&0&1&2&3\\ \hline 0&0&0&0&0\\ \hline 1&0&1&3&6\\ \hline 2&0&0&5&16\\ \hline 3&0&0&0&21\\ \hline \end{array}\]当 $z=2$ 时,有\[\begin{array}{c|cccc}\hline y\backslash x&0&1&2&3\\ \hline 0&0&0&0&0\\ \hline 1&0&0&0&0\\ \hline 2&0&0&5&21\\ \hline 3&0&0&0&42\\ \hline \end{array}\] 当 $z=3$ 时,有\[\begin{array}{c|cccc}\hline y\backslash x&0&1&2&3\\ \hline 0&0&0&0&0\\ \hline 1&0&0&0&0\\ \hline 2&0&0&0&0\\ \hline 3&0&0&0&42\\ \hline \end{array}\] 因此所求不同的填法共有 $42$ 种.

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

发表评论