有限数学与排列组合.docVIP

從排列組合談離散數學的教學 演講綱要 李國偉 （中央研究院數學研究所） 台北市高中教師專業成長研習 （2009年12月30日建國高中） 現行教科書如何引入排列 以「南一」、「三民」、「翰林」、「龍騰」、「康熹文化」、「全華」、「泰宇」各版為例。 現行教科書如何引入排列：一些反思 從n=3的例子直接跳到一般情形（有些提到乘法原理），沒有設計讓學生動手枚舉，因此學生缺乏對於實例數量暴增的感性認知。 （沒有感性的認知，抽象思維會空洞化） 用填空格的模式說明，利用可能情形數量的連乘，能夠得到總數的答案，但是缺乏羅列所有物件的有條理方法。 （先有物才有數，應注意物件的枚舉） 基本上都忽視n=1與n=2的情形（只有一本書有n=2的例子） （應重視歸納法的基本步驟） 約半數沒有充分使用樹狀圖協助思考。 新符號的引入是為了用比較精簡的方式，代表已知的事實。例如不宜在舉實例前引入連乘積符號。 以「排列、組合」培養離散數學的思維方式： 1、具體例證先於符號表徵。 2、有條理的分類整理重於空洞的原理與公式記憶。 3、重用樹狀圖協助分析狀況。 4、嘗試以演算法的精神建構物件的枚舉。 5、歸納是演算法的基礎，歸納要從最簡單的情形開始。 有限數學 新版普通高級中學課程綱要，「數學II」的總標題是「有限數學」。內容包括： 1、數列與級數 2、排列、組合 3、機率 4、數據分析 因為「數學II」處理的對象都限制在有限集合，所以用「有限數學」暫時做為統稱。「有限數學」的基礎部分「排列、組合」，在當代數學的領域裡，屬於所謂的「離散數學」（discrete mathematics），也稱為「組合數學」（combinatorics）。 「連續」的數學處理像是幾何或實數上的多項式等類問題，「離散」的數學處理有限的集合，或者集合裡元素之間有明顯區分的問題。離散數學處理的集合，經常要把元素做成有規則的構型，所以也叫做組合數學。 離散數學的主要分支 1. 古典組合學 2. 圖論（graph）與超圖（hypergraph） 3. 組合設計（design）與有限幾何（finite geometry） 4. 編碼（coding）與密碼（cryptography） 5. 組合優化（combinatorial optimization） 6. 演算法（algorithm）與計算複雜度（computational complexity） 離散數學是20世紀中葉興起的數學新生分支，做為資訊科學的基礎數學，它的重要性與影響力在21世紀將日漸明顯。 離散數學在社會科學、生命科學方面都有重要的應用。 新課綱「數列與級數」 一、數列與級數 1.數列 1.1發現數列的規律性 1.2數學歸納法 1.1只談實數數列、不含二階遞迴關係 1.2不等式型式的數學歸納法置於數學甲/乙I數列與極限中討論 2.級數 2.1介紹Σ符號及其基本操作 數學歸納法 數學歸納法盲點 錯例1：試證 1 + 2 + 3 … + n = n(n + 1)/2 + 1。 錯證：假設 n = k 時等式成立，即 1 + 2 + 3 … + k = k(k + 1)/2 + 1 ， 則當 n = k + 1 時， 1 + 2 + 3 … + k + (k + 1) = k(k + 1)/2 + 1 + (k + 1) = (k + 1)(k + 2)/2 + 1 。 即 n = k + 1 時等式成立。 錯例2：試證 「任何 n 個人都同高」。 錯證：當 n = 1 時，命題變為「任何一個人都同高」，結論顯然成立。 假設 n = k 時命題成立，即「任何 k 個人都同高」，那麼當 n = k + 1 時，將 k + 1個人記為 A1, A2, … , Ak, Ak+1，由歸納法假設可知A1, A2, … , Ak 都同高，而A2, … , Ak, Ak+1 也都同高，故 A1, A2, … , Ak, Ak+1 都同高。 數學歸納法讓學生最感困惑的地方，可能是結論先由何而來。如果不知道答案時還能歸納嗎？ 最好能有建構性證明來輔助數學歸納法。（以若干圖示法為例） 新課綱「排列、組合」 二、排列、組合 1.邏輯、集合與計數原理 1.1簡單的邏輯概念：介紹「或」、「且」、「否定」及笛摩根定律 1.2集合的定義、集合的表示法與操作 1.3基本計數原理（含窮舉法、樹狀圖、一一對應原理） 1.4加法原理、乘法原理、取捨原理 2.排列與組合 2.1直線排列、重複排列 2.2組合、重複組合 2.1不含環狀排列 本章節要避免情境不合常理、過深、或同時涉及太多觀念的題型 3.二項式定理 3.1以組合概念導出二項式定理、巴斯卡三角形 3.1不含超過二項的展開式 新課綱比現行課綱內容減少，但是由高二下學期提前到高一下學期學習。 現行