奥数组合

无三角形的图不允许两个相邻顶点有公共邻居,因此它们的度数之和被 $n$ 严格限制;将顶点分成大致相等的两组并连接所有跨组的点对,会在所有地方同时使这个上界饱和,这正是为何均衡的完全二部图是极值例子。

对 $n$ 归纳。当 $n \le 2$ 时命题显然成立,因为 $\lfloor n^2/4 \rfloor \ge 0$ 且至多2个顶点的图至多有1条边。

假设命题对所有顶点数小于 $n$ 的无三角形图成立,设 $G$ 是 $n$ 个顶点上的无三角形图。若 $G$ 没有边则界显然成立,故设 $G$ 有一条边 $uv$。由于 $G$ 无三角形,$u$ 与 $v$ 没有公共邻居,即 $N(u) \cap N(v) = \varnothing$。

因为 $N(u)$ 与 $N(v)$ 是 $n$ 个顶点集合中的不相交子集,故 $\deg(u)+\deg(v) = |N(u)|+|N(v)| = |N(u) \cup N(v)| \le n$。

从 $G$ 中删去 $u$ 与 $v$,得到 $n-2$ 个顶点上的无三角形图 $G'$。$G$ 的每条边要么是边 $uv$,要么是 $u$ 或 $v$ 到其余顶点的边,要么是 $G'$ 的边;仔细计数可得 $e(G) = e(G') + \deg(u) + \deg(v) - 1$(其中 $-1$ 修正了边 $uv$ 在 $\deg(u)+\deg(v)$ 中被计入一次但它并非 $G'$ 的边这一点)。

由归纳假设 $e(G') \le \lfloor (n-2)^2/4 \rfloor$,故 $e(G) \le \lfloor (n-2)^2/4 \rfloor + n - 1$。直接计算得 $(n-2)^2/4 + n - 1 = n^2/4 - n + 1 + n - 1 = n^2/4$,分别检验 $n$ 的奇偶情形可知 $\lfloor (n-2)^2/4 \rfloor + n - 1 \le \lfloor n^2/4 \rfloor$ 恰好成立。因此 $e(G) \le \lfloor n^2/4 \rfloor$,归纳完成。

对于极值情形,两部大小为 $\lfloor n/2 \rfloor$ 与 $\lceil n/2 \rceil$ 的完全二部图不含三角形(任何三角形都需要同一部分内的一条边,但不存在这样的边),且恰好有 $\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \lfloor n^2/4 \rfloor$ 条边,因此该界是紧的。

两边数的是同一件事——从 $2n$ 人中选出 $n$ 人的方法数——因此完全不需要对二项系数做代数变形,只需仔细地用两种不同顺序描述同一个选择过程。

考虑由 $n$ 个男生和 $n$ 个女生组成的 $2n$ 人集合。我们用两种方式数从这 $2n$ 人中恰好选出 $n$ 人组成委员会的方法数。

直接地,按定义这个数是 $\binom{2n}{n}$,因为我们只是从 $2n$ 个对象中选 $n$ 个。

另一方面,按委员会中包含的男生人数对所有合法委员会分类。若委员会恰好包含 $k$ 个男生,即对某个满足 $0 \le k \le n$ 的 $k$ 而言,那么这 $k$ 个男生有 $\binom{n}{k}$ 种选法,其余 $n-k$ 名成员必须是女生,从 $n$ 个女生中选出有 $\binom{n}{n-k}$ 种方法。由对称恒等式 $\binom{n}{n-k} = \binom{n}{k}$,恰好包含 $k$ 个男生的委员会数为 $\binom{n}{k} \cdot \binom{n}{k} = \binom{n}{k}^2$。

每个合法的 $n$ 人委员会都有一个介于 $0$ 到 $n$ 之间确定的男生人数 $k$,且不同 $k$ 值之间不会重复计数任何委员会,因此对所有 $k$ 求和即得委员会总数 $\sum_{k=0}^{n} \binom{n}{k}^2$。

由于两个表达式数的是完全相同的委员会集合,它们必须相等:$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$。