第七十六讲 算两次 讲义-2026年高中数学竞赛

第七十六讲  算两次

广义上讲, 算两次是指对同一个对象从两种不同的角度加以计算 (或估计), 从而得到等式(或不等式)关系, 这样的例子在数学中比比皆是。狭义上讲, 算两次是指两重计数法, 或称富比尼 (Fubini) 原理。

1. 富比尼原理

我们用到的富比尼原理主要是下面有限集合的形式, 更一般的富比尼原理是指二重积分中的交换积分符号,是积分理论中的重要内容。

富比尼原理 设 是两个有限集合, 。 设 是定义在 上的函数。则

例 1 设 是一个 元集合。求 。

解 考虑集合 ,且 。一方面,对于每个固定的 ,恰有 个 ,满足 ,因此 。另一方面,对每个固定的 ,包含 的集合 恰有 个,故 。结合两方面的计算可知

评注 1. 由于 的 元子集恰有 个,按 的元素个数分类计算可得 。于是我们得到了组合恒等式

在 例 1 中用组合恒等式直接证明了上式。

2. 算两次的过程也可以用交换求和符号的方式来写,

例 2 设 是 的所有排列中恰有 个不动点的排列个数。 证明:

注: 对 的排列 ,若 ,则称 是这个排列的一个不动点。

证明 设 是 的全体排列所构成的集合。对 ,记 为 的不动点的个数。定义集合

一方面，

另一方面,以某个 为不动点的排列 一共有 个,故

结合两方面的计算即得结论成立。

3. 应用举例

例 3 设 是正整数, 是直角坐标平面上 个整点构成的集合。设 是四个顶点均在 中的所有正方形构成的集合。对 , 2，3，记 为 的二元子集 的个数，满足恰有 个 中的正方形其四个顶点包含 。证明: 。

证明 对 中每个正方形,取其四个顶点的二元子集,计算这些二元子集的个数, 有

另一方面,计算 的所有二元子集个数,有

下面计算 。对于一个整点正方形 ,可作一个边平行于坐标轴的正方形 , 使得 分别在 的四条边上,特别当 的边平行于坐标轴时, 就是 。我们称 为 的外接标准正方形。易知,若 的边长为 ,则以 为外接标准正方形的整点正方形个数等于 。以 分类来计算 ,顶点在 中、边长等于 且边平行于坐标轴的正方形个数为 个,故

从而有

即 。

例 4 给定平面上 个点,其中任意三点不共线, 。若其中 个点的凸包是一个凸 边形,且内部不含其他给定点,则称这 个点是 “好的”。对 , 记好的 点集数目为 。证明: 不依赖于点的位置,只与 有关。

证明 将平面上 个点的集合记为 。下面用两种方法来计算和式