【正文】 列： 推導(dǎo)：反復(fù)利用加法法則與乘法法則（2）組合： 推導(dǎo)：利用組合與排列的異同（3）例：n＝5，r＝3，即元素為1，2，3，4，5 排列：134，143，314，341，413，431；254，425，……組合：134，245，……（4）特點(diǎn)：排列考慮順序，組合不然?！尽拷o程序模塊命名，需要用3個字符，其中首字符要求用字母A～G或U～Z，后兩個要求用數(shù)字1~9，問最多可以給多少種程序命名？（解）首字符選法：7＋6＝13種（加法法則）。（3）變量X——男生（18種取值），變量Y——女生（12種取值）。（2）設(shè)集合：A——男生，B——女生。（二） 應(yīng)用【】仍設(shè)某班有男生18人，女生12人，現(xiàn)要求從中分別選出男女生各一名代表全班參加比賽，問共有多少種選法？（解）（1）分兩步挑選，先選女生（12種選法），再選男生（18種選法）。那么，共有個元素。l 集合描述：設(shè)有限集合A有m個元素，B有n個元素，且A與B不相交，記為一有序?qū)?。則完成該件事情共有m其中英文字母共有26個，數(shù)字0～9共10個。事件“A或B”——選男生或女生，由加法法則，有18＋12＝30種可能。該班中的學(xué)生要么屬于A，要么屬于B，且AB＝，故＝18＋12＝30。由加法法則，有18＋12＝30選法。當(dāng)然A與B各自所含的基本事件是互相不同的。l 集合描述：設(shè)有限集合A有m個元素，B有n個元素，且A與B不相交，則A與B的并共有m＋n個元素。只要選擇任何方案中的某一種方法，就可以完成這件事情，并且這些方法兩兩互不相同。【】設(shè)某地的街道將城市分割成矩形方格，某人在其住處的向東7個街道、向北5個街道的大廈處工作（），按照最短路徑（即只能向東或向北走），他每次上班必須經(jīng)過某12個街段，問共有多少種不同的上班路線？（解）（1）將街道抽象為等長的。應(yīng)該比賽99場。反之，要淘汰一個選手，必須恰好經(jīng)過一場比賽（失敗者→場次）。組合數(shù)學(xué)用的較多的方法：（3）與（4）。應(yīng)用：組合恒等式的證明（也稱組合意義法）。思路：將未解決問題的模式轉(zhuǎn)化為一種已經(jīng)解決的問題模式。（2） 迭代法【例】已知數(shù)列滿足關(guān)系，求的解析表達(dá)式。第二類：通常與問題所涉及的組合學(xué)概念無關(guān)，而對多種問題均可使用。（三） 研究方法分類：第一類：從組合學(xué)基本概念、基本原理出發(fā)解題的所謂常規(guī)方法（利用容斥原理、二項(xiàng)式定理、P243。解決搜索、排序、組合優(yōu)化等問題，其數(shù)學(xué)基礎(chǔ)為《組合數(shù)學(xué)》。主要解決數(shù)值計(jì)算問題，如方程求根、解方程組、求積分等，其數(shù)學(xué)基礎(chǔ)是《高等數(shù)學(xué)》與《線性代數(shù)》（解決建模問題，《數(shù)值分析》或稱《計(jì)算方法》解決離散化問題，即在計(jì)算機(jī)上的求解方法問題）。注意：不改變原來的相對順序。舉例：ryybbbrb（a）（b）58/58 姜建國形式總數(shù)：＝81種。A1 B2 C3 D4 E5 F6 A1 B2 C3 D4 E5 F6B2 C3 D4 E5 F6 A1 B3 C4 D5 E6 F1 A2C3 D4 E5 F6 A1 B2 C5 D6 E1 F2 A3 B4D4 E5 F6 A1 B2 C3 D2 E3 F4 A5 B6 C1E5 F6 A1 B2 C3 D4 E4 F5 A6 B1 C2 D3F6 A1 B2 C3 D4 E5 F6【】（計(jì)數(shù)——圖形染色）用3種顏色紅（r）、黃（y）、藍(lán)（b）涂染平面正方形的四個頂點(diǎn)，若某種染色方案在正方形旋轉(zhuǎn)某個角度后，與另一個方案重合，則認(rèn)為這兩個方案是相同的。例：將2，4，6，8，10，12，14，16，18填入下列幻方：【】（拉丁方）36名軍官問題：有1，2，3，4，5，6共六個團(tuán)隊(duì)，從每個團(tuán)隊(duì)中分別選出具有A、B、C、D、E、F六種軍銜的軍官各一名，共36名軍官。關(guān)心的問題 （1） 存在性問題：即n階幻方是否存在？ （2） 計(jì)數(shù)問題：如果存在，對某個確定的n，這樣的幻方有多少種？ （3） 構(gòu)造問題：即枚舉問題，亦即如何構(gòu)造n階幻方。每一行（或列、或?qū)蔷€）之和稱為幻方的和（簡稱幻和）?！督M合數(shù)學(xué)》 第一章 組合數(shù)學(xué)基礎(chǔ)第1章 組合數(shù)學(xué)基礎(chǔ)1. 排列組合的基本計(jì)數(shù)問題2. 多項(xiàng)式系數(shù)的計(jì)算及其組合意義3. 排列組合算法 緒 論（一） 背景起源：數(shù)學(xué)游戲幻方問題：給定自然數(shù)1, 2, …, n2，將其排列成n階方陣，要求每行、每列和每條對角線上n個數(shù)字之和都相等。這樣的n階方陣稱為n階幻方。例：3階幻方，幻和＝(1＋2＋3＋…＋9)/3＝15。816276357951492438奇數(shù)階幻方的生成方法：一坐上行正中央，依次斜填切莫忘，上邊出格往下填，右邊出格往左填，右上有數(shù)往下填，右上出格往下填。問能否把這些軍官排成66的方陣，使每行及每列的6名軍官均來自不同的團(tuán)隊(duì)且具有不同軍銜？本問題的答案是否定的。求本質(zhì)上不同的染色方案。實(shí)際總數(shù)（見第6章）：L＝＝24【】（存在性）不同身高的26個人隨意排成一行，那么，總能從中挑出6個人，讓其出列后，他們的身高必然是由低到高或由高到低排列的（見第5章）。（二） 研究內(nèi)容算法分類：l 第一類：數(shù)值算法。l 第二類：組合算法。按所研究問題的類型，研究內(nèi)容：l 組合計(jì)數(shù)理論l 組合設(shè)計(jì)l 組合矩陣論l 組合優(yōu)化本課程重點(diǎn)：以組合計(jì)數(shù)理論為主，部分涉及其它內(nèi)容。lya 定理解計(jì)數(shù)問題；解遞推關(guān)系的特征根方法、母函數(shù)方法；解存在性問題的抽屜原理等）。例如：（1） 數(shù)學(xué)歸納法：前提是已知問題的結(jié)果。（解）直接迭代即得：＝＋1＝＝＝＝＝（3） 一一對應(yīng)技術(shù)原理：建立兩類事物之間的一一對應(yīng)關(guān)系，把一個較復(fù)雜的組合計(jì)數(shù)問題A轉(zhuǎn)化成另一個容易計(jì)數(shù)的問題B，從而利用對B的計(jì)數(shù)運(yùn)算達(dá)到對A的各種不同方案的計(jì)數(shù)。（4） 殊途同歸方法原理：從不同角度討論計(jì)數(shù)問題，以建立組合等式。（5） 數(shù)論方法特別是利用整數(shù)的奇偶性、整除性等數(shù)論性質(zhì)進(jìn)行分析推理的方法?！尽坑?00名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問要產(chǎn)生冠軍共需要進(jìn)行多少場比賽？（解）常規(guī)思路：50＋25＋12＋6＋3＋2＋1＝99場10000名選手：5000＋2500＋1250＋625＋312＋…＋1采用一一對應(yīng)方法：每場比賽產(chǎn)生一個失敗者，且每個失敗者只能失敗一次（場次→失敗者）。結(jié)論：失敗者比賽場次。一般情況：單循環(huán)淘汰制，n個選手，比賽n－1場。 （2）對應(yīng)為（元素可重復(fù)的）排列問題：路徑（藍(lán)色）→ 排列ｘｙｙｘｘｙｙｘｘｘｘｙ排列ｙｘｘｙｙｙｙｘｘｘｘｘ → 路徑（紅色）結(jié)論：最短路徑7個x和5個y的排列（3）求解：再對應(yīng)為（元素不重復(fù)的）排列問題＝＝＝792（4）一般情形：從（0，0）點(diǎn)到達(dá)（m，n）點(diǎn)的不同的最短路徑數(shù)為 兩個基本法則1. 2. 1 加法法則（一） 加法法則l 常規(guī)描述：如果完成一件事情有兩個方案，而第一個方案有m種方法，第二個方案有n種方法可以實(shí)現(xiàn)。則完成這件事情共有m＋n種方法。l 概率角度描述：設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則事件“A或B”有m＋n種產(chǎn)生方式。（二） 應(yīng)用【】某班又男生18人，女生12人，從中選出一名代表參加會議，問共有多少種選法？（解）（1）兩個選擇方案：男生（18種選法）或女生（12種選法）。（2）設(shè)集合：A——男生，B——女生。（3）事件A——選男生（18種可能），事件B——選女生（12種可能）?！尽坑靡粋€小寫英文字母或一個阿拉伯?dāng)?shù)字給一批機(jī)器編號，問總共可能編出多少種號碼？（解）26＋10＝36個。1. 2. 2 乘法法則（一） 乘法法則l 常規(guī)描述：如果完成一件事情需要兩個步驟，而第一步有m種方法、第二步有n種方法去實(shí)現(xiàn)。n種方法。所有有序?qū)?gòu)成的集合稱為A和B的積集（或笛卡兒乘積），記作。l 概率角度描述：設(shè)離散型隨機(jī)變量X有m個取值，Y有n個取值，則離散型隨機(jī)向量（X，Y）有種可能的取值。由乘法法則，有1218＝216種選法。由乘法法則，AB＝1812＝216。由乘法法則，隨機(jī)向量（X，Y）有1812＝216種可能的值?？倲?shù)： 1399＝1053種（數(shù)字可重復(fù)使用）（乘法法則）。（二） 數(shù)學(xué)模型（1）排列問題：將r個有區(qū)別的球放入n個不同的盒子，每盒不超過一個，則總的放法數(shù)為P(n，r)。對應(yīng)關(guān)系元素盒子位置球元素和位置編號12345A B C排列1ABC1 3 4排列2CBA4 3 1排列3ACB1 4 3排列4ACB2 5 4排列5BAC4 2 5組合1●●●1 3 4組合2●●●2 4 51. 3. 2 相異元素允許重復(fù)的排列（一） 問題從n個不同元素中允許重復(fù)地選r個元素的排列，簡稱r元重復(fù)排列，排列數(shù)記為RP(∞，r)。對應(yīng)關(guān)系元素盒子位置球元素和位置編號12345A B C排列1ABC1 1 4排列2C BA4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4 2 5（三） 計(jì)算公式RP(∞，r)＝（四） 集合描述方式設(shè)無窮集合，從S中取r個元素的排列數(shù)即為RP(∞，r)。1. 3. 3 不盡相異元素的全排列（一） 問題有限重復(fù)排列（或部分排列）：設(shè)（），從S中任取r個元素，求其排列數(shù)RP(n，r)。例： S＝{22，14，2