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

本文格式為Word版，下載可任意編輯——《組合數(shù)學(xué)》教案1章（排列組合基礎(chǔ)）《組合數(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階幻方。

834159672294753618圖1.1.13階幻方

奇數(shù)階幻方的生成方法：

一坐上行正中央，依次斜填切莫忘，上邊出格往下填，右邊出格往左填，

1/62

《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)

右上有數(shù)往下填，右上出格往下填。

例：將2，4，6，8，10，12，14，16，18填入以下幻方：

（拉丁方）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ì)且具有不同軍銜？

本問題的答案是否定的。

A1B2C3D4E5F6A1B2C3D4E5F6B2C3D4E5F6A1B3C4D5E6F1A2C3D4E5F6A1B2C5D6E1F2A3B4D4E5F6A1B2C3D2E3F4A5B6C1E5F6A1B2C3D4E4F5A6B1C2D3F6A1B2C3D4E5F6

（計(jì)數(shù)——圖形染色）用3種顏色紅（r）、黃（y）、藍(lán)（b）涂染平面正方形的四個(gè)頂點(diǎn)，若某種染色方案在正方形旋轉(zhuǎn)某個(gè)角度后，與另一個(gè)方案重合，則認(rèn)為這兩個(gè)方案是一致的。求本質(zhì)上不同的染色方案。

舉例：

ry

ybbb（a）rb（b）2/62

《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)

形式總數(shù)：34＝81種。實(shí)際總數(shù)（見第6章）：

L＝

14?342?3?2?3＝24

?（存在性）不同身高的26個(gè)人隨意排成一行，那么，總能從中挑出6個(gè)人，讓其出列后，他們的身高必然是由低到高或由高到低排列的（見第5章）。

注意：不改變?cè)瓉淼南鄬?duì)順序。（二）研究?jī)?nèi)容算法分類：

?第一類：數(shù)值算法。主要解決數(shù)值計(jì)算問題，如方程求根、解方程組、求積分等，其數(shù)學(xué)基礎(chǔ)是《高等數(shù)學(xué)》與《線性代數(shù)》（解決建模問題，《數(shù)值分析》或稱《計(jì)算方法》解決離散化問題，即在計(jì)算機(jī)上的求解方法問題）。?其次類：組合算法。解決探尋、排序、組合優(yōu)化等問題，其數(shù)學(xué)基礎(chǔ)就是《組合數(shù)學(xué)》。按所研究問題的類型，研究?jī)?nèi)容：?組合計(jì)數(shù)理論?組合設(shè)計(jì)?組合矩陣論?組合優(yōu)化

本課程重點(diǎn)：以組合計(jì)數(shù)理論為主，部分涉及其它內(nèi)容。（三）研究方法

分類：

第一類：從組合學(xué)基本概念、基本原理出發(fā)解題的所謂常規(guī)方法（利用容斥原理、二項(xiàng)式定理、Pólya定理解計(jì)數(shù)問題；解遞推關(guān)系的特征根方法、母函數(shù)方法；解存在性問題的抽屜原理

3/62

《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)

等）。

其次類：尋常與問題所涉及的組合學(xué)概念無關(guān)，而對(duì)多種問題均可使用。例如：

（1）數(shù)學(xué)歸納法：前提是已知問題的結(jié)果。（2）迭代法

?hn?2hn?1?1,如已知數(shù)列?hn?滿足關(guān)系?，求hn的解析

?h1?1表達(dá)式。

（解）直接迭代即得：

hn?2hn?1?1

＝2?2hn?2?1?＋1＝22hn?2?2?1

＝22?2hn?3?1??2?1＝23hn?3?22?2?1

?

＝2n?1h1?2n?2?2n?3???22?2?1＝2n?1

（3）一一對(duì)應(yīng)技術(shù)

原理：建立兩類事物之間的一一對(duì)應(yīng)關(guān)系，把一個(gè)較繁雜的組合計(jì)數(shù)問題A轉(zhuǎn)化成另一個(gè)簡(jiǎn)單計(jì)數(shù)的問題B，從而利用對(duì)B的計(jì)數(shù)運(yùn)算達(dá)到對(duì)A的各種不同方案的計(jì)數(shù)。

思路：將未解決問題的模式轉(zhuǎn)化為一種已經(jīng)解決的問題模式。（4）殊途同歸方法

原理：從不同角度探討計(jì)數(shù)問題，以建立組合等式。應(yīng)用：組合恒等式的證明（也稱組合意義法）。（5）數(shù)論方法

4/62

《組合數(shù)學(xué)》第一章組合數(shù)學(xué)基礎(chǔ)

特別是利用整數(shù)的奇偶性、整除性等數(shù)論性質(zhì)進(jìn)行分析推理的方法。

組合數(shù)學(xué)用的較多的是方法（3）與（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è)選手，必需恰好經(jīng)過一場(chǎng)比賽。

結(jié)論：失敗者與比賽場(chǎng)次之間一一對(duì)應(yīng)，故應(yīng)當(dāng)比賽99場(chǎng)。一般狀況：?jiǎn)窝h(huán)淘汰制的比賽，若有n個(gè)選手參考比賽，則須經(jīng)過n－1場(chǎng)比賽，方可產(chǎn)生冠軍。

設(shè)某地的街道將城市分割成矩形方格，某人在其住處A(0，0)的向東7個(gè)街道、向北5個(gè)街道的大廈B(7，5)處工作（見圖1.1.3），依照最短路徑（即只能向東或向北走），他每次上班必需經(jīng)過某12個(gè)街段，問共有多少種不同的上班路