基本计数公式的应用(续) 例2求100!的末尾有多少个0? 1000.=1000×999×998×,×2×1 将上面的每个因子分解,若分解式中共有i个5,个2, 那么min{i门}就是0的个数 1,,400有 500个是2的倍数,j>50; 200个是5的倍数, 40个是25的倍数(多加40个5), 8个是125的倍数(再多加8个5), 1个是625的倍数(再多加1个5) 200+40+8+1=249.min{bj}=249
11 例 2 求 1000！的末尾有多少个 0？ 1000!=1000 ×999× 998 ×… × 2×1 将上面的每个因子分解，若分解式中共有 i 个 5, j 个 2， 那么 min{ i, j }就是 0 的个数. 1, …,1000 中有 500 个是 2 的倍数，j > 500; 200 个是 5 的倍数， 40 个是 25 的倍数（多加 40 个 5）， 8 个是 125 的倍数（再多加 8 个 5）， 1 个是 625 的倍数（再多加 1 个 5） i = 200+40+8+1 = 249. min{ i, j }=249. 基本计数公式的应用（续）
多重集的排列 多重集S={n1m1,m2m,…,nk“a},0<m≤+ (1)全排列r=n,m1+m2+…+mk=n N n1·m2… 证明:分步选取,先放a1,有C(n,m)种方法; 再放a,有C(m-n,n2种方法, 放ak,有Cn-n-m12…,nk)种方法 N=C(n, n,C(n-ni, n2).C(n-ny-n2 k-11k (2)若K≤m1时,每个位置都有k种选法,得K
12 多重集 S={n1⋅a1, n2⋅a2, …, nk⋅ak}，0 <ni ≤+∞ （1）全排列 r=n, n1 + n2 + … + nk = n ! !... ! ! n1 n2 nk n N = 证明：分步选取，先放 a1, 有 C(n, n1) 种方法； 再放 a2, 有 C(n-n1, n2)种方法，..., 放 ak，有 C(n-n1-n2-…-nk-1, nk) 种方法 ! !... ! ! ( , ) ( , )... ( ... , ) 1 2 1 1 2 1 2 1 k k k n n n n N C n n C n n n C n n n n n = = − − − − − − （2）若 r≤ni时，每个位置都有 k 种选法，得 kr. 多重集的排列
多重集的组合 多重集S={m11,n2m2,…,kk}的组合数为 N=C(k+r-r,当r≤m 证明一个r组合为 {x1,x22,…,xk}, 其中x+x2+…+xk=r,x为非负整数 这个不定方程的非负整数解对应于下述排列 1,,101.101..10,.01.1 x个x2个x个 x个 r个1,k1个0的全排列数为 N (r+k-1) =C(k+r-1,r) r!(k-1)
13 多重集 S={ n1⋅a1, n2⋅a2, …, nk⋅ak }的组合数为 N = C(k+r-1,r), 当 r ≤ ni 证明 一个 r 组合为 { x1⋅a1, x2⋅a2, …, xk⋅ak }， 其中 x1 + x2 + … + xk = r , xi 为非负整数 这个不定方程的非负整数解对应于下述排列 1…1 0 1…1 0 1…1 0 …… 0 1…1 x1个 x2 个 x3个 xk 个 r 个 1，k-1 个 0 的全排列数为 N = ( 1, ) !( 1)! ( 1)! C k r r r k r k = + − − + − 多重集的组合
实例 例5r个相同的球放到n个不同的盒子里,每个盒子球数不 限,求放球方法数 解:设盒子的球数依次记为x,x2,,x,则满足 x1+x2+…+xn=r,x1,x2,,xn为非负整数 N=C(n+r-1, 例4排列26个字母,使得a与b之间恰有7个字母,求方 法数 解:固定a和b中间选7个字母,有2P24,种方法, 将它看作大字母与其余17个全排列有18!种,共 N=2P(24,7)18
14 例 5 r 个相同的球放到 n 个不同的盒子里，每个盒子球数不 限，求放球方法数. 解： 设盒子的球数依次记为 x1, x2, …, xn, 则满足 x1 + x2 + … + xn = r， x1, x2, … , xn为非负整数 N = C(n+r-1, r) 例 4 排列 26 个字母，使得 a 与 b 之间恰有 7 个字母，求方 法数. 解： 固定 a 和 b 中间选 7 个字母，有 2 P(24,7)种方法， 将它看作大字母与其余 17 个全排列有 18！种，共 N = 2 P(24,7) 18! 实例
实例(续) 例5(1)10个男孩,5个女孩站成一排,若没有女孩相邻,有 多少种方法? (2)如果站成一个圆圈,有多少种方法? 解:(1)P10,10)P(15) (2)P(10,10)P(10,5/10 例6把2n个人分成n组,每组2人,有多少分法? 解:相当于2n不同的球放到n个相同的盒子,每个盒子2个, 放法为 (2n)!(2 (2)yn!22"nt
15 例 5 （1）10 个男孩，5 个女孩站成一排，若没有女孩相邻，有 多少种方法？ （2） 如果站成一个圆圈，有多少种方法？ 解：（1）P(10,10) P(11,5) （2）P(10,10) P(10,5)/10 例 6 把 2n 个人分成 n 组，每组 2 人，有多少分法？ 解：相当于 2n 不同的球放到 n 个相同的盒子，每个盒子 2 个， 放法为 2 ! (2 )! (2!) ! (2 )! n n n n N n n = = 实例（续）