組合數(shù)學(xué)第一章修改11ben

1、 電子科大計(jì)算機(jī)學(xué)院楊國武 Tel: ，61830580組合數(shù)學(xué)教學(xué)安排與要求學(xué)時(shí)數(shù)：32教材: 組合數(shù)學(xué)電子科技大學(xué) 孫世新內(nèi)容： 組合數(shù)學(xué)15章課后輔導(dǎo): C205答疑安排:每次課后作業(yè)： 每章結(jié)束后上交本章作業(yè)考核:平時(shí)成績:不定時(shí)點(diǎn)名，作業(yè)和到課率 20% 期中考試 10% 期末考試 70%主要參考書1. R.A.Brualdi：組合學(xué)引論（李盤林，王天明譯），華中工學(xué)院出版社，19822. 盧開澄：組合數(shù)學(xué)，清華大學(xué)出版社，19933. C.L.Liu：組合數(shù)學(xué)導(dǎo)論（魏萬迪譯），四川大學(xué)出版社，1987據(jù)說很早以前，夏禹治水時(shí)，河南洛陽附近的大河里浮出了一只烏龜，背上有一個(gè)很奇怪的圖

2、形，古人認(rèn)為是一種祥瑞，預(yù)示著洪水將被夏禹王徹底制服。后人稱之為洛書或河圖。 519372486前 言幻方可以看作是一個(gè)3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對角線的和都是15。 （斜排法）前 言其它幻方。1 2 3 4 5 6 7 8 9 10 11 1213 14 15 16 1 15 14 4 12 6 7 9 8 10 11 513 3 2 16 【對調(diào)法】前 言 賈憲， 北宋數(shù)學(xué)家（約11世紀(jì)） 著有黃帝九章細(xì)草等都已失傳。楊輝著詳解九章算法（1261年）中曾引賈憲的“開方作法本源”圖（即指數(shù)為正整數(shù)的二項(xiàng)式展開系數(shù)表，現(xiàn)稱“楊輝三角形”）和“增乘開方法”（求高次冪的正

3、根法）。前者比帕斯卡三角形早600年，后者比霍納（William Geoge Horner，17861837）的方法（1819年）早770年。 1666年萊布尼茲所著組合學(xué)論文一書問世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。 組合數(shù)學(xué)的蓬勃發(fā)展則是在計(jì)算機(jī)問世和普遍應(yīng)用之后。由于組合數(shù)學(xué)涉及面廣，內(nèi)容龐雜，并且仍在很快地發(fā)展著，因而還沒有一個(gè)統(tǒng)一而有效的理論體系。這與數(shù)學(xué)分析形成了對照。 組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。 但是，要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。前 言 第一章 排 列 、組合與二項(xiàng)式定理 1.1 加

4、法規(guī)則和乘法規(guī)則 組合數(shù)學(xué)研究的主要問題之一就是計(jì)數(shù)問題。 而加法規(guī)則和乘法規(guī)則又是解決計(jì)數(shù)問題的有力工具。這兩個(gè)規(guī)則是直觀的，形式上的驗(yàn)證可以用數(shù)學(xué)歸納法得到 加法規(guī)則 設(shè)S是有限集合，若 , 且 時(shí)， 則有：S=| | = (1.1) 特別：當(dāng)m=2時(shí)，有S=| |= | | + | |換言之，加法規(guī)則可以敘述為：若集合S可以分解為互不相交子集S1，S2，Sm之和,則 確定S中的事物個(gè)數(shù) 先求出各子集Si中的事物個(gè)數(shù) 然后相加。 加法規(guī)則用生活中的話來說: 對m=2，加法規(guī)則的另一種敘述就是假若有互相獨(dú)立的兩個(gè)事件X和Y分別有k種和l種方法產(chǎn)生，則產(chǎn)生X和Y的方法數(shù)有k+l種。加法規(guī)則 例

5、有一所學(xué)校給一名物理競賽優(yōu)勝者發(fā)獎(jiǎng)，獎(jiǎng)品有三類： 第一類是三種不同版本的法漢詞典；第二類是四種不同類型的物理參考書；第三類是兩種不同的獎(jiǎng)杯。這位優(yōu)勝者只能挑選一樣獎(jiǎng)品。那么，這位優(yōu)勝者挑選獎(jiǎng)品的方法有多少？ 答案 9種解：設(shè)S是所有這些獎(jiǎng)品的集合，Si是第i類獎(jiǎng)品的集合(i=1,2,3)。顯然SiSj=(ij)，于是由加法規(guī)則有也就是說這位優(yōu)勝者挑選獎(jiǎng)品的方法共有9種。乘法規(guī)則 若Si(i=1,2,m)為有限集，且 S=S1S2Sm=(a1,a2,am)|aiSi,i=1,2,m, 則有S=S1S2Sm= (1.2)特別，當(dāng)m=2時(shí)，有S=S1S2=S1S2 換言之，乘法規(guī)則可以敘述為：若集合

6、S是集合S1，S2，Sm的直積，則確定S中的事物個(gè)數(shù)1.先求出各個(gè)集合Si中的事物個(gè)數(shù)2.然后相乘乘法規(guī)則應(yīng)當(dāng)注意:對于S中的元(a1,a2,am)，它的各分量是相互獨(dú)立的。同樣，避開集合這個(gè)名詞，使用在實(shí)際生活中容易理解的字眼，對m=2，乘法規(guī)則可以敘述為：若有互相獨(dú)立的兩個(gè)事件X和Y分別有k種和l種方法產(chǎn)生，則同時(shí)產(chǎn)生事件X與事件Y的方法數(shù)為kl。乘法規(guī)則例 從A地到B地有兩條不同的道路，從B地到C地有四條不同的道路，而從C地到D地有三條不同的道路。求從A地經(jīng)B、C兩地到達(dá)D地的道路數(shù)。 答案 24分析:數(shù)字互不相同四位偶數(shù)例 由數(shù)字1，2，3，4，5可以構(gòu)成多少個(gè)所有數(shù)字互不相同的四位偶

7、數(shù)。例求出從7個(gè)數(shù)學(xué)系的學(xué)生，8個(gè)化學(xué)系的學(xué)生，105個(gè)經(jīng)濟(jì)系的學(xué)生和21個(gè)物理系的學(xué)生中選出兩個(gè)不同專業(yè)的學(xué)生的方法數(shù)。 484151例 某種樣式的運(yùn)動(dòng)服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有42 = 8種著色方案。 若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則，方案數(shù)就不是4 4 = 16， 而只有 4 3 = 12 種。(必須能區(qū)分條紋色) 在乘法法則中要注意事件 A 和 事件 B 的相互獨(dú)立性。由上可以總結(jié)：在實(shí)際中，大量的計(jì)數(shù)問題分為兩大類； 1.計(jì)算事物的有序安排或有序選擇數(shù)。這又分為如下兩種情況： a.不允許任何事物重復(fù) b.允許事物重復(fù) 排列2. 計(jì)算事物的無序安排或無序選擇數(shù)。這又分為如下兩種情況： a.不允許任何事物重復(fù) b.允許事物重復(fù) 組合集合：A=a,b,c,d重集：集合中的元素可以重復(fù)。 如