《組合數(shù)學(xué)》教案 1章(排列組合基礎(chǔ))1

《《組合數(shù)學(xué)》教案 1章(排列組合基礎(chǔ))1》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)第1章組合數(shù)學(xué)基礎(chǔ)1.排列組合的基本計數(shù)問題2.多項式系數(shù)的計算及其組合意義3.排列組合算法1.1緒論（一）背景起源：數(shù)學(xué)游戲幻方問題：給定自然數(shù)，將其排列成n階方陣，要求每行、每列和每條對角線上n個數(shù)字之和都相等。這樣的n階方陣稱為n階幻方。每一行（或列、或?qū)蔷€）之和稱為幻方的和（簡稱幻和）。例：3階幻方，幻和＝(1＋2＋3＋…＋9)/3＝15。關(guān)心的問題存在性問題：即n階幻方是否存在？計數(shù)問題：如果存在，對某個確定的n，這樣的幻方有多少種？構(gòu)造問題：即枚舉問題，亦即如何構(gòu)造n階幻方。816357492奇數(shù)階幻方的

2、生成方法：一坐上行正中央，依次斜填切莫忘，上邊出格往下填，右邊出格往左填，右上有數(shù)往下填，右上出格往下填。例：將2，4，6，8，10，12，14，16，18填入下列幻方：46/46姜建國《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)【例1.1.1】（拉丁方）36名軍官問題：有1，2，3，4，5，6共六個團隊，從每個團隊中分別選出具有A、B、C、D、E、F六種軍銜的軍官各一名，共36名軍官。問能否把這些軍官排成6×6的方陣，使每行及每列的6名軍官均來自不同的團隊且具有不同軍銜？本問題的答案是否定的。A1B2C3D4E5F6A1B2C3D4E5F6B2C3D4E5F6

3、A1B3C4D5E6F1A2C3D4E5F6A1B2C5D6E1F2A3B4D4E5F6A1B2C3D2E3F4A5B6C1E5F6A1B2C3D4E4F5A6B1C2D3F6A1B2C3D4E5F6【例1.1.2】（計數(shù)——圖形染色）用3種顏色紅（r）、黃（y）、藍（b）涂染平面正方形的四個頂點，若某種染色方案在正方形旋轉(zhuǎn)某個角度后，與另一個方案重合，則認為這兩個方案是相同的。求本質(zhì)上不同的染色方案。舉例：ryybbbrb（a）（b）46/46姜建國《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)形式總數(shù)：＝81種。實際總數(shù)（見第6章）：L＝＝24【例1.1.3】

4、（存在性）不同身高的26個人隨意排成一行，那么，總能從中挑出6個人，讓其出列后，他們的身高必然是由低到高或由高到低排列的（見第5章）。注意：不改變原來的相對順序。（一）研究內(nèi)容算法分類：l第一類：數(shù)值算法。主要解決數(shù)值計算問題，如方程求根、解方程組、求積分等，其數(shù)學(xué)基礎(chǔ)是《高等數(shù)學(xué)》與《線性代數(shù)》（解決建模問題，《數(shù)值分析》或稱《計算方法》解決離散化問題，即在計算機上的求解方法問題）。l第二類：組合算法。解決搜索、排序、組合優(yōu)化等問題，其數(shù)學(xué)基礎(chǔ)為《組合數(shù)學(xué)》。按所研究問題的類型，研究內(nèi)容：l組合計數(shù)理論l組合設(shè)計l組合矩陣論l組合優(yōu)化本課程重點：

5、以組合計數(shù)理論為主，部分涉及其它內(nèi)容。（二）研究方法分類：第一類：從組合學(xué)基本概念、基本原理出發(fā)解題的所謂常規(guī)方法（利用容斥原理、二項式定理、Pólya定理解計數(shù)問題；解遞推關(guān)系的特征根方法、母函數(shù)方法；解存在性問題的抽屜原理等）。第二類：通常與問題所涉及的組合學(xué)概念無關(guān)，而對多種問題均可使用。例如：（1）數(shù)學(xué)歸納法：前提是已知問題的結(jié)果。（2）迭代法【例】已知數(shù)列滿足關(guān)系，求46/46姜建國《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)的解析表達式。（解）直接迭代即得：＝＋1＝＝＝＝＝（1）一一對應(yīng)技術(shù)原理：建立兩類事物之間的一一對應(yīng)關(guān)系，把一個較復(fù)雜的組合計數(shù)

6、問題A轉(zhuǎn)化成另一個容易計數(shù)的問題B，從而利用對B的計數(shù)運算達到對A的各種不同方案的計數(shù)。思路：將未解決問題的模式轉(zhuǎn)化為一種已經(jīng)解決的問題模式。（2）殊途同歸方法原理：從不同角度討論計數(shù)問題，以建立組合等式。應(yīng)用：組合恒等式的證明（也稱組合意義法）。（3）數(shù)論方法特別是利用整數(shù)的奇偶性、整除性等數(shù)論性質(zhì)進行分析推理的方法。組合數(shù)學(xué)用的較多的方法：（3）與（4）?！纠?.1.4】有100名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問要產(chǎn)生冠軍共需要進行多少場比賽？（解）常規(guī)思路：50＋25＋12＋6＋3＋2＋1＝99場10000名選手：5000＋250

7、0＋1250＋625＋312＋…＋1采用一一對應(yīng)方法：每場比賽產(chǎn)生一個失敗者，且每個失敗者只能失敗一次（場次→失敗者）。反之，要淘汰一個選手，必須恰好經(jīng)過一場比賽（失敗者→場次）。結(jié)論：失敗者比賽場次。應(yīng)該比賽99場。一般情況：單循環(huán)淘汰制，n個選手，比賽場?！纠?.1.5】設(shè)某地的街道將城市分割成矩形方格，某人在其住處的向東7個街道、向北5個街道的大廈46/46姜建國《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)處工作（見圖1.1.3），按照最短路徑（即只能向東或向北走），他每次上班必須經(jīng)過某12個街段，問共有多少種不同的上班路線？（解）（1）將街道抽象為等長的

8、。（2）對應(yīng)為（元素可重復(fù)的）排列問題：路徑（藍色）→排列ｘｙｙｘｘｙｙｘｘｘｘｙ排列ｙｘｘｙｙｙｙｘｘｘｘｘ→路徑（紅色