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

2021年9月4日的清华大学丘成桐数学零试第一题如下：(完整试题及解析见：【修订版】丘成桐数学零试完整试题&解析发布！内附猿辅导独家试题评析)

题目：

答案： ．

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

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

题目： 计算：

方法一： 本题答案为调和级数

考虑如下组合问题：

，，，为，，，的任意一个排列，称优于当且仅当，且．求的个数的数学期望，满足不存在使得优于．

1. 答案为．
   若，则优于．
   而时，不优于任何数．
   于是，结合知．

2. 答案为．
   用容斥原理进行计算．
   首先假设每个数均符合题意．
   对于任意二元数组，，有的概率，即优于，此时的不满足题意．
   对于任意三元数组，其中为最大数，若，且，此情况已在二元数组的讨论中被计算次，而其发生的概率为(对，，排序后，最大)
   ……
   由容斥原理即得：．\

因此

方法二： 考虑次多项式，满足对任意，都有．由拉格朗日插值公式知，这样的多项式存在．于是，，，为方程的个根．即

其中为常数．

等式左侧的常数项为，右侧的常数项为，于是，即

等式右侧的一次项系数为

等式左侧的一次项系数为．

于是

因此

最后一步是因为为次多项式，其阶差分为．