一道组合数学题

这是2014-2015年北京市25校联合综合能力测试的压轴题：

给定正奇数$n(n\geqslant 5)$，数列$\left\{a_n\right\}:a_1,a_2,\cdots,a_n$是$1,2,\cdots,n$的一个排列，定义 $$E\left(a_1,a_2,\cdots,a_n\right)=\left|a_1-1\right|+\left|a_2-2\right|+\cdots+\left|a_n-n\right|$$ 为数列$\left\{a_n\right\}$的位差和．

（1）当$n=5$时，求数列$\left\{a_n\right\}:1,3,4,2,5$的位差和；

（2）若位差和$E\left(a_1,a_2,\cdots,a_n\right)=4$，求满足条件的数列$\left\{a_n\right\}$的个数；

（3）若位差和$E\left(a_1,a_2,\cdots,a_n\right)=\frac 12\left(n^2-1\right)$，求满足条件的数列$\left\{a_n\right\}$的个数．

（1）4；

（2）“1+1+1+1型”有$\mathrm C_{n-2}^2$个；

“2+2”型有$n-2$个；

“1+1+2”型有$2(n-2)$个；

因此总共有$\mathrm C_{n-2}^2+3(n-2)=\frac 12(n-2)(n+3)$个．

（3）先考虑$n=5$的情形，此时$E=12$，很容易有以下构造：

$$\begin{matrix}1&2&3&4&5\\5&4&3&2&1\end{matrix}$$

此时我们可以发现

$$E=(5-1)+(4-2)+(3-3)+(4-2)+(5-1)=12.$$

也就是说，这是当$n=5$时的最大位差和．这个事实很容易推广到一般情形，设$n=2k-1$，则：

$$\begin{split}E\left(a_1,a_2,\cdots,a_n\right)&=\left|a_1-1\right|+\left|a_2-2\right|+\cdots+\left|a_n-(2k-1)\right|\\&\leqslant \left[k+2\cdot (k+1)+2\cdot (k+2)+\cdots 2\cdot (2k-1)\right]-\left[2\cdot 1+2\cdot 2+\cdots +2\cdot (k-1)+k\right]\\&=2k^2-2k=\frac 12\left(n^2-1\right).\end{split}$$

于是我们需要且只需要保证$1,2,3,\cdots,k$在后$k$个位置或$k,k+1,k+2,\cdots,2k-1$在前$k$个位置即可．为了达到这个目的，可以先将$k$安排在任意一个位置，然后将剩下的位置中的前一半中安排$k+1,k+2,\cdots,2k-1$，后一半中安排$1,2,3,\cdots,k-1$就可以了．也就是说，满足条件的数列$\left\{a_n\right\}$的个数为 $$(2k-1)\cdot (k-1)!\cdots (k-1)!=n\cdot\left(\frac {n-1}2\right)!.$$