【文章內(nèi)容簡介】 …,299} C = {3, 6, …, 300} 分別取自 A, B, C: 各 C(100,3) A, B, C 各取 1 個（分步處理）： C(100,1)3 N= C(100,3) + 1003 = 1485100 例 1 從 1— 300中任取 3個數(shù)使得其和能被 3整除有多少種方法？ 8343 2022/7/13 基本計數(shù)公式的應(yīng)用 (續(xù) ) 解 : 1000!=1000 ?999? 998 ?… ? 2?1 將上面的每個因子分解，若分解式中共有 i 個 5, j 個 2， 那么 min(i, j)就是 0的個數(shù) . 1, …,1000 中有 500個是 2 的倍數(shù)， j 500。 200個是 5 的倍數(shù)， 40個是 25 的倍數(shù)（多加 40 個 5）， 8個是 125 的倍數(shù)（再多加 8 個 5）， 1個是 625 的倍數(shù)（再多加 1 個 5） i = 200+40+8+1 = 249. min(i, j)=249. 例 2 求 1000！的末尾有多少個 0？ 8344 2022/7/13 基本計數(shù)公式的應(yīng)用 (續(xù) ) 例 3 設(shè) A為 n 元集 ， 問 (1) A上的自反關(guān)系有多少個 ？ (2) A上的反自反關(guān)系有多少個 ？ (3) A上的對稱關(guān)系有多少個 ？ (4) A上的反對稱關(guān)系有多少個 ？ (5) A上既不對稱也不是反對稱 的關(guān)系有多少個 ？ nn ?22nn ?222222222 nnnnn ?? ?2232nnn?nnnnnnn )( 23222 22222 ??? ??8345 2022/7/13 多重集的排列 定理 多重集 S={n1?a1, n2?a2, …, nk?ak}， 0 ni ?+∞ (1) 全排列 r = n, n1 + n2 + … + nk = n 證明：分步選取 . 先放 a1, 有 C(n,n1) 種方法；再放 a2, 有 C(n? n1,n2)種方法 , ... , 放 ak,有 C(n?n1?n2? … ? nk?1,nk) 種方法 (2) 若 r ? ni 時，每個位置都有 k 種選法，得 kr. ??????????kk nnnn...nnnnN...!!!!2121!!!!!0!)!. . .(. . .)!(!)!()!(!!2111212111121211kkkkk. . . nnnnnnnnnnnnnnnnnn),nn. . .nn) . . . C ( n,nn) C ( nC ( n , nN?????????????????8346 2022/7/13 多重集的組合 定理 多重集 S={n1?a1, n2?a2, …, nk?ak}， 0ni ?+∞ 當(dāng) r ? ni , S的 r 組合數(shù)為 N = C(k+r?1,r), 證明 一個 r 組合為 {x1?a1, x2?a2, …, xk?ak}， 其中 x1 + x2 + … + xk = r , xi 為非負(fù)整數(shù) . 這個不定方程的非負(fù)整數(shù)解對應(yīng)于下述排列 1…1 0 1…1 0 1…1 0 …… 0 1…1 x1個 x2個 x3個 xk個 r 個 1， k?1個 0 的全排列數(shù)為 ),1()!1(! )!1( rrkCkr krN ???????8347 2022/7/13 實(shí)例 例 5 排列 26個字母，使得 a 與 b 之間恰有 7個字母，求方法數(shù) . 解： 設(shè)盒子的球數(shù)依次記為 x1, x2, …, xn, 則滿足 x1 + x2 + … + xn = r， x1, x2, …, xn 為非負(fù)整數(shù) N = C(n+r?1, r) 例 4 r 個相同的球放到 n 個不同的盒子里，每個盒子球數(shù)不限，求放球方法數(shù) . 解： 固定 a 和 b, 中間選 7個字母，有 2 P(24,7)種方法， 將它看作大字母與其余 17個字母全排列有 18！種，共 N = 2 P(24,7) 18! 8348 2022/7/13 實(shí)例 (續(xù) ) 例 6 (1) 10個男孩， 5個女孩站成一排，若沒有女孩相鄰， 有多少種方法？ (2) 如果站成一個圓圈，有多少種方法？ 解 : (1) P(10,10) P(11,5) (2) P(10,10) P(10,5)/10 解：相當(dāng)于 2n 不同的球放到 n 個相同的盒子，每個盒子 2個，放法為 !2)!(22!0!2. . .2)!42()!22(22 ) !(2!2!1( 2 , 2 ). . .2 , 2 )(2, 2 )(2!1 nnnnnnnCnCnnNn???????例 7 把 2n 個人分成 n 組，每組 2人，有多少分法？ 8349 2022/7/13 實(shí)例 (續(xù) ) 解 使用一一對應(yīng)的思想求解這個問題 . a1, a2, …, ak ： k個不相鄰的數(shù) , 屬于集合 {1, 2, …, n} b1, b2, …, bk： k個允許相鄰的數(shù) , 屬于集合 {1, …, n?(k?1)} 對應(yīng)規(guī)則是 bi = ai?(i?1). i =1, 2, …, k 因此 N = C(n?k+1,k) 例 8 從 S={1, 2, … , n}中選擇 k 個不相鄰的數(shù)，有多少種方法？ 8350 2022/7/13 二項(xiàng)式定理 組合恒等式 非降路徑問題 8351 2022/7/13 二項(xiàng)式定理 定理 n 是正整數(shù)，對一切 x 和 y 證明方法 : 數(shù)學(xué)歸納法、組合分析法 . 證 當(dāng)乘積被展開時其中的項(xiàng)都是下述形式： xi yn?i, i = 0, 1, 2, …, n. 而構(gòu)成形如 xiyn?i 的項(xiàng)，必須從 n 個 和 (x+y) 中選 i 個提供 x，其它的 n?i 個提供 y. 因此， xiyn?i 的系數(shù)是 ，定理得證 . ????????????? nkknkn yxknyx0)(????????in8352 2022/7/13 二項(xiàng)式定理的應(yīng)用 例 1 求在 (2x－ 3y)25的展開式中 x12y13的系數(shù) . 解 由二項(xiàng)式定理 令 i =13 得到展開式中 x12y13的系數(shù)，即 ??? ???????????? 2502525 )3()2(25))3(2(iii yxiyx13121312 32!12!13!25)3(21325 ???????????8353 2022/7/13 組合恒等式 —— 遞推式 ??????????????????? ???????????????????????????????????????????????111.311.2.1knknknknknknknnkn證明方法：公式代入、組合分析 應(yīng)用： 1式用于化簡 2式用于求和時消去變系數(shù) 3式用于求和時拆項(xiàng)（兩項(xiàng)之和或者差），然后合并 8354 2022/7/13 組合恒等式 —— 變下項(xiàng)求和 NnknNnknnkknnk????????????????????? ????0)1(.5,00證明公式 4. 方法：二項(xiàng)式定理或者組合分析 . 設(shè) S={1,2,…, n}，下面計數(shù) S 的所有子集 . 一種方法就是分類處理， n元集合的 k子集個數(shù)是 ????????kn?? ????????nk kn