每日一题[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$ 种．