Problem 1
(1)
求 $$ \sum_{k=0}^{n} \binom{ 2n }{ 2k } $$
解
$$ \begin{align*} & \sum_{k=0}^{n} (-1)^{k}\binom{ n }{ k } = 0 \\ \implies & \sum_{k=0}^{2n} (-1)^{k}\binom{ 2n }{ k } =0 \\ \implies & \sum_{k=0}^{2n} \binom{ 2n }{ 2k } = \sum_{k=1}^{2n} \binom{ 2n }{ 2k - 1 } \end{align*} $$ 同时由于 $$ \sum_{k=0}^{2n} \binom{ 2n }{ 2k } + \sum_{k=1}^{2n} \binom{ 2n }{ 2k - 1 } = \sum_{k=0}^{2n} \binom{ 2n }{ k } = 2^{2n} $$ 得到 $$ \sum_{k=0}^{2n} \binom{ 2n }{ 2k } = 2^{2n-1} $$
(2)
求 $$ \sum_{k=0}^{3n} \binom{ 3n }{ 3k } $$
解
同理 (1) 的解法，设 $ z $ 为一个三次单位根，那么根据二项式定理有 $$ \sum_{k=0}^{n} z^{k}\binom{ n }{ k } = (1 + z)^{n} $$ 那么设 $ \sum_{k=0}^{3n}\binom{ 3n }{ 3k }=A,\,\sum_{k=0}^{3n-1}\binom{ 3n }{ 3k+1 }=B,\,\sum_{k=0}^{3n-1}\binom{ 3n }{ 3k+2 }=C $，就能得到 $$ A + z\cdot B + z^{2}\cdot C = (1 + z)^{3n} $$
设 $ \omega=e^{ \frac{2\pi i}{3} } $ ，则有 $ 1+\omega+\omega^{2}=0,\omega^{3}=1 $. 分别令 $ z \in \{ 1,\omega,\omega^{2} \} $ 带入上式，得到 $$ \begin{cases} A + B + C & = (1+1)^{3n} \\ A + \omega B + \omega^{2}C & = (1+\omega)^{3n} \\ A + \omega^{2}B + \omega C & = (1 + \omega^{2})^{3n} \end{cases} $$ 将三式相加并利用 $ 1+\omega+\omega^{2}=0 $ 的性质，移项即可得到 $$ A = \dfrac{2^{3n} + (1+\omega)^{3n} + (1+\omega^{2})^{3n}}{3} $$ 带入 $ \omega=-\dfrac{1}{2}+\dfrac{\sqrt{ 3 }}{2}\cdot i $ 得到 $ 1+\omega=e^{ \frac{\pi i}{3} },1+\omega^{2}=e^{ - \frac{\pi i}{3} } $ ，带入上式并化简可得 $$ \sum_{k=0}^{n} \binom{ 3n }{ 3k } = \dfrac{2^{3n} + 2(-1)^{n}}{3} $$
Problem 2
(1) $$ \binom{ n }{ m } \binom{ m }{ k } = \binom{ n }{ k } \binom{ n-k }{ m-k } $$ 证 1
考虑左右两边组合意义：
$ \binom{ n }{ m }\binom{ m }{ k } $ 可以表示在 $ n $ 个人中先选出 $ m $ 个人，再在这 $ m $ 个人中选出 $ k $ 个人的概率，本质上是把 $ n $ 个人分成了 $ 3 $ 类，每类分别有 $ n-m,\,m-k,\,k $ 个人。
$ \binom{ n }{ k }\binom{ n-k }{ m-k } $ 可以看成在 $ n $ 个人里面选出 $ k $ 个人，再在剩下 $ n-k $ 个人中选出 $ m-k $ 个人，同样也可以看成是分成了分别有 $ n-m,\,m-k,\,k $ 个人的三类。
因此左右表示同一个组合意义，值必然相同。
证 2 $$ \binom{ n }{ m } \binom{ m }{ k } = \dfrac{n^{\underline{m}}}{m!}\cdot \dfrac{m^{\underline{k}}}{k!} = \dfrac{n^{\underline{k}}}{k!}\cdot \dfrac{n^{\underline{m}}}{n^{\underline{k}}}\cdot \dfrac{m^{\underline{k}}}{m!} = \dfrac{n^{\underline{k}}}{k!}\cdot \dfrac{(n-k)^{\underline{m-k}}}{(m-k)!} = \binom{ n }{ k } \binom{ n-k }{ m-k } $$
(2) $$ \sum_{k=0}^{r} \binom{ n+k }{ k } = \binom{ n+r+1 }{ r } $$ 证 1
考虑组合意义。
右式变形为 $ \binom{ n+r+1 }{ n+1 } $ 可以表示为在 $ n+r+1 $ 个人中选出 $ n+1 $ 个人的方案数。
左侧变形为 $ \sum \binom{ n+k }{ n } $ 可以看成枚举要选的最后一个人是第 $ n+k+1 $ 个人，在前 $ n+k $ 个人中选择 $ n $ 个人，所有情况的和恰好也是在 $ n+r+1 $ 个人中选出 $ n+1 $ 个人的方案数。
因此左右两次可以表达同一个组合意义，值相同。
证 2
考虑等式 $$ \binom{ n+k }{ k } + \binom{ n+k }{ k-1 } = \binom{ n+k+1 }{ k } $$ 移项得到 $$ \binom{ n+k }{ k } = \binom{ n+k+1 }{ k } - \binom{ n+k }{ k-1 } $$ 在求和可得 $$ \sum_{k=0}^{r} \binom{ n+k }{ k } = \sum_{k=0}^{r} \left[ \binom{ n+k+1 }{ k } - \binom{ n+k }{ k-1 } \right] = \binom{ n+r+1 }{ r } - \binom{ n }{ -1 } $$ 认为 $ \binom{ n }{ k } $ 在 $ k>n $ 或者 $ k< 0 $ 时 $ \binom{ n }{ k }=0 $ ，则可得到 $$ \sum_{k=0}^{r} \binom{ n+k }{ k } = \binom{ n+r+1 }{ r } $$
(3) $$ \sum_{k=0}^{n} \binom{ n }{ k } ^{2}k = n\binom{ 2n-1 }{ n-1 } $$ 证 1
考虑组合意义，同样以在班级中选人举例。
由于 $ 2\binom{ 2n-1 }{ n-1 }=\binom{ 2n }{ n } $，右侧变形为 $ \frac{n}{2}\binom{ 2n }{ n } $ ，可以表示在 $ 2n $ 个人（男女各一半）的班级中选出 $ n $ 个人当班委，再在这 $ n $ 个人中选出一个男生当班长的方案数。
左侧变成 $ \sum_{k=0}^{n}\binom{ n }{ k }\binom{ n }{ n-k }k $ ，对于每个 $ k $ 表示 $ n $ 个男生 $ n $ 个女生的班级中，男生选出 $ k $ 个人，女生选出 $ n-k $ 个人，共 $ n $ 个人当班委，再从 $ k $ 个男生班委中选出一个人当班长的方案数。把所有 $ k $ 的情况合起来，同样可以得到在男女各半的 $ 2n $ 个人中选出 $ n $ 个班委和一个男生班长的方案数。
因此左右两式可以表达同一个组合意义，值相同。
证 2
将恒等式 $$ k\binom{ n }{ k } = n\binom{ n-1 }{ k-1 } = n\binom{ n-1 }{ n-k } $$ 带入左式，左右两侧消去 $ n $ 后，只需证 $$ \sum_{k=0}^{n} \binom{ n }{ k } \binom{ n-1 }{ n-k } = \binom{ 2n-1 }{ n-1 } $$ 根据 Vandermonde 卷积 $$ \sum_{k=0}^{n} \binom{ n }{ k } \binom{ n-1 }{ n-k } = \binom{ n + n - 1 }{ n } = \binom{ 2n-1 }{ n } $$ 因此原式得证！
(4) $$ \sum_{i=0}^{a} \binom{ a }{ i } \binom{ b+i }{ a } = \sum_{i=0}^{a} \binom{ a }{ i } \binom{ b }{ i } 2^{i} $$ 证 1
从组合意义证明，同样以班级选班委举例。考虑一个班级有 $ a $ 个班委和 $ b $ 个非班委，现进行班委换届。
左式对于每个 $ i $ ，$ \binom{ a }{ i }\binom{ b+i }{ a } $ 表示 $ a $ 个班委中有 $ i $ 个人有意愿再参与下一届的班委选举，在 $ b+i $ 个人中选举产生新的 $ a $ 个班委。每种情况加起来，表示 $ a $ 个原班委自由选择是否参加选举的前提下班委换届的所有方案数。
右式对于每个 $ i $ ，将 $ \binom{ a }{ i } $ 变换为 $ \binom{ a }{ a-i } $ ，$ \binom{ a }{ a-i }\binom{ b }{ i } $ 表示新一届班委中有 $ i $ 个来自原先 $ b $ 个非班委的方案数，$ 2^{i} $ 表示剩下没选上、未知竞选意愿的 $ i $ 个原班委所有竞选意愿的可能。将每种情况加起来，也同样可以得到 $ a $ 个原班委自由选择是否参选的前提下班委换届的方案数。
因此左右两式可以表示相同的组合意义，值相同。
证 2
根据 Vandermonde 卷积 $$ \binom{ b+i }{ a } = \sum_{j=0}^{i} \binom{ i }{ j } \binom{ b }{ a-j } $$ 带入左式得到 $$ \begin{align*} \sum_{i=0}^{a} \binom{ a }{ i } \binom{ b+i }{ a } & = \sum_{i=0}^{a} \sum_{j=0}^{i} \binom{ b }{ a-j } \binom{ a }{ i } \binom{ i }{ j } \\ & = \sum_{i=0}^{a} \sum_{j=0}^{i} \binom{ b }{ a-j } \binom{ a }{ j } \binom{ a-j }{ i-j } \\ & = \sum_{j=0}^{a} \binom{ b }{ a-j } \binom{ a }{ j } \sum_{i=j}^{a} \binom{ a-j }{ i-j } \\ & = \sum_{j=0}^{a} \binom{ b }{ a-j } \binom{ a }{ a-j } 2^{a-j} \\ & \xlongequal{i=a-j} \sum_{i=0}^{a} \binom{ b }{ i } \binom{ a }{ i } 2^{i} \end{align*} $$
Problem 3
给定集合 $ A=\{1,2,\ldots,n\} $ 与正整数 $ k $，从 $ A $ 中选出一组按三角阵排列的 $ \binom{k+1}{2} $ 个子集 $$ \begin{matrix} S_{1,1} \\ S_{2,1} & S_{2,2} \\ \vdots & \vdots & \ddots \\ S_{k,1} & S_{k,2} & \dots & S_{k,k} \end{matrix} $$ 满足每个集合是它左边和上方的集合（如果存在）的子集。需要求出满足这个要求的选择方案数。
解
由于每个元素相互独立，具体方案和元素无关，因此可以考虑一个元素的合法出现方式（在哪些集合会包含这个元素）的总数，设为 $ f(k) $ ，那么最后答案即为 $ [f(k)]^{n} $ 。
现在考虑 $ x\in A $ ，根据包含关系，不难看出如果 $ x\in S $ ，那么 $ S $ 左侧和上方（如果存在）的集合都会包含 $ x $。因此出现 $ x $ 的集合在 $ k $ 阶三角形中可以形成一个从 $ (1,1) $ 出发，每次可以向右或者下方通行的有向图。
考虑某个合法方案，设元素最后一次出现在对角线（$ S_{1,1},\dots,S_{k,k} $）的位置为 $ S_{r,r} $ ，那么根据包含关系，此时显然 $ x $ 包含于上方的 $ r $ 阶小三角阵中的每一个元素，并且不会出现在下方的 $ k-r $ 阶小三角方阵中（否则必然会再次出现在对角线中）。因此只需要考虑 $ x $ 在余下部分，也就是四个顶点分别为为 $ (r+1,1),(r+1,r),(k,1),(k,r) $ 的长方形区域中的合法方案数即可。
对于这样的长方形区域，我们可以按行考虑，显然根据包含的规则， $ x $ 在每一行出现的形式必定是从最左侧开始连续的一段，并且上到下每一行 $ x $ 出现的次数是不降的。因此我们可以把这个问题转化为求一个长度为 $ k-r $ ，每个数范围为 $ 0\sim r $ 的单调不降序列的方案数。设第 $ i $ 个数的值为 $ t_{i} $ ，那么方案数为 $$ \begin{align*} \sum_{t_{1}=0}^{r} \sum_{t_{2}=0}^{t_{1}} \dots \sum_{t_{k-r}=0}^{t_{k-r-1}} 1 & = \sum_{t_{1}=0}^{r} \dots \sum_{t_{k-r-1}=0}^{t_{k-r-2}} (t_{k-r-1} + 1) \\ & = \sum_{t_{1}=0}^{r} \dots \sum_{t_{k-r-1}=0}^{t_{k-r-2}} \binom{ t_{k-r-1} + 1 }{ 1 } \\ & = \sum_{t_{1}=0}^{r} \dots \sum_{t_{k-r-2}=1}^{t_{k-r-3}} \binom{ t_{k-r-2}+2 }{ 2 } \\ & \dots \\ & = \sum_{t_{1}=0}^{r} \binom{ t_{1} + k-r-1 }{ k-r-1 } = \binom{ k }{ k-r } \end{align*} $$ 因此 $$ f(k) = \sum_{r=0}^{k} \binom{ k }{ k-r } = \sum_{r=0}^{k} \binom{ k }{ r } = 2^{k} $$ 所以方案数为 $$ [f(k)]^{n} = 2^{nk} $$
Problem 4
给定一个长度为 $ mn+1 $ 的序列 $ a_{0},a_{1},\ldots,a_{mn} $，其中每一项只可能取 $ 1 $ 或 $ 1-m $，并且满足总和 $$ \sum_{i=0}^{mn} a_i = 1 . $$ 在此条件下：
(1)
证明：在该序列里，取值为 $ 1 $ 的项共有 $ mn-n+1 $ 个，而取值为 $ 1-m $ 的项共有 $ n $ 个。
证
设 $ 1 $ 有 $ a $ 个，$ 1-m $ 有 $ b $ 个，那么得到方程 $$ \begin{cases} a + b = mn+1 \\ a + (1-m)b = 1 \end{cases} $$ 直接可以解得 $$ \begin{cases} a = mn-n+1 \\ b=n \end{cases} $$
(2)
把序列首尾相接排成一个圆环。考虑所有可能的“起点”选择（即对序列做循环移位）。
证明：恰好存在唯一一个起点 $ k $，使得从该位置开始依次相加得到的所有部分和都为正，即 $$ a_k,\ a_k+a_{k+1},\ \ldots,\ a_k+a_{k+1}+\cdots+a_{k-1} $$ 全部大于 $ 0 $（下标按模 $ mn+1 $ 计算）。
证
考虑序列前缀和 $ S_{t} = \sum_{i=0}^{t}a_{i} $ ，并且 $ S_{-1}=0 $。在序列 $ \{ S_{-1},S_{0},\dots,S_{mn} \} $ 中存在最小值 $ S_{k} $，如果有多个，取其中下标最大的为 $ S_{k} $，显然 $ S_{k} $ 唯一。
于是 $ \forall r\in \{ k+1,\dots,mn \} $ ，有 $ S_{r}>S_{k} $ ，因此从 $ k+1 $ 到 $ r $ 的子段和为 $ \sum_{i=k+1}^{r}a_{i}=S_{r}-S_{k}>0 $
并且 $ \forall l\in \{ 0,\dots,k \}: S_{l-1}\leq S_{k} $ ，因此从 $ k+1 $ 开始的一段循环序列中的和为（考虑在原序列中这一段的补集）： $$ \sum_{i=k+1}^{mn+1+l}a_{i\bmod (mn+1)}=\sum_{i=0}^{mn}a_{i} - \sum_{i=l}^{k}a_{i}=1-(S_{k}-S_{l-1}) = 1+S_{l-1}-S_{k}\geq 1 > 0 $$
综上，我们找出了唯一满足从该位置开始左右的部分和都为正的一个位置，证毕。
(3)
求满足“所有前缀部分和都为正”的序列 $ a_{0},a_{1},\ldots,a_{mn} $ 的总数。
证 1
不考虑任意前缀和为正的限制，所有的序列总数为 $ \binom{ mn+1 }{ n } $（总共 $ mn+1 $ 个数，选择 $ n $ 个数为 $ 1-m $）。
对于任意一个序列，根据 $ (2) $ 的结论，存在唯一的 $ k $ 使得从 $ k $ 开始的所有前缀和为正，因此我们将改序列的下标向左平移 $ k $ 即可得到一个合法的序列。
这说明每种圆排列都对应唯一一个合法的序列，所以答案为 $$ \dfrac{1}{mn+1}\binom{ mn+1 }{ n } $$
证 2（没证出来😭）
首先必然有 $ a_{0}=1 $ ，否则 $ a_{0}=1-m< 0 $ 已经不满足条件。因此可以在原序列去掉 $ a_{0} $，问题的约束转化为 $ \sum_{i=1}^{mn}a_{i}=0 $ ，保证从 $ a_{1} $ 开始的前缀和非负即可。
将问题转化为在一个二维网格上路径计数的模型：从起点 $ O(0,0) $ 出发，每一步会向上走 $ 1 $ 格或者向右走 $ 1 $ 格，目标走到 $ D(n,n(m-1)) $，其中前缀和非负的约束转化为不能越过直线 $ l:y=(m-1)x $ 。
我们将向上走的操作记为 $ U $，向右走的操作记为 $ R $，显然最终一个 $ R $ 可以对应 $ (m-1) $ 个 $ U $ 操作。由于一个 $ R $ 操作的跨度过大，使我们难以操作“路径中第一个不合法的点”，因此我们考虑将 $ R $ 拆解成粒度更小 $ (m-1) $ 个连续的 $ r $ 操作，可以看成向右移动 $ \dfrac{1}{m-1} $ 格的距离。此时一条路径中含有 $ N=n(m-1) $ 个 $ U $ 操作和 $ r $ 操作。
考虑一条不合法的路径，可以看成一个不合法的操作序列 $ S $，单独找出第一次越过 $ l $ 的 $ r $ 操作，可以将 $ S $ 分解成 $$ S = ArB $$ 其中 $ A $ 的末尾刚好在 $ l $ 上，满足 $ r=U $ （数量），$ B $ 为剩余序列。
由于 $ A $ 的性质更好，所以参考 Catalan 数的证明，我们考虑将 $ A $ “反射”，将其中的所有 $ r $ 和 $ U $ 操作互换，得到 $ \overline{A} $，从而构造出 $$ S'=\overline{A}rB $$ 于是我们得到了一个不合法序列 $ S $ 和某个 $ S' $ 序列的双射。从 $ S' $ 映射会 $ S $ 同样只需要找出第一次到达 $ l $ 的位置找出 $ \overline{A} $，再进行一次“反射”即可。
我们再定义一个压缩操作，表示从左到右扫描一个序列，遇到 $ U $ 直接加入新的序列，遇到累计遇到 $ (m-1) $ 个 $ r $ 向新序列中加入一个 $ R $。这样对于任意一个 $ U $ 和 $ r $ 数量均为 $ N $ 的序列，压缩后都会得到一个无约束的 $ U-R $ 序列。我们将这个操作记为 $ C(S) $，$ S $ 表示操作的 $ U-r $ 序列。
于是现在我们对于一条不合法的路径，将其细化为 $ U-r $ 序列 $ S $ 后再反射为 $ S' $，压缩后得到 $ P=C(S') $，这是一个无约束的 $ U-R $ 序列，含有 $ n $ 个 $ R $。
// 通过手动计算小数据，可以猜出一个合法序列对应 $ n(m-1) $ 个非法序列的结论。并且注意到有 $ N $ 个 $ U $ 操作，因此希望通过引入某种“标记操作”，来标记某个 $ U $ 操作，来构造出一个 $ \text{非法序列} \leftrightarrow (\text{合法序列},u^{*}) $ 的双射，其中 $ u^{*} $ 表示被标记的 $ U $ 操作。这样说明一个合法序列对应 $ N $ 个非法序列，于是合法序列数量为 $$ \dfrac{1}{N+1}\binom{ mn }{ n } = \dfrac{1}{n(m-1)+1}\binom{ mn }{ n } = \dfrac{1}{mn+1}\binom{ mn+1 }{ n } $$