题目 设 $k$ 为正整数，称数字 $1\sim3k+1$ 的排列 $x_1,x_2,\cdots,x_{3k+1}$ 为“$N$ 型”的，如果这些数满足：（i）$x_1<x_2<\cdots<x_{k+1}$；（ii）$x_{k+1}>x_{k+2}>\cdots>x_{2k+1}$；（iii）$x_{2k+1}<x_{2k+2}<\cdots<x_{3k+1}$．<br/>记 $d_k$ 为所有“$N$ 型”排列的个数． 问题1 求 $d_1,d_2$ 的值； 答案1 $d_1=5,d_2=71$ 解析1 首先注意到 $x_{k+1}$ 的值只能取$$3k+1,3k,\cdots,2k+1,$$这些数字，因为必须有 $2k$ 个值比它小，而 $x_{2k+1}$ 的值只能取 $1,2,\cdots,k+1$ 这些数字，因为必须有 $2k$ 个值比它大．<br/>记 $x_{k+1}=3k+2-j,x_{2k+1}=i$（其中 $i,j=1,2,\cdots,k+1$）时的“$N$ 型”排列个数为 $d_{k}^{(i,j)}$，则$$d_{k}^{(i,j)}=\mathrm{C}_{3k+1-(i+j)}^{k+1-i}\mathrm{C}_{3k+1-(i+j)-(k+1-i)}^{k+1-j},d_k=\sum\limits_{i,j=1}^{k+1}{d_k^{(i,j)}}.$$化简得$$d_{k}^{(i,j)}=\dfrac{(3k+1-i-j)!}{(k-1)!(k+1-i)!(k+1-j)!}.$$计算可得 $d_1=5,d_2=71$． 备注1 问题2 证明：对任意正整数 $k$，$d_k$ 均为奇数． 答案2 略 解析2 易知 $d_{k}^{(i,j)}=d_k^{(j,i)}$，则$$d_k^{(i,i)}=\dfrac{(3k+1-2i)!}{(k-1)!(k+1-i)!(k+1-i)!},d_k^{(k+1,k+1)}=1.$$当 $k>1$ 时，对于所有 $i=1,2,\cdots,k$，$d_{k}^{(i,i)}$ 是偶数．事实上对于 $x_{2k+1}=i,x_{k+1}=3k+2-i$ 时的任何一个“$N$ 型”排列，此时数字 $1,2,\cdots,i-1$ 只能放在 $x_1,x_2,\cdots,x_{i-1}$ 的位置，数字$$3k+2-(i-1),3k+2-(i-2),\cdots,3k+2-1,$$只能放在$$x_{3k+2-(i-1)},x_{3k+2-(i-2)},\cdots,x_{3k+1},$$其中 $x_i,x_{i+1},\cdots,x_k$ 和 $x_{3k+2-i},x_{3k+2-(i+1)},\cdots,x_{2k+2}$ 的数字可以互换得到一个新的“$N$ 型”排列，于是 $d_k^{(i,i)}$ 是偶数．它的组合意义就是将 $m$ 个白球，$n$ 个红球，$n$ 个蓝球排成一行的排列数．于是任何一个排列，交换红蓝球可对应另一种排列．<br/>于是 $\displaystyle d_k=\sum\limits_{i,j=1}^{k+1}{d_k^{(i,j)}}=\sum\limits_{i,j=1}^{k}{d_k^{(i,j)}}+d_{k}^{(k+1,k+1)}+\sum\limits_{i\ne j,i,j=1}^{k+1}{d_k^{(i,j)}}$ 为奇数． 备注2