从一个排列组问题看.docVIP

從一個排列組合問題看 張家齊 國立台灣師範大學附屬高級中學 1007班42號 序言: 升高三的暑假,曾經有位班上的同學,在午休時拿了以下的問題來問我 是一題課本上的問題,題目是這樣的: 把五件東西分給三個人,每人至少得一個 (1)東西相同,有幾種分法?(2)東西不同,有幾種分法? 我當時使用數對(1,2,3,4,5),在1,2,3,4,5處填入1,2,3代表某東西分給某人,然後進行分類討論,回了答他的問題,以下是我的做法的一些整理 映射與函數 一開始的想法是,我們可以將人所成的集合{1,2,3}和物所成的集合{1,2,3,4,5}做一個映射,一種映射表示一種對應方式,所以,或許可以用一種映射表示一種分法??現在出現一個問題,我們是應該將人集合映射到物集合,還是將物集合映射到人集合呢??以下讓我們回憶一下國中學過的函數的概念: 不是函數 是函數 () () 相信大家多多少少都有看過這樣的試題,國中時應該也學過函數的定義 函數就是:一個x不可以對到兩個y的一種映射 也就是說,可以寫成y=f(x)形式的映射f我們就把他稱之為函數 好了,言歸正傳,回到原始的問題,我們先選一種分法來看看: 將物1給人1,物2給人2,物3給人1,物4給人3,物5給人2 根據以上這種分法,我們可以定義出兩個映射m:人集合{1,2,3}-物集合{1,2,3,4,5} 以及 n:物集合{1,2,3,4,5}-人集合{1,2,3} m:人--物 n:物--人 不是函數 是函數 根據函數的定義劃出圖形,我們發現只有其中一種映射是函數,而另一種不是;再找幾個例子,會發現,只有物--人方向的映射才會是函數,往後我們再分析問題時,會先找是函數方向的映射,在進行分類討論;因為函數的單值化定義(well-defined)會使的一些工作方便進行,以下我們將會一一介紹 函數的表示法 定義: 函數的表示法是一個我再解釋給同學聽時無意間想到的一種方法,讓我們看看上面的例子,順便介紹這種表示法; 上面的 m:人-物 用數學的寫法是 上面的 n:物-人 用數學的寫法是 我的想法就是,用一個有序對來紀錄這個映射,比方說用上面的對應方式 ; 我們可以用(1,2,1,3,2)來紀錄映射n ; 然而映射m呢,因為它不是單值函數,所以無法只使用一個有序對來紀錄,可能要用(1,2,4),(3,2,4),(3,5,4)…等等才能紀錄完全;再看看一個例子,如同上面所呈現的(不是函數)和(是函數)的圖形,當我們將寫成y=f(x)形式時,可表示成唯一的形式而如果是則需要和才足夠描述這個y,就跟上述的,需要很多個數對才能描述其中一種映射有異曲同工之妙 其實函數的表示法就是這樣的一個想法了,利用有序數對的來紀錄函數 定義: 假設函數其對應方式為(既…)我們取裡的元素稱之為函數的表示法 例如: (1,2,1,3,2)就是函數ｎ的表示法 依照這樣的定義,我們可以得到以下的定理: 對每一個的函數,我們都可以在裡找到一個元素a,使得a是f的表示法 當然一定要是函數才有這樣的性質,普通的映射不一定會有 因此,我們可以發現,計算函數f的個數,其實就是在計算裡元素的個數;如果把題目中每人至少得一個的條件拿掉的話,其實,個數就是====15,是一個高中常見的計數模型,在高中的題目裡很多地方都會看到,顯示它應該是個艇重要的概念 (註:集合的乘積:,裡面的元素稱之為有序對(a,b)請參閱參考資料[1][2][3]) 從集合劃分與等價類看加法原理和乘法原理 定義:為S集合的劃分:(1) (2) 用白話一點說嘛,就是把一個集合S分成許多彼此不相交的部分,而那些部分連及起來會是原本的S;這個概念在高中的數學裡也有,加法原理就是從這裡來的,讓我們回憶一下加法原理: 這是每個課本都會題的一個定理,也是一種蠻常見的計數模型,相信大家再課本或課堂上都聽過一些關於加法原理的證明,我這裡就不再證明了 接下來我想利用加法原理,和集合劃分的概念,來證明乘法原理: 乘法原理: (其中我們先假設,) proof:由前面的註,我們知道,同樣的我們先找到他的幾個不相交的子集合 ……. 我們可以很容易發現: 以及 所以我們所構照的那f個子集合是集合的劃分,根據加法原理我們有: 接下來我們會發現, ==…== (比較嚴格的說法是,我們可以構造出用我們可以很容易證明它是1-1且onto 的,所以我們可以說=,詳情請參閱參考資料[1][2][3][