丘成桐数学零试第1题及类似一题

答案： 40320．

此类问题一般可以用递推来计算，也可以通过寻找组合意义，用算两次的方法解决．(考虑由1，2，⋯，8组成的八位数个数，要求每个数字均出现)

本题让我想到一道类似的组合数求值问题，但难度更大：

1. 答案为𝐻_(𝑛)．
   若𝜋(𝑛)≠1，则𝑛优于𝜋^(−1)(1)．
   而𝜋(𝑛)=1时，𝑛不优于任何数．
   于是𝐸_(𝑛)=𝐸_(𝑛−1)+(1)/(𝑛)，结合𝐸_(1)=1知𝐸_(𝑛)=𝐻_(𝑛)．

2. 答案为∑_(𝑟=1)^(𝑛)(−1)^(𝑟−1)((𝑛)/(𝑟))(1)/(𝑟)．
   用容斥原理进行计算．
   首先假设每个数均符合题意．
   对于任意二元数组{𝑖,𝑗}，𝑖>𝑗，有(1)/(2)的概率𝜋(𝑖)>𝜋(𝑗)，即𝑖优于𝑗，此时的𝑖不满足题意．
   对于任意三元数组{𝑖,𝑗,𝑘}，其中𝑖为最大数，若𝜋(𝑖)>𝜋(𝑗)，且𝜋(𝑖)>𝜋(𝑘)，此情况已在二元数组的讨论中被计算2次，而其发生的概率为(1)/(3)(对𝜋(𝑖)，𝜋(𝑗)，𝜋(𝑘)排序后，𝜋(𝑖)最大)
   ……
   由容斥原理即得：𝐸_(𝑛)=∑_(𝑟=1)^(𝑛)(−1)^(𝑟−1)((𝑛)/(𝑟))(1)/(𝑟)．\

因此

方法二： 考虑𝑛−1次多项式𝑃(𝑥)，满足对任意𝑘=1,2,⋯,𝑛，都有𝑃(𝑘)=(1)/(𝑘)．由拉格朗日插值公式知，这样的多项式𝑃(𝑥)存在．于是1，2，⋯，𝑛为方程𝑥𝑃(𝑥)−1=0的𝑛个根．即

公式：xP(x)-1=a(x-1)(x-2)\cdots(x-n)

其中𝑎为常数．

等式左侧的常数项为−1，右侧的常数项为𝑎(−1)^(𝑛)𝑛!，于是𝑎(−1)^(𝑛)𝑛!=−1，即

等式右侧的一次项系数为

公式：\begin{align*} &a(-1)^{n-1}\left(\dfrac{n!}{1}+\dfrac{n!}{2}+\cdots+\dfrac{n!}{n}\right)\\ =&\dfrac{1}{1}+\dfrac{1}{2}+\cdots+\dfrac{1}{n} \end{align*}

等式左侧的一次项系数为𝑃(0)．

于是

因此

公式：\begin{align*} &\sum\limits_{r=1}^n(-1)^{r-1}\binom{n}{r}\dfrac{1}{r}\\ =&P(0)-(-1)^n\sum\limits_{r=0}^n(-1)^{n-r}\binom{n}{r}P(r)\\ =&H(n)-(-1)^n\Delta^nP(0)\\ =&H(n) \end{align*}

最后一步是因为𝑃(𝑥)为𝑛−1次多项式，其𝑛阶差分为0．