【正文】 。求不同的放法數(shù)。第二步：將余下的96個(gè)1放入，有變異一：求非負(fù)整數(shù)解（即）。排列組合問(wèn)題：從4種相異元素中可重復(fù)地選100個(gè)，每種元素至少選一個(gè)。＝＝156849（組）方法Ⅱ：分配模型：將100個(gè)相同的“1”放入4個(gè)不同的盒子，每個(gè)盒子至少放一個(gè)。分配模型：將3個(gè)相同的球放入99個(gè)相異的盒子，每盒最多放一個(gè)球?！?— … — ＋ — — … — ＋— …— — —＋ — … —問(wèn)題轉(zhuǎn)化：在99個(gè)空位置上放3個(gè)“＋”號(hào)，未放“＋”號(hào)的線段合成一條線段，求放法總數(shù)。函數(shù)個(gè)數(shù) ＝40（個(gè)）【】滿足的正整數(shù)解有多少組？（解）（組合問(wèn)題）方法Ⅰ思路：長(zhǎng)度為100的線段被分為4段，每段的長(zhǎng)度均為正整數(shù)，記為?？倲?shù)： 54＋253＋52＝900 （個(gè)）【】從－2，－1，0，1，2，3共6個(gè)數(shù)中不重復(fù)地選3個(gè)數(shù)作為二次函數(shù)的系數(shù)，使得拋物線的開口方向向下，共可作出多少個(gè)二次函數(shù)？（解）（不重復(fù)排列）拋物線開口向下a＜0。例：n＝10，r＝514678 → 14679 → 1467A → 14689 → 1468A → 1469A → 14789 應(yīng)用舉例【】試確定由1，2，3，4，5這五個(gè)數(shù)字能組成多少個(gè)大于43500的五位數(shù)？（解）（有限制條件的RP(∞，5)的問(wèn)題）。（3） ，j＝i＋1, i＋2, …, r。若每個(gè)cj ＝n－r＋j，則已經(jīng)達(dá)到最后一個(gè)組合，生成完畢。 組合的生成算法【例】從6個(gè)元素1, 2, 3, 4, 5, 6中取3個(gè)的組合：123 → 124 → 125 → 126 → 134 → 135 → 136 → 145 → 146 → 156 →234 → 235 → 236 → 245 → 246 → 256 → 345 → 346 → 356 → 456規(guī)律：低位累加，逐位前移。舉例（n＝4）： 規(guī)律：4從一端移到另一端，共進(jìn)行了3次換位，然后暫停一次，3開始活動(dòng)。n＝4的全部排列：1234 → 1243 → 1324 → 1342 → 1423 → 1432 → 2134 → 2143 →2314 → 2341 → 2413 → 2431 → 3124 → 3142 → 3214 → 3241 →3412 → 3421 → 4123 → 4132 → 4213 → 4231 → 4312 → 4321說(shuō)明：第（4）步的必要性（2）85376421 i＝4，j＝6 ＝85476321 8541236785412367 i＝8，j＝8 ＝85412376 85412376 i＝7，j＝8 ＝85412673 8541263785413726 i＝8，j＝8 ＝8541376285413762 i＝6，j＝7 ＝85416732 854167231. 6. 3 鄰位互換生成算法初始排列：（當(dāng)一個(gè)數(shù)上方箭頭所指的一側(cè)相鄰的數(shù)比該數(shù)小時(shí)，稱該數(shù)處于活動(dòng)狀態(tài)）初始排列：設(shè)當(dāng)前排列為 （1） 若排列中無(wú)一數(shù)處于活動(dòng)狀態(tài)，則停止，否則轉(zhuǎn)（2）；（2） 求所有處于活動(dòng)狀態(tài)的數(shù)中的最大者，設(shè)為k，k和它的箭頭所指的一側(cè)的相鄰數(shù)互換位置，轉(zhuǎn)（3）。初始排列： 設(shè)當(dāng)前排列為（1） 求滿足關(guān)系式的k的最大值，設(shè)為i，即（2） 求滿足關(guān)系式的k的最大值，設(shè)為j，即（3） 與互換位置得（4） 中部分的元素順序逆轉(zhuǎn)，得新排列。特點(diǎn)：n元排列n－1位變進(jìn)制數(shù)。1!＝n!－1＜n!；④將十進(jìn)制換算為變進(jìn)制數(shù)方法。 （3）特點(diǎn)：① 變進(jìn)制；② 從右向左，第位逢＋1進(jìn)一；③n－1位數(shù)最小為0，最大為：(n－1)(n－1)!＋(n－2)(n－2)!＋…＋22!＝＝＝＋＋…＋＋(m－)247。2!＋12!＋1 排列的生成算法1. 6. 1 序數(shù)法（一） 數(shù)的位權(quán)表示（1）十進(jìn)制數(shù)：小于的正整數(shù)n的位權(quán)形式：n＝， 0≤≤9＜10例 315＝（r＝3）（2）推廣（p進(jìn)制數(shù)）n＝， 0≤＜p（3）特點(diǎn)：①固定進(jìn)制；②逢p進(jìn)一；③十進(jìn)制r位數(shù)最小為0，最大為999…9＝－1＜；④將十進(jìn)制換算為p進(jìn)制數(shù)方法：除p取余法。＝420【】在的展開式中，項(xiàng)的系數(shù)是什么？（解）令。＝1得＝（五） 例【】求的展開式。（證）＝（1）所有項(xiàng)都具形式，且（2）一般項(xiàng)的系數(shù)：個(gè)因式中選取，得項(xiàng)，其系數(shù)為＝＝＝稱為多項(xiàng)式系數(shù)。轉(zhuǎn)化：求（n1＋n2＋…＋nt＝n）的全排列數(shù)RP(n，n)：仿照二項(xiàng)式系數(shù)，記為。例 ＝(a＋b)(a＋b)＝aa＋ab＋ba＋bb＝＝(a＋b)(a＋b)(a＋b)＝(aa＋ab＋ba＋bb)(a＋b)＝aaa＋aab＋aba＋abb＋baa＋bab＋bba＋bbb＝產(chǎn)生系數(shù)的根源：同一單項(xiàng)式中有順序，即排列問(wèn)題（球不同的分配問(wèn)題）?？倲?shù)＝ 多項(xiàng)式系數(shù)（一） Newton二項(xiàng)式(1) 二項(xiàng)展開式Newton二項(xiàng)式定理（n是正整數(shù)）右端稱為二項(xiàng)式(a＋b)n的展開式，叫做二項(xiàng)式系數(shù)。統(tǒng)計(jì)方法一：先選正式代表，再?gòu)娜酥羞x列席代表，總的選法為。另法：第一次摸到白球概率。每次摸出一個(gè)球，不放回，直至摸到白球?yàn)橹埂＿x法2：①?gòu)膎名太太中選k人；②從此k人中選一人任主席；③再?gòu)膎名先生中選n－k人（1≤k≤n）。選法1：①選一名太太任主席；②再選n－1人。啟發(fā)：存在一一對(duì)應(yīng)關(guān)系。分類統(tǒng)計(jì)：i個(gè)紅球，r－i個(gè)藍(lán)球的選法為。舉例：n＝20＝5＋7＋8＝7＋8＋5，＝推廣：n個(gè)元素分為t堆，且可以若干堆個(gè)數(shù)相等n＝20＝4＋2＋5＋9＝2＋9＋4＋5，＝【等式4】C(n＋r＋1，r)＝ ＝C(n＋r，r)＋C(n＋r－1，r－1)＋C(n＋r－2，r－2)＋C(n＋r－3，r－3)＋…＋C(n，0) 或 C(n＋r＋1，r)＝ ＝ C(n＋r，n)＋C(n＋r－1，n)＋C(n＋r－2，n)＋…＋C(n，n)（一）組合意義：（二）說(shuō)明：等式2的推廣。（2） 右端：“將n個(gè)元素分為3堆：第三堆r個(gè)，第二堆個(gè)，第一堆個(gè)”，求組合方案數(shù)。（二）例：從{1，2，3，4，5}中取3個(gè)的組合情況：第一類（包含元素“1”）： 123，124，125，134，135，145第二類（不包含“1”）： 234，235，245，345（三）路徑問(wèn)題：等價(jià)形式組合意義：從（0，0）點(diǎn)到（m，n）點(diǎn)的路徑數(shù)等于從（0，0）點(diǎn)分別到（m，n－1）點(diǎn)和（m－1，n）點(diǎn)的路徑數(shù)之和。（2） 不含元素，組合數(shù)為。是產(chǎn)生和證明組合恒等式的普遍方法。對(duì)于恒等式的實(shí)質(zhì)揭露得更為深刻。（4）求解：構(gòu)造多項(xiàng)式P6 (x)＝(1＋x＋x2＋x3)(1＋x＋x2)(1＋x)＝1＋3x＋5x2＋6x3＋5x4＋3x5＋x6系數(shù)求和： ＝1＋3＋5＋6＋5＋3＋1＝24方法化簡(jiǎn)：求P6(1)＝＝432＝24（5）一般規(guī)律：設(shè)正整數(shù)n分解為，則習(xí)題：18，21小結(jié)：課程任務(wù)；技巧性。故14不是約數(shù)，16＝也不是約數(shù)。20＝24001. 3. 6 不盡相異元素任取r個(gè)的組合問(wèn)題（一） 問(wèn)題設(shè)集合（），從S中任取r個(gè)，求其組合數(shù)RC(n，r)。（4）總方案數(shù)： L＝5！ △△△ b △△△ d △△△ e △△△ a（3）將余下的3個(gè)空格插入4個(gè)間隔：分析：將3個(gè)相同的球放入4個(gè)不同的盒子，盒子的容量不限。（五） 應(yīng)用【】不同的5個(gè)字母通過(guò)通信線路被傳送，每?jī)蓚€(gè)相鄰字母之間至少插入3個(gè)空格，但要求空格的總數(shù)必須等于15，問(wèn)共有多少種不同的傳送方式？（解）三步求解：（1）先排列5個(gè)字母，排列數(shù) P(5，5)＝5!。例：n＝5，r＝4： 1111，1122，1345，5555（三） 計(jì)算公式設(shè)所選r個(gè)元素為：1≤a1≤a2≤…≤ar≤n令 ， i＝1，2，…，r則 1≤b1＜b 2＜…＜br≤n＋(r－1)反之 結(jié)論：與從n＋r－1個(gè)相異元素中不重復(fù)地取r個(gè)元素的組合方案一一對(duì)應(yīng)。1. 3. 5 相異元素允許重復(fù)的組合（一） 問(wèn)題設(shè)，從S中允許重復(fù)地取r個(gè)元素構(gòu)成組合，稱為r可重組合，其組合數(shù)記為RC(∞，r)。結(jié)論：兩個(gè)圓排列對(duì)應(yīng)一個(gè)項(xiàng)鏈排列，故有24/2＝12種。條件：可以翻轉(zhuǎn)的圓排列。＝(n－1)!32541 25413 54132 41325 13254【】從n個(gè)相異元素中不重復(fù)地取r個(gè)圍成圓排列，求不同的排列總數(shù)CP(n，r)。條件：元素同時(shí)按同一方向旋轉(zhuǎn)，絕對(duì)位置變化，相對(duì)位置未變，即元素間的相鄰關(guān)系未變，視為同一圓排列。5}＝{1，1，2，2，2，2，3，4，4，4，5，5}對(duì)應(yīng)關(guān)系元素盒子位置球元素和位置編號(hào)12345A B C排列1ABC1 1 4排列2B C A4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4 2 5說(shuō)明：（1）極端情形：相異元素不重復(fù)的排列強(qiáng)調(diào)的是不重復(fù)，即盒子的容量為1；（2）極端情形：相異元素允許重復(fù)的排列強(qiáng)調(diào)的是無(wú)限重復(fù)，即盒子的容量無(wú)限；（3）一般情形：不盡相異元素的排列強(qiáng)調(diào)的是有限重復(fù)，即盒子的容量有限，介于兩者之間。3，31，4（二） 模型將r個(gè)有區(qū)別的球放入t個(gè)不同的盒子，每個(gè)盒子的容量有限，其中第i個(gè)盒子最多只能放入個(gè)球，求分配方案數(shù)。不重復(fù)排列：S＝＝。（二） 模型將r個(gè)不相同的球放入n個(gè)有區(qū)別的盒子，每個(gè)盒子中的球數(shù)不加限制而且同盒的球不分次序。（2）組合問(wèn)題：將r個(gè)無(wú)區(qū)別的球放入n個(gè)不同的盒子，每盒不超過(guò)一個(gè)，則總的放法數(shù)為C(n，r)?！尽繌腁地到B地有條不同的道路，從A地到C地有條不同的道路，從B地到D地有條不同的道路，從C地到D地有條不同的道路，那么，從A地經(jīng)B或C到達(dá)目的地D共有多少種不同的走法? （解）路線ABD：種走法（乘法法則） 路線ACD：種走法（乘法法則）總數(shù)：＋種走法（加法法則）23＋34＝18 排列與組合1. 3. 1 相異元素不允許重復(fù)的排列數(shù)和組合數(shù)（一） 計(jì)算公式從n個(gè)相異元素中不重復(fù)地取r個(gè)元素的排列數(shù)和組合數(shù)：（1）排