关于两个组合恒等式的双射证明

摘 要： 本文首先总结归纳了高中阶段数学学习的排列数与组合数，并以双射证明的角度诠释了两个组合恒等式.

关键词： 双射证明 排列数 组合数

一、引言

计数组合学是计算有限集合S中元素个数的学科.既然任何数学问题本质上都可以归结为计数问题，那么上述定义本身并未包含很多该学科的信息.对于真正的计数问题中的元素通常具有相当简单的组合学定义，而且几乎没有什么附加条件.S往往很大，我们考虑的基本问题是计数（或估计）S的元素的个数，而非其他问题，如寻找某个特殊元素.

二、乘法原理与加法原理

加法原理：设事件A有m种产生方式，事件B有n种处理方式，当A与B产生的方式不重叠时，“事件A或B”有m+n种产生方式。

乘法原理：设事件A有m种产生方式，事件B有n种处理方式，当A与B相互独立时，“事件A与B”有mn种产生方式。

三、定义与两个组合恒等式

定义1：设S是n个元素的集合，从S中有序地选出r个元素组成的组合结构称为一个r-排列，全部r-排列个数记作P（n，r）；特别地，当n=r时，选出的元素组成集合S的一个全排列，总数记作P（n，n）.

下面我们用乘法原理计算P（n，r）.

在选出的r-排列中第一个位置共有n种可能；第二个位置只能从剩下的n-1个元素中选一个放置，从而有n-1种可能；第三个位置只有n-2种可能；依次类推，最后一个位置只有n-r+1种可能，由乘法原理可知，P（n，r）=n（n-1）（n-2）…（n-r+1）.

进而可算出，当n=r时，S的全排列个数为P（n，n）=n！.

定义2：设S是n个元素的集合，从S中无序地选出r个元素组成的组合结构称为r-组合，全部r-组合的个数记作C（n，r）.

下面我们用双射证明方法计算C（n，r）.

所谓双射证明，也可称为组合证明，就是为了证明某个集合S的元素个数为m而构造S与另一个我们已知有m个元素的集合之间的一一对应。

我们用两种方法计数相同的组合结构：集合S的r-排列。

方法一：直接从集合S中有序地选出r个元素，显然得到的是集合S的r-排列，个数为P（n，r）=n（n-1）（n-2）…（n-r+1）.

四、结语

在组合数学中，组合恒等式非常多，有一些组合恒等式不仅可以用定义去证明，还可以应用如生成函数、数学归纳法等方法进行证明，它们的组合证明是很清楚的，但是存在大量组合恒等式还没有找到组合证明的方法，有待我们进一步探索和研究.

参考文献：

[1]Richard Stanley.Enumerative Combinatorics（I）.Cambridge Press，1997.

[2]曲婉玲，耿素云，张立昂.离散数学[M].高等教育出版社，2008（第一版）.

[3]卢开澄，卢华明.组合数学[M].清华大学出版社，2002（第三版）.