对应原理(The Principle of Correspo

对应原理

已知每班教室里有 $$36$$ 张座位。现在老师进教室后,眼光一扫,发现没有空位,每个位子上都作了一个人。请问有多少学生?这个问题有什幺好问的,答案就是 $$36$$。但是仔细一想,老师并没有一个一个数学生不是吗?怎幺知道就是 $$36$$ 个?当然原因是这样:没有空位,每个位子上都坐一个人,表示学生和座位一样多。

这其实就是对应原理:

对应原理:如果两集合 $$S,T$$ 之间有一个对应(bijection),则 $$|S| = |T|$$

再看仔细一点:老师想要知道学生的个数 $$|S|$$,但是已知座位的个数 $$|T|$$。现在学生 $$(S)$$ 和座位 $$(T)$$ 之间有一一对应(没有空位,每个位子上都坐一个人),因此学生和座位必须一样多 $$(|S| = |T|)$$。

对应原理说来简单,但是要找到好的对应来帮助解题,就是各凭本事了,这也是精彩所在。现行高中课本的排列组合并不强调对应。但是在介绍重複组合时,实际上已经偷用了对应原理。重複组合的第一个例子是:$$3$$ 种不同的水果数量皆不虞匮乏,一共要选 $$5$$ 个,共有几种方法?这样想:有五个水果和两个隔板排成一列;第一个隔板之前,两个隔板之间,第二个隔板之后分别代表三种水果的个数。多画几个例子:

$$\bigcirc\bigcirc\big|\bigcirc\bigcirc\big|\bigcirc$$ 表示 $$2 + 2 + 1$$,即苹果 $$2$$ 个, 橘子 $$2$$ 个, 香蕉 $$1$$ 个.
$$\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\big|\big|$$ 表示 $$5+0+0$$,即苹果 $$5$$ 个, 橘子 $$0$$ 个, 香蕉 $$0$$ 个.
$$\bigcirc\bigcirc\bigcirc\big|\bigcirc\big|\bigcirc$$ 表示 $$3+1+1$$,即苹果 $$3$$ 个, 橘子 $$1$$ 个, 香蕉 $$1$$ 个.
$$\big|\bigcirc\big|\bigcirc\bigcirc\bigcirc\bigcirc$$ 表示 $$0+1+4$$,即苹果 $$0$$ 个, 橘子 $$1$$ 个, 香蕉 $$4$$ 个.
. . . . . .

因此,任何一个o, o, o, o, o, |, | 的排列就对应到一种选水果的方法。而五个球和两根棍子的排列我们已经会算了,因此一共有 $$\frac{7!}{5!2!}=21$$ 种方法。如果不用对应原理转化成直线排列处理,会变得非常难解释。

寻找对应

利用 $$S, T$$ 间的对应与已知的 $$|T|$$ 来求 $$|S|$$ 是对应原理的一个面向。另一个面向可以这样说:如果 $$|S|=|T|$$,则理论上 $$S$$ 和 $$T$$ 之间应该有个对应。

在高等数学的研究上,常常我们经过很複杂的方法,对正在研究的对象算出一个意外简单的答案,而这个简单的答案是我们熟知的某个结构的量;或是两个貌似不相干的计数问题,算出同一个答案。不管是哪一种,这就表示应该有一个简单的解释。

例如:在上一篇文章中,我们用乘法原理得到由 $$0, 1$$ 组成的长度为 $$n$$ 的字(words) 共有 $$2^n$$ 个。另一方面,令 $${S}={x_1,x_2,\mbox{…},x_n}$$ 则其部分集合一共也有 $$2^n$$ 个。所以这两者之间应该有一个对应关係。用 $$n=3$$ 来当例子就可以看出对应:

$$\begin{array}{rcl} \varnothing & \longleftrightarrow & 000\\ \{x_3\}& \longleftrightarrow & 001\\\{x_1,x_2\}& \longleftrightarrow & 110\\ \{x_2,x_3\}& \longleftrightarrow & 011\end{array}$$

. . . . . .

应该有一个简单自然的对应” 这个不起眼的一句话,是非常多的困难组合学问题以及理论发展的根源。有些寻找对应的问题已经困扰了组合学家非常久。寻找对应的背后的哲学意义是,我们希望“看穿” 一个结构,或是我们希望看穿两个结构之间的关係。只有在找到了好的对应后,才能真正说有了真正的理解。

最后给一个简单的有趣练习,有兴趣的同学可以从这个问题体会对应原理的奥妙,也可以由此出发当作探索的专题:

1. 将 $${n}$$ 写成一些正整数的和,次序要计(即 $$3 + 2$$ 和 $$2 + 3$$ 是不同的),但是每个数要 $$\geq$$,有几种方法?
2. 将 $${n}$$ 写成一些正整数的和,次序要计,但是每个数必须是奇数,有几种方法?
3. 解释上面两者的关係!