Fubini 原理

编辑: -

Fubini 原理
观察以下的矩阵:

\(\displaystyle\left[\begin{array}{cccccc}1&6&0&4&1&1\\2&0&1&5&0&2\\0&0&7&0&3&3\\2&4&1&2&0&0\end{array}\right]\)

请问所有数字和一共多少?我们可以有系统一点,先求每一横列的和,得到 \(13, 10, 13, 9\),再把这四个和相加得到 \(13 +10 +13 +9 = 45\)。或者,先求每一直行的和,得到 \(5, 10, 9, 11, 4, 6\),相加得到 \(5+10+9+11+4+6 = 45\)。换句话说,

\(\displaystyle\sum^4_{i=1}\sum^6_{j=1}{a_{ij}}=\sum^6_{j=1}\sum^4_{i=1}{a_{ij}}\)

以上的想法是非常容易的,但这就是 Fubini 原理。

熟悉微积分的读者应该可以马上触发,这恰恰就是下述微积分中的 Fubini 原理的离散形式:若 \(f{(x,y)}\) 在长方形区域 \({R}:{a}\leq{x}\leq{b}\),\({c}\leq{y}\leq{d}\) 中连续,则

\(\displaystyle \int^{d}_{c}\int^{b}_{a} f(x,y) dx dy=\int^{b}_{a}\int^{d}_{c} f(x,y) dx dy\)

离散的好处就是可以不要管收敛发散的问题,基本上就是用两个角度去算同一个结果, 因此“Fubini原理”又称为“算两次原理”。更抽象一点说,Fubini 定理的叙述就是:

用两个方法算同一个量,结果会一样.

这个貌似无用的叙述看起来非常荒谬──但是它的确是非常有用的原理。底下举几个例子说明:

无言的证明

高中数学归纳法一定会有一题例题: 证明

\(1+3+5+\mbox{…}+(2n+1)=n^2\)

我们现在用两个方法来算下列 \( n\times n\) 点阵的点数。第一个方法,当然一共有 \({n}\times{n}={n^2}\) 个点。第二个方法,从左上角慢慢挖掉愈来愈大的正方形,得到 \(1+3+5+\mbox{…}+(2n+1)\)

Fubini 原理

因此由 Fubini 原理,原式得证。

附带一提,我个人一直觉得,除了数学归纳法以外,这个证明也应该要教给学生──数学归纳法牵涉到形式操作和逻辑论证,而 Fubini 定理的证明牵涉到美感以及直觉。这是数学的两个不同面向,不可偏废。而能让学生体会美感和直觉的例题很少,这正是一个好机会。

同样一个正方形,也可证明另一个高中数学的习题:

\(1+2+3+\mbox{…}+(n-1)+n+(n-1)+\mbox{…}+3+2+1={n^2}\)

我相信读者应该非常顺利可以看出来怎幺数点!

美国数学学会(MAA) 曾经出版了两本无言的证明(Proofs without Words I,II),里面有数以百计的初等数学等式或不等式的证明。其中有一些就用到 Fubini 原理,有些想法相当巧妙。比如,读者能否挑战一下用 Fubini 原理证明 \(1^3+2^3+\mbox{…}+n^3=(\frac{n(n+1)}{2})^2\)?

握手定理

离散数学中,一个图是指在一些顶点间连有一些边所成的图形,比如正方形再画一条对角线,就是一个四个顶点,五条边的图。我们称这个图的四个顶点的度(degree, 指连出去的边数) 分别是 \(2, 3, 2, 3\)

图的基本元素是「点」和「边」, 所以常常可以运用 Fubini 原理。任给一个图,所有顶点的 degree 总和可以有什幺结论?我们从另一个角度(Fubini原理!) 算 degree:观察到任一条边连接了两个顶点,这条边分别对这两个顶点各贡献了 degree \(1\)。所以,一条边贡献了 degree \(2\)。我们马上得到图论(graph theory) 的第一个定理:任意图 \(G\) 中,

\(\displaystyle\sum_{\nu\in{G}}deg(\nu)\) 是 \(2\) 的倍数,

即 degree 的总和必为偶数。

这个定理又叫做握手定理(Handshake theorem): 一群人见面互相握手,则把每个人握手的次数相加,结果一定是偶数。比如若有一群人参加舞会,两两跳舞,会后统计每个人跳舞的次数分别是 \(2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 10\),则可以断定中间一定有人记错了。

正多面体

最后我们来谈高中数学中另一个美丽(却一直被忽略) 的主题:正多面体。比如正方体正四面体等等都是正多面体。有几个正多面体呢?课本说 \(5\) 个。但是这怎幺导出来的呢?首先要用到多面体着名的 Euler 公式:任何一个凸多面体(不一定要正多面体),都有

\(\nu-e+f =2\)

\(\text{点数}-\text{边数}+\text{面数}=2\)

此外,Fubini 定理扮演了重要角色。底下我们来导出五个。

设多面体有点线面各有 \(\nu\),\({e}\),\({f}\) 个。且每面是 \({m}\) 边形,每个顶点 degree 为 \({n}\)。则一共多少边? 有两个方向可以考虑:

1. 共有 \({f}\) 面,每面是 \({m}\) 边形,所以一共 \(\displaystyle\frac{fm}{2}\) 边
2. 共有 \({v}\) 点,每点 degree 是 \({n}\),所以一共 \(\displaystyle\frac{vn}{2}\) 边

所以由 Fubini 原理,

\(\displaystyle e=\frac{fm}{2}=\frac{vn}{2}\)

因此 \(\displaystyle f=\frac{2e}{m},~v=\frac{2e}{n}\) 带回去 Euler 公式得到 \(\displaystyle\frac{2e}{n}-{e}+\frac{2e}{m}=2\),即

\(\displaystyle\frac{1}{m}+\frac{1}{n}=\frac{1}{2}+\frac{1}{e}\),

即 \(\displaystyle\frac{1}{m}+\frac{1}{n}>\frac{1}{2}\)。这个式子可化为

\((m-2)(n-2)<4\)

但是本来\(m\geq{3},~n\geq{3}\)(否则根本拼不成立体),所以上式表示两个自然数乘积\(< 4\)。所以只能是 \(1, 2, 3\)。因此只有五个可能

\((m-2, n-2) = (1, 1), (2, 1), (1, 2), (1, 3), (3, 1)\)

\((m, n) = (3, 3), (4, 3), (3, 4), (3, 5), (5, 3)\)

我们算出来正多面体只能有五个! 真正去拼拼看是拼的出来的,比如 \((3, 5)\) 表示每个面是正三角形,每个顶点 degree 是 \(5\)──这是正二十面体。因此我附带一提,上述的解也顺便得到了这五个正多面体间有些是互相对偶的(边数和点数互换),由此可以引出非常深刻的几何学,不过我们在此打住。

要用 Fubini 原理处理的组合问题,通常都已经超过一般高中排列组合教学的深度。但诚如第一节给的例子,善用 Fubini 原理可以清楚解释一些等式的来源,是有实际上教学的意义的。

你会喜欢下面的文章? You'll like the following article.