關(guān)于兩個(gè)組合恒等式的雙射證明

陶禹辰

摘 要： 本文首先總結(jié)歸納了高中階段數(shù)學(xué)學(xué)習(xí)的排列數(shù)與組合數(shù)，并以雙射證明的角度詮釋了兩個(gè)組合恒等式.

關(guān)鍵詞： 雙射證明 排列數(shù) 組合數(shù)

一、引言

計(jì)數(shù)組合學(xué)是計(jì)算有限集合S中元素個(gè)數(shù)的學(xué)科.既然任何數(shù)學(xué)問題本質(zhì)上都可以歸結(jié)為計(jì)數(shù)問題，那么上述定義本身并未包含很多該學(xué)科的信息.對(duì)于真正的計(jì)數(shù)問題中的元素通常具有相當(dāng)簡單的組合學(xué)定義，而且?guī)缀鯖]有什么附加條件.S往往很大，我們考慮的基本問題是計(jì)數(shù)（或估計(jì)）S的元素的個(gè)數(shù)，而非其他問題，如尋找某個(gè)特殊元素.

二、乘法原理與加法原理

加法原理：設(shè)事件A有m種產(chǎn)生方式，事件B有n種處理方式，當(dāng)A與B產(chǎn)生的方式不重疊時(shí)，“事件A或B”有m+n種產(chǎn)生方式。

乘法原理：設(shè)事件A有m種產(chǎn)生方式，事件B有n種處理方式，當(dāng)A與B相互獨(dú)立時(shí)，“事件A與B”有mn種產(chǎn)生方式。

三、定義與兩個(gè)組合恒等式

定義1：設(shè)S是n個(gè)元素的集合，從S中有序地選出r個(gè)元素組成的組合結(jié)構(gòu)稱為一個(gè)r-排列，全部r-排列個(gè)數(shù)記作P（n，r）；特別地，當(dāng)n=r時(shí)，選出的元素組成集合S的一個(gè)全排列，總數(shù)記作P（n，n）.

下面我們用乘法原理計(jì)算P（n，r）.

在選出的r-排列中第一個(gè)位置共有n種可能；第二個(gè)位置只能從剩下的n-1個(gè)元素中選一個(gè)放置，從而有n-1種可能；第三個(gè)位置只有n-2種可能；依次類推，最后一個(gè)位置只有n-r+1種可能，由乘法原理可知，P（n，r）=n（n-1）（n-2）…（n-r+1）.

進(jìn)而可算出，當(dāng)n=r時(shí)，S的全排列個(gè)數(shù)為P（n，n）=n！.

定義2：設(shè)S是n個(gè)元素的集合，從S中無序地選出r個(gè)元素組成的組合結(jié)構(gòu)稱為r-組合，全部r-組合的個(gè)數(shù)記作C（n，r）.

下面我們用雙射證明方法計(jì)算C（n，r）.

所謂雙射證明，也可稱為組合證明，就是為了證明某個(gè)集合S的元素個(gè)數(shù)為m而構(gòu)造S與另一個(gè)我們已知有m個(gè)元素的集合之間的一一對(duì)應(yīng)。

我們用兩種方法計(jì)數(shù)相同的組合結(jié)構(gòu)：集合S的r-排列。

方法一：直接從集合S中有序地選出r個(gè)元素，顯然得到的是集合S的r-排列，個(gè)數(shù)為P（n，r）=n（n-1）（n-2）…（n-r+1）.

四、結(jié)語

在組合數(shù)學(xué)中，組合恒等式非常多，有一些組合恒等式不僅可以用定義去證明，還可以應(yīng)用如生成函數(shù)、數(shù)學(xué)歸納法等方法進(jìn)行證明，它們的組合證明是很清楚的，但是存在大量組合恒等式還沒有找到組合證明的方法，有待我們進(jìn)一步探索和研究.

參考文獻(xiàn)：

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

[2]曲婉玲，耿素云，張立昂.離散數(shù)學(xué)[M].高等教育出版社，2008（第一版）.

[3]盧開澄，盧華明.組合數(shù)學(xué)[M].清華大學(xué)出版社，2002（第三版）.