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

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

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

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

3、4D5E6F1A2C3D4E5F6A1B2C5D6E1F2A3B4D4E5F6A1B2C3D2E3F4A5B6C1E5F6A1B2C3D4E4F5A6B1C2D3F6A1B2C3D4E5F6【例1.1.2】（計(jì)數(shù)——圖形染色）用3種顏色紅（r）、黃（y）、藍(lán)（b）涂染平面正方形的四個(gè)頂點(diǎn)，若某種染色方案在正方形旋轉(zhuǎn)某個(gè)角度后，與另一個(gè)方案重合，則認(rèn)為這兩個(gè)方案是相同的。求本質(zhì)上不同的染色方案。舉例：ryybbbrb（a）（b）62/62《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)形式總數(shù)：＝81種。實(shí)際總數(shù)（見第6章）：L＝＝24【例1.1.3】（存在性）不同身高的26個(gè)人隨意排成一行，那么，總能從

4、中挑出6個(gè)人，讓其出列后，他們的身高必然是由低到高或由高到低排列的（見第5章）。注意：不改變?cè)瓉淼南鄬?duì)順序。（一）研究?jī)?nèi)容算法分類：l第一類：數(shù)值算法。主要解決數(shù)值計(jì)算問題，如方程求根、解方程組、求積分等，其數(shù)學(xué)基礎(chǔ)是《高等數(shù)學(xué)》與《線性代數(shù)》（解決建模問題，《數(shù)值分析》或稱《計(jì)算方法》解決離散化問題，即在計(jì)算機(jī)上的求解方法問題）。l第二類：組合算法。解決搜索、排序、組合優(yōu)化等問題，其數(shù)學(xué)基礎(chǔ)就是《組合數(shù)學(xué)》。按所研究問題的類型，研究?jī)?nèi)容：l組合計(jì)數(shù)理論l組合設(shè)計(jì)l組合矩陣論l組合優(yōu)化本課程重點(diǎn)：以組合計(jì)數(shù)理論為主，部分涉及其它內(nèi)容。（二）研究方法分類：第一類：從組合學(xué)基本概念、基本原

5、理出發(fā)解題的所謂常規(guī)方法（利用容斥原理、二項(xiàng)式定理、Pólya定理解計(jì)數(shù)問題；解遞推關(guān)系的特征根方法、母函數(shù)方法；解存在性問題的抽屜原理等）。62/62《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)第二類：通常與問題所涉及的組合學(xué)概念無關(guān)，而對(duì)多種問題均可使用。例如：（1）數(shù)學(xué)歸納法：前提是已知問題的結(jié)果。（2）迭代法【例】如已知數(shù)列滿足關(guān)系，求的解析表達(dá)式。（解）直接迭代即得：＝＋1＝＝＝＝＝（3）一一對(duì)應(yīng)技術(shù)原理：建立兩類事物之間的一一對(duì)應(yīng)關(guān)系，把一個(gè)較復(fù)雜的組合計(jì)數(shù)問題A轉(zhuǎn)化成另一個(gè)容易計(jì)數(shù)的問題B，從而利用對(duì)B的計(jì)數(shù)運(yùn)算達(dá)到對(duì)A的各種不同方案的計(jì)數(shù)。思路：將未解決問題的模式轉(zhuǎn)化為一種已經(jīng)解決的

6、問題模式。（4）殊途同歸方法原理：從不同角度討論計(jì)數(shù)問題，以建立組合等式。應(yīng)用：組合恒等式的證明（也稱組合意義法）。（5）數(shù)論方法特別是利用整數(shù)的奇偶性、整除性等數(shù)論性質(zhì)進(jìn)行分析推理的方法。62/62《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)用的較多的是方法（3）與（4）?！纠?.1.4】有100名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問要產(chǎn)生冠軍共需要進(jìn)行多少場(chǎng)比賽？（解）常規(guī)思路：50＋25＋12＋6＋3＋2＋1＝99場(chǎng)10000名選手：5000＋2500＋1250＋625＋312＋…＋1采用一一對(duì)應(yīng)方法：每場(chǎng)比賽產(chǎn)生一個(gè)失敗者，且每個(gè)失敗者只能失敗一次。反之，要淘汰一個(gè)選手，必須

7、恰好經(jīng)過一場(chǎng)比賽。結(jié)論：失敗者與比賽場(chǎng)次之間一一對(duì)應(yīng)，故應(yīng)該比賽99場(chǎng)。一般情況：?jiǎn)窝h(huán)淘汰制的比賽，若有n個(gè)選手參考比賽，則須經(jīng)過n－1場(chǎng)比賽，方可產(chǎn)生冠軍?！纠?.1.5】設(shè)某地的街道將城市分割成矩形方格，某人在其住處A(0，0)的向東7個(gè)街道、向北5個(gè)街道的大廈B(7，5)處工作（見圖1.1.3），按照最短路徑（即只能向東或向北走），他每次上班必須經(jīng)過某12個(gè)街段，問共有多少種不同的上班路線？（解）（1）將街道抽象為等長的。B(7,5)A