Problem 1
证明 $$ \begin{align*} \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } \\ \sum_{i=0}^{n} \binom{ k }{ i } D_{n-i} = \sum_{j=0}^{n-k} (-1)^{j}\binom{ n-k }{ j } (n-j)! \end{align*} $$ 证 1
对于第一个式子，我们考虑组合意义。设有 $ A,B $ 两个集合，分别包含 $ n $ 和 $ m $ 个元素，总共 $ n+m $ 个元素。我们希望从集合 $ B $ 中恰好选择 $ k $ 个元素。我们可以通过容斥原理的补集形式求解，定义事件 $ A_{i} $ 为所选的 $ k $ 个元素中至少包含 $ i $ 个来自 $ A $ 的元素，那么我们需要求解的事件集合为 $ U\setminus\bigcup_{i\leq n}A_{i} $，并且 $$ \left| A_{i} \right| = \binom{ n }{ i } \binom{ n+m-i }{ k-i } $$ 因此根据容斥原理，就可以得到 $$ \left| U\setminus \bigcup_{i\leq n}A_{i} \right| = \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } $$
对于第二个式子，同样考虑组合意义。我们可以假定 $ n\geq k $，否则两侧均为零。设有 $ n $ 个元素的排列，分成 $ A $ 和 $ B $ 两部分，分别包含 $ k $ 和 $ n-k $ 个元素。左侧所有枚举所有 $ A $ 中元素的组合固定，剩下的进行错排，可以表示 $ A $ 中元素任意，$ B $ 中元素必须为错排的方案数。我们同样考虑通过容斥原理的补集形式来求解。右侧我们定义事件 $ B_{i} $ 表示 $ B $ 中至少有 $ i $ 个元素不是错排（值等于自己的编号），剩下的数随意，于是 $ \left| B_{i} \right|=\binom{ n-k }{ i }(n-i)! $。同时我们需要求解的事件集合为 $ U\setminus\bigcup_{i=1}^{n-k}B_{i} $，因此根据容斥原理可以得到 $$ \left| U\setminus \bigcup_{j=1}^{n-k}B_{j} \right| = \sum_{i=0}^{n} \binom{ k }{ i } D_{n-i} = \sum_{j=0}^{n-k} (-1)^{j}\binom{ n-k }{ j } (n-j)! $$ 证 2：
这两个式子和二项反演都有一定的类似之处。 $$ g_{n} = \sum_{i=0}^{n} \binom{ n }{ i } f_{i} \implies f_{n} = \sum_{i=0}^{n} (-1)^{n-i}\binom{ n }{ i } g_{i} $$ 我们直接证明二项反演。
将 $ g_{i} $ 的表达式带入要证明的式子，只需证明 $$ \begin{align*} \\ f_{n} & = \sum_{i=0}^{n} (-1)^{n-i}\binom{ n }{ i } \sum_{j=0}^{i} \binom{ i }{ j } f_{j} \\ & = \sum_{i=0}^{n} \sum_{j=0}^{i} (-1)^{n-i}\binom{ n }{ i } \binom{ i }{ j } f_{j} \\ & = \sum_{i=0}^{n} \sum_{j=0}^{i} (-1)^{n-i}\binom{ n }{ j } \binom{ n-j }{ i-j } f_{j} \\ & = \sum_{j=0}^{n}\binom{ n }{ j } f_{j} \sum_{i=j}^{n} (-1)^{n-i}\binom{ n-j }{ i-j } \\ & = \sum_{j=0}^{n} \binom{ n }{ j } f_{j}\cdot \left( \sum_{i=0}^{n-j} (-1)^{n+j-i}\binom{ n-j }{ i } \right) \\ & = \sum_{j=0}^{n} \binom{ n }{ j } f_{j}\cdot[n-j=0] \\ & = f_{n} \end{align*} $$ 这就证明了二项式反演。
因此对于第一个式子 $$ \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \sum_{i=0}^{n} (-1)^{n-i}\binom{ n }{ i } \binom{ m+i }{ k-n+i } $$ 令 $ g_{i}:=\binom{ m+i }{ k-n+i } $，那么上式就是 $ \sum_{i=0}^{n}(-1)^{n-i}\binom{ n }{ i }g_{i} $。
根据组合意义，显然有恒等式 $$ g_{t} = \binom{ m+t }{ k-n+t } = \sum_{i=0}^{t} \binom{ t }{ i } \binom{ m }{ k-n+(t-i) } = \sum_{i=0}^{t} \binom{ t }{ i } \binom{ m }{ k-n+i } $$ 因此我们直接取 $ f_{i}=\binom{ m }{ k-n+i } $ 就可以得到 $$ \sum_{i=0}^{n} \binom{ n }{ i } f_{i} = g_{n} \implies \sum_{i=0}^{n} (-1)^{n-i}\binom{ n }{ i } g_{i} = f_{n} = \binom{ m }{ k } $$ 对于 $$ \sum_{i=0}^{n} \binom{ k }{ i } D_{n-i} = \sum_{j=0}^{n-k} (-1)^{j}\binom{ n-k }{ j } (n-j)! $$ 似乎构造比较复杂，暂时搁置这个思路(
Problem 2
(1)
有多少种方法可以从 $ n $ 个元素的序列中选择 $ k $ 个非连续的元素？
解
设从 $ n $ 个元素中选择 $ k $ 个元素的全体集合为 $ U $，$ A_i $ $ (1 \leq i \leq k-1) $ 表示选择的 $ k $ 个数中第 $ i $ 和 $ i+1 $ 个数同时被选中的事件。我们需要用容斥原理计算 $ \left| U \setminus \bigcup_{i=1}^{k-1} A_i \right| $。
全集：$ |U| = \binom{n}{k} $。
单项和：$ |A_i| = \binom{n-1}{k-1} $，因此 $$ \sum_{i=1}^{k-1} |A_i| = (k-1) \binom{n-1}{k-1} $$
$ m $ 重交集：对于 $ 1 \leq i_1 < i_2 < \cdots < i_m \leq k-1 $，$ \bigcup_{j=1}^{m}A_{i_{j}} $ 等价于从 $ n-m $ 中选取 $ k-m $ 个数，方案数为 $ \binom{ n-m }{ k-m } $。
因此 $$ \sum_{S\in[n]\land \left| S \right| =m} \left( \bigcup_{i\in S}A_{i} \right) = \binom{ k-1 }{ m } \binom{ n-m }{ k-m } $$
由容斥原理 $$ \left| U\setminus \bigcup_{i=1}^{k-1}A_{i} \right| = \sum_{m=0}^{k-1} (-1)^{m}\binom{ k-1 }{ m } \binom{ n-m }{ k-m } $$
通过组合意义，可以得到该式化简后等于 $$ \binom{n-k+1}{k} $$ (2)
有多少种方法可以从 $ n $ 个元素的循环排列中选择 $ k $ 个非连续的元素？
解
设从 $ n $ 个元素的循环排列中选择 $ k $ 个元素的全体集合为 $ U $，$ A_i $ $ (1 \leq i \leq k) $ 表示选择的 $ k $ 个数中第 $ i $ 和第 $ i+1 $（模 $ k $）个数在循环上相邻的事件。我们需要用容斥原理计算 $ \left| U \setminus \bigcup_{i=1}^{k} A_i \right| $。
全集：$ |U| = \binom{n}{k} $。
单项和：对于 $ 1 \leq i \leq k-1 $，$ |A_i| = \binom{n-1}{k-1} $；对于 $ A_k $（首尾相邻），$ |A_k| = \binom{n-2}{k-2} $，因此 $$ \sum_{i=1}^{k} |A_i| = (k-1) \binom{n-1}{k-1} + \binom{n-2}{k-2} $$
$ m $ 重交集：对于 $ 1 \leq i_1 < i_2 < \cdots < i_m \leq k $，若这些事件在循环上形成 $ c $ 个连通段，则 $ \left|\bigcap_{j=1}^{m}A_{i_{j}}\right| = \binom{n-(m+c)}{k-(m+c)} $。
设 $ N_k(m,c) $ 为从 $ k $ 个事件中选 $ m $ 个形成恰好 $ c $ 个连通段的方案数，则 $$ \sum_{1 \leq i_1 < \cdots < i_m \leq k} \left|\bigcap_{j=1}^{m}A_{i_{j}}\right| = \sum_{c=1}^{\min(m,k)} N_k(m,c) \binom{n-(m+c)}{k-(m+c)} $$
其中 $ N_k(m,c) = \frac{k}{m} \binom{m}{c} \binom{m-c}{c} $（将 $ m $ 个事件在 $ k $ 个位置的循环上分成 $ c $ 个连通段）。
由容斥原理 $$ \left| U\setminus \bigcup_{i=1}^{k}A_{i} \right| = \sum_{m=0}^{\lfloor k/2 \rfloor} (-1)^{m} \sum_{c=1}^{m} N_k(m,c) \binom{n-(m+c)}{k-(m+c)} $$
通过组合意义，可以得到该式化简后等于 $$ \frac{n}{n-k}\binom{n-k}{k} $$
组合意义：从 $ n $ 个位置的循环排列中选择 $ k $ 个位置，使得任意两个选中位置不相邻的方案数。可通过将 $ k $ 个选中位置和 $ n-k $ 个未选中位置交替排列的方式理解此公式。
(3)
假设我们希望将 $ n $ 对夫妇安排在一张圆桌周围，其中男性和女性交替排列，并且每位女性与她的丈夫不相邻。座位旋转视为相同。证明安排的数量为： $$ (n-1)!\sum_{k=0}^{n} (-1)^{k} \dfrac{2n}{2n-k}\binom{2n-k}{k} (n-k)! $$
解
设 $ A_i $ 表示第 $ i $ 对夫妇相邻的事件。
全集：男女交替排列，考虑旋转等价。固定一名男性的位置，其余 $ n-1 $ 名男性排列有 $ (n-1)! $ 种，$ n $ 名女性排列有 $ n! $ 种，因此 $$ |U| = (n-1)! \cdot n! $$ 单项和：将第 $ i $ 对夫妇视为一个单元，该单元内部有 2 种排法（考虑男女交替约束）。剩余排列方式为 $ (n-1)! \cdot (n-1)! $，因此 $$ |A_i| = 2(n-1)!(n-1)!, \quad \sum_{i=1}^{n} |A_i| = 2n(n-1)!(n-1)! $$ $ m $ 重交集：选定 $ m $ 对夫妇 $ i_1, \ldots, i_m $ 相邻。在圆桌的 $ 2n $ 个座位上选择 $ m $ 个不重叠的相邻座位对，考虑循环对称性，方案数为 $ \frac{n}{n-m}\binom{2n-m}{m} $。
- 将 $ m $ 对夫妇分配到这 $ m $ 个座位对：$ m! $
- 每对夫妇内部排列：考虑男女交替的整体约束，共有 2 种全局配置
- 剩余 $ n-m $ 对夫妇的男女各自排列：$ (n-m)! \times (n-m)! $
因此 $$ \left|\bigcap_{j=1}^{m} A_{i_j}\right| = \frac{2}{2n-m}\binom{2n-m}{m} m! (n-m)!^2 $$
$ m $ 重交集和： $$ \sum_{1 \leq i_1 < \cdots < i_m \leq n} \left|\bigcap_{j=1}^{m} A_{i_j}\right| = \binom{n}{m} \cdot \frac{2}{2n-m}\binom{2n-m}{m} m! (n-m)!^2 = \frac{2n!}{2n-m}\binom{2n-m}{m} (n-m)! $$
由容斥原理： $$ \left|U \setminus \bigcup_{i=1}^{n} A_i\right| = \sum_{k=0}^{n} (-1)^k \frac{2n!}{2n-k}\binom{2n-k}{k} (n-k)! = (n-1)!\sum_{k=0}^{n} (-1)^k \frac{2n}{2n-k}\binom{2n-k}{k} (n-k)! $$
Problem 3
(1)
假设 $ f,g,h $ 都是数论函数，满足 $$ g(n) = \sum_{d|n}df(d), \quad h(n) = \sum_{d|n}f(d) $$ 证明 $$ h(n) = \dfrac{1}{n} \sum_{d|n} \varphi(n/d)g(d) $$ 证
我们讲 $ g(d) $ 带入目标表达式，得到 $$ \begin{align*} h(n) & = \dfrac{1}{n} \sum_{d|n}\varphi\left( \dfrac{n}{d} \right)\left( \sum_{e|d}ef(e) \right) \\ & = \dfrac{1}{n} \sum_{e|d, d|n}\varphi\left( \dfrac{n}{d} \right)ef(e) \\ & \xlongequal{d=ek} \dfrac{1}{n}\sum_{e|n}\sum_{k|(n / e)} \varphi\left( \dfrac{n}{ek} \right)ef(e) \\ & = \dfrac{1}{n}\sum_{e|n}ef(e) \sum_{k|(n / e)} \varphi\left( \dfrac{n / e}{k} \right) \end{align*} $$ 由于 $ \sum_{k|m}\varphi(k)=m $，因此 $$ \sum_{k|(n / e)} \varphi\left( \dfrac{n / e}{k} \right) = \dfrac{n}{e} $$ 带入得到 $$ h(n) = \dfrac{1}{n}\sum_{e|n}ef(e) \cdot \dfrac{n}{e} = \sum_{e|n}f(e) = \sum_{d|n}f(d) $$ 得证！
(2)
希望用 $ q $ 种颜色对一条由 $ n $ 颗珠子组成的项链进行着色。确定 $ N_n $，即着色方案的数量，其中如果两种着色方案可以通过旋转互相得到，则认为它们是相同的。
同样地，可以将 $ N_n $ 定义为在 $ [q] $ 上的循环序列的数量，其中通过旋转得到的两个序列被认为是相同的。求 $ N_n $ 。
（提示：设 $ M(d) $ 为长度为 $ d $ 且非周期性的循环序列的数量。）
解
按照提示设出 $ M(d) $，那么找项链最小的循环节，容易得到 $$ N_{n} = \sum_{d|n} M(d) $$ 我们需要计算 $ M(d) $。考虑普通序列和循环序列之间的关系。对于长度 $ n $，普通序列的总数为 $ q^{n} $，而每个最小周期为 $ d $ 的循环序列对应 $ d $ 中不同的表示，因此数量为 $ dM(d) $，这就得到了 $$ q^{n}= \sum_{d|n}dM(d) $$ 因此根据上一问的结论，我们就得到了 $$ N_{n} = \dfrac{1}{n}\sum_{d|n}\varphi\left( \dfrac{d}{n} \right)q^{d} $$
Problem 4
考虑一个偏序集 $ \mathcal{P} = (P, \preccurlyeq) $，其中 $$ P = \{(a_1, a_2, a_3, a_4) : a_i \in [4]\} $$ 并且 $ (a_1, a_2, a_3, a_4) \preccurlyeq (b_1, b_2, b_3, b_4) $ 当且仅当对于所有 $ i $ 都有 $ a_i \le b_i $。求满足 $ \mu(x, y) < 0 $ 的序对 $ x, y \in P $ 的数量。
解
对于两个 $ x,y\in P $，根据讲义的 Lemma 4.24，莫比乌斯函数的积性，得到 $$ \mu(x,y) = \prod_{i=1}^{4}\mu_{[4]}(x_{i},y_{i}) $$ 对于一个 $ [4] $ 的链，我们直接计算 $ \mu_{[4]}(a,b) $：
- 如果 $ a \not\leq b $，那么 $ \mu_{[4]}(a,b)=0 $。
- 如果 $ a=b $，那么 $ \mu_{[4]}(a,b)=1 $。
- 如果 $ b=a+1 $，那么 $ \mu_{[4]}(a,b)=-1 $。
- 如果 $ b\geq a+2 $，那么 $ \mu_{[4]}(a,b)=-\sum_{k=a}^{b-1}\mu_{[4]}(a,k)=0 $。
因此对于 $ x,y\in P $，$ \mu(x,y)\neq 0 $ 当且进行对于所有 $ i $ 满足 $ y_{i}-x_{i}\leq 1 $。定义 $ k $ 为 $ y_{i}=x_{i}+1 $ 的下标数量，其余 $ y_{i}=x_{i} $，于是就有 $$ \mu(x,y) = (-1)^{k} $$ 小于 $ 0 $ 当且仅当 $ k=1,3 $。
我们分开计算 $ k=1,3 $ 的序对数量：
- $ k=1 $，根据组合意义可以得到总数为 $ \binom{ 4 }{ 1 }\times 3^{1} \times 4^{3}=768 $。
- $ k=3 $，总数为 $ \binom{ 4 }{ 3 }\times 3^{3} \times 4=432 $。
因此总数为 $ 768+432=1200 $。
Problem 5
挑选两个在 $ [100] $ 范围内均匀、独立随机的数字 $ a $ 和 $ b $。在 $ [100] $ 上的偏序关系定义为整除关系，求 $ \mu(a, b) = -1 $ 的概率。
解
我们考虑直接算出所有满足条件的 $ (a,b) $ 的总数。对于 $ \mu(a,b) $，分类讨论：
- 如果 $ a \not\mid b $，那么 $ \mu(a,b)=0 $。
- 如果 $ a=b $，那么 $ \mu(a,b)=1 $。
- 如果 $ b=ka $（$ k \geq 2 $），那么 $ \mu(a,b)=\mu(1,k) $，其中 $ \mu(1,k)=(-1)^{\omega(k)} $ 当 $ k $ 无平方因子，否则 $ \mu(1,k)=0 $。
因此 $ \mu(a,b)=-1 $ 当且仅当 $ k $ 无平方因子且 $ \omega(k) $ 为奇数。定义 $ m $ 为 $ \omega(k) $ 的奇数值，其可能取值 $ m=1,3 $（因 $ k \leq 100 $，最大 $ m=3 $）。
我们分开计算 $ m=1,3 $ 的序对数量：
- $ m=1 $（$ k $ 为素数），总数为 $ \sum_{p \leq 100} \lfloor 100/p \rfloor =171 $。
- $ m=3 $（$ k $ 为三个不同素数的乘积），此类 $ k=30,42,66,70,78 $，总数为 $ \lfloor 100/30 \rfloor + \lfloor 100/42 \rfloor + \lfloor 100/66 \rfloor + \lfloor 100/70 \rfloor + \lfloor 100/78 \rfloor =3+2+1+1+1=8 $。
因此总数为 $ 171+8=179 $，于是 $$ \mathbb{P}(\mu(a,b)=-1) = \dfrac{179}{100^{2}} = \dfrac{179}{10000}. $$
Problem 6
设 $ a_1, a_2, \dots, a_n $ 是一些实数，它们的绝对值都满足 $ |a_i| \ge 1 $。考虑所有 $ 2^n $ 种线性组合 $ \sum_{i=1}^{n} \epsilon_i \cdot a_i $，其中每个 $ \epsilon_i $ 可以取值 $ \{-1, +1\} $。请证明，这些和中落在任意区间 $ (x-1, x+1) $ 内的数量至多为 $ \binom{n}{\lfloor n/2 \rfloor} $。
证
我们稍微转化一下题目，令 $ b_{i}=2a_{i} $，取 $ \{ b_{n} \} $ 的幂集 $ \mathcal{P} $，对于 $ S\in \mathcal{P} $，$ S $ 中所有元素之和显然可以有一组 $ \sum_{i=1}^{n}\epsilon_{i}\cdot a_{i} $ 平移得到，就这样 $ \mathcal{P} $ 可以和 $ 2^{n} $ 中 $ a_{i} $ 的线性组合一一对应。并且我们只需要考虑落在任意区间中的数量，所以平移操作并不会造成影响，于是我们的问题就转化成了 $ \mathcal{P} $ 中集合的元素之和落在任意区间 $ (x-1,x+1) $ 内的集合数量至多位 $ \binom{ n }{ \lfloor n / 2 \rfloor } $。
假设集合 $ S $ 是一个满足条件的集合。由于 $ \left| b_{i} \right|=2\left| a_{i} \right|>2 $，因此在 $ S $ 的基础上任意添加一个原来不包含的元素，至少会导致元素之和变化 $ 2 $，从而一定不会落在 $ (x-1,x+1) $ 中。这说明了若 $ \sum_{S}\in(x-1,x+1) $，那么任意 $ S' $ 满足 $ S\subset S' $，都有 $ \sum_{S'}\not\in (x-1,x+1) $。
因此我们直接考虑偏序集 $ (\mathcal{P},\subseteq) $。根据上面的分析，显然元素之和落在 $ (x-1,x+1) $ 的所有集合一定是一个反链。直接利用 Sperner 定理，得到此时反链的数量至多为 $ \binom{ n }{ \lfloor n / 2 \rfloor } $，因此满足条件的集合数量也至多为 $ \binom{ n }{ \lfloor n / 2 \rfloor } $。