集合论中基数关系：配对与二项式恒等式问题求解

题目描述 #

设$A$是一个包含$n$个元素的非空集合：

• a) 确定满足$X \subseteq Y \subseteq A$，且$\text{card}(X)=k$，$\text{card}(Y)=m$（其中$1 \leq k \leq m \leq n$，$k$和$m$为固定值）的配对$(X,Y)$的数量。
• b) （修正笔误后）证明恒等式：$\binom{n}{0}\binom{n}{m} + \binom{n}{1}\binom{n-1}{m-1} + \ldots + \binom{n}{m}\binom{n-m}{0} = 2^m \binom{n}{m}$。

你的初始思路回顾 #

你提到对问题a用乘法法则得到$\binom{m}{n}\binom{k}{m}$，但不确定是否正确；对于问题b，你考虑了满足$X \subseteq Y \subseteq A$且$|X|=k, |Y|=m$的配对总数，写成$\sum_{k=0}^{m} \binom{m}{n} \binom{k}{m} = \binom{m}{n} \left( \sum_{k=0}^{m}\binom{k}{m} \right)$。

问题a的正确解答 #

你的思路方向是对的，但组合数的下标写反啦！正确的计算逻辑是这样的：
要构造符合要求的配对$(X,Y)$，可以分两步完成：

1. 先从$A$的$n$个元素中选出$m$个元素组成集合$Y$，选法有$\binom{n}{m}$种；
2. 再从已选好的$Y$的$m$个元素中选出$k$个元素组成子集$X$，选法有$\binom{m}{k}$种。

根据乘法原理，总的配对数就是两步选法的乘积：$\binom{n}{m} \times \binom{m}{k}$。

另外，这个结果也可以换一种思路推导：先选$X$（$\binom{n}{k}$种选法），再从$A$中剩下的$n-k$个元素里选$m-k$个元素加到$X$中得到$Y$，即$\binom{n}{k} \times \binom{n-k}{m-k}$，这两个式子是等价的，你可以通过组合数公式验证一下。

问题b的正确解答 #

首先说明：原题目里的组合数下标存在笔误，$\binom{0}{n}$这类写法不符合组合数定义（组合数$\binom{a}{b}$要求$a \geq b \geq 0$），修正后才是有意义的恒等式，接下来用双重计数法证明：

角度1：计算等式左边的含义 #

左边的每一项$\binom{n}{k}\binom{n-k}{m-k}$，其实就是问题a中固定$k$时，满足$X \subseteq Y \subseteq A$、$|X|=k$、$|Y|=m$的配对$(X,Y)$的数量。把$k$从0到$m$累加，左边的总和就是所有满足$Y \subseteq A$且$|Y|=m$的子集$Y$，以及$Y$的任意子集$X$的配对$(X,Y)$的总数。

角度2：换一种方式计算同一个总数 #

我们可以先选$Y$：从$A$中选$m$个元素组成$Y$，有$\binom{n}{m}$种选法；对于每个选定的$Y$，它的子集$X$共有$2^{m$个（因为$m$元集合的子集总数是$2}m$）。因此总的配对数就是$\binom{n}{m} \times 2^m$，也就是等式右边的结果。

因为两种方式计算的是同一个集合的元素个数，所以左边等于右边，恒等式得证。

另外你提到的$\sum_{k=0}^{{m}\binom{m}{k}=2}m$是对的，这是二项式定理的直接结论（$(1+1)^m=\sum_{k=0}m\binom{m}{k}$），所以$\binom{n}{m} \times \sum_{k=0}^m\binom{m}{k} = \binom{n}{m} \times 2^m$，也能对应上我们的证明结果。

备注：内容来源于stack exchange，提问作者math.enthusiast9