IBM Ponder This #071 · 2004 年 3 月

本题由 Yuval Dekel 根据 Vladeta Jovovic 和 Vladimir Baltic 的工作提出。

整数序列若非递减或非递增，便称为“弱单调”。例如由 {0,1} 构成的长度为 3 的弱单调序列恰有 000、001、011、100、110、111 六个；010 则不满足。若数组的每行与每列各自弱单调，就称其合法，不同行列可以选择不同的单调方向。

分别给出公式并证明：

1. 元素属于 {0,1} 的合法 M×N 数组有多少个？
2. 元素属于 {0,1,2} 的合法 3×N 数组有多少个？
3. 元素属于 {0,1,2} 的合法 M×N 数组有多少个？
4. 元素属于 {0,1} 的合法 M×N×K 三维数组有多少个？三维情形要求沿三个坐标轴方向的每条线均弱单调。

原题接受任意一问的完整证明，优先使用不含递推或求和、仅含二项式系数等的闭式。

解答

认真尝试后再打开

待补充。