【正文】 8383 2022/7/13 例 4 解（續(xù)） 用 迭代法 求解該遞歸關(guān)系： bn= bn1+n– 1 = bn2+n– 2+n1 = bn3+n– 3+n– 2+n– 1 = … = b1 + 1 + 2 + … +n– 3 + n– 2 + n– 1 = 0 + 1 + 2 + … +n – 3 + n– 2 + n– 1 = n(n1)/2。 輸出 ： s1, s2, … ,sn， 按非遞減順序排列 。 按此規(guī)律 ， 在沒有兔子死亡的情形下 ， 一對初生的兔子 ， 一年可以繁殖成多少隊(duì)兔子 ？ 解 因?yàn)?Fn = Fn1 + Fn2， 所以根據(jù)迭代法 ， 有 F12 = F11 + F10 = 2F10 + F9 = 3F9 + 2F8 = 5F8 + 3F7 = 8F7 + 5F6 = … = 89F2 +55F1 = 89 + 55 =143 。 8378 2022/7/13 例 2 解 將鐵盤按重量分類 ， 所有 a克到 a+； a+ a+； a+ a+ ， … .， 最后 ， a+ a+ ， 共計(jì) 20類 ， 由 鴿籠原理 知 ， 若該工廠生產(chǎn) 21個(gè)鐵盤 ， 那么就能得知有兩個(gè)鐵盤屬于同一類 ， 因而它們之間的重量差將不超過 。 8377 2022/7/13 例 2 某一制造鐵盤的工廠 ， 由于設(shè)備和技術(shù)的原因只能將生產(chǎn)盤子的重量控制在 a克到 （ a+） 克之間 。 為了安全起見 ， 必須有 4位在場時(shí)才能打開大門 。 200個(gè)是 5 的倍數(shù)， 40個(gè)是 25 的倍數(shù)（多加 40 個(gè) 5）， 8個(gè)是 125 的倍數(shù)（再多加 8 個(gè) 5）， 1個(gè)是 625 的倍數(shù)（再多加 1 個(gè) 5） i = 200+40+8+1 = 249. min(i, j)=249. 例 2 求 1000！的末尾有多少個(gè) 0？ 8344 2022/7/13 基本計(jì)數(shù)公式的應(yīng)用 (續(xù) ) 例 3 設(shè) A為 n 元集 ， 問 (1) A上的自反關(guān)系有多少個(gè) ？ (2) A上的反自反關(guān)系有多少個(gè) ？ (3) A上的對稱關(guān)系有多少個(gè) ？ (4) A上的反對稱關(guān)系有多少個(gè) ？ (5) A上既不對稱也不是反對稱 的關(guān)系有多少個(gè) ？ 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 時(shí)，每個(gè)位置都有 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), 證明 一個(gè) r 組合為 {x1?a1, x2?a2, …, xk?ak}， 其中 x1 + x2 + … + xk = r , xi 為非負(fù)整數(shù) . 這個(gè)不定方程的非負(fù)整數(shù)解對應(yīng)于下述排列 1…1 0 1…1 0 1…1 0 …… 0 1…1 x1個(gè) x2個(gè) x3個(gè) xk個(gè) r 個(gè) 1， k?1個(gè) 0 的全排列數(shù)為 ),1()!1(! )!1( rrkCkr krN ???????8347 2022/7/13 實(shí)例 例 5 排列 26個(gè)字母，使得 a 與 b 之間恰有 7個(gè)字母，求方法數(shù) . 解： 設(shè)盒子的球數(shù)依次記為 x1, x2, …, xn, 則滿足 x1 + x2 + … + xn = r， x1, x2, …, xn 為非負(fù)整數(shù) N = C(n+r?1, r) 例 4 r 個(gè)相同的球放到 n 個(gè)不同的盒子里，每個(gè)盒子球數(shù)不限，求放球方法數(shù) . 解： 固定 a 和 b, 中間選 7個(gè)字母，有 2 P(24,7)種方法， 將它看作大字母與其余 17個(gè)字母全排列有 18！種，共 N = 2 P(24,7) 18! 8348 2022/7/13 實(shí)例 (續(xù) ) 例 6 (1) 10個(gè)男孩， 5個(gè)女孩站成一排，若沒有女孩相鄰， 有多少種方法？ (2) 如果站成一個(gè)圓圈，有多少種方法？ 解 : (1) P(10,10) P(11,5) (2) P(10,10) P(10,5)/10 解：相當(dāng)于 2n 不同的球放到 n 個(gè)相同的盒子，每個(gè)盒子 2個(gè)，放法為 !2)!(22!0!2. . .2)!42()!22(22 ) !(2!2!1( 2 , 2 ). . .2 , 2 )(2, 2 )(2!1 nnnnnnnCnCnnNn???????例 7 把 2n 個(gè)人分成 n 組，每組 2人，有多少分法？ 8349 2022/7/13 實(shí)例 (續(xù) ) 解 使用一一對應(yīng)的思想求解這個(gè)問題 . a1, a2, …, ak ： k個(gè)不相鄰的數(shù) , 屬于集合 {1, 2, …, n} b1, b2, …, bk： k個(gè)允許相鄰的數(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 個(gè)不相鄰的數(shù)，有多少種方法？ 8350 2022/7/13 二項(xiàng)式定理 組合恒等式 非降路徑問題 8351 2022/7/13 二項(xiàng)式定理 定理 n 是正整數(shù)，對一切 x 和 y 證明方法 : 數(shù)學(xué)歸納法、組合分析法 . 證 當(dāng)乘積被展開時(shí)其中的項(xiàng)都是下述形式： xi yn?i, i = 0, 1, 2, …, n. 而構(gòu)成形如 xiyn?i 的項(xiàng)，必須從 n 個(gè) 和 (x+y) 中選 i 個(gè)提供 x，其它的 n?i 個(gè)提供 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