文章目录
一、排列组合示例 1 ( 组合 | 乘法法则 | 加法法则 )
二、排列组合示例 2
参考博客 :
【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )
【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )
一、排列组合示例 1 ( 组合 | 乘法法则 | 加法法则 )
基本计数公式就是 加法法则 , 乘法法则 ;
从 1 11 ~ 300 300300 中任意取出 3 33 个数 , 使得这三个数的和能被 3 33 整除 , 有多少种选取方法 ?
使用 分类 ( 乘法法则 ) , 分布 ( 加法法则 ) , 排列组合 的方法进行解决 ;
将上述 1 11 ~ 300 300300 数字 , 按照除以 3 33 的余数分为以下三类 :
① 除以 3 33 余数为 1 11 : A = { 1 , 4 , ⋯ , 298 } A = \{ 1, 4, \cdots , 298 \}A={1,4,⋯,298}
② 除以 3 33 余数为 2 22 : B = { 2 , 5 , ⋯ , 299 } B = \{ 2, 5, \cdots , 299 \}B={2,5,⋯,299}
③ 除以 3 33 余数为 0 00 : C = { 3 , 6 , ⋯ , 300 } C = \{ 3, 6, \cdots , 300\}C={3,6,⋯,300}
组合问题 :
在 A AA 集合中任选 3 33 个数 , 三个数之和肯定是 3 33 的倍数 , 可以倍 3 33 整除 ; 选取方法有 C ( 100 , 3 ) C(100, 3)C(100,3) 种 ;
在 B BB 集合中任选 3 33 个数 , 三个数之和肯定是 3 33 的倍数 , 可以倍 3 33 整除 ; 选取方法有 C ( 100 , 3 ) C(100, 3)C(100,3) 种 ;
在 C CC 集合中任选 3 33 个数 , 三个数之和肯定是 3 33 的倍数 , 可以倍 3 33 整除 ; 选取方法有 C ( 100 , 3 ) C(100, 3)C(100,3) 种 ;
乘法法则 : 在 A , B , C A,B,CA,B,C 中每个集合各取一个数 , 三个数之和也是 3 33 的倍数 ,
第一个集合取 1 11 个数 , 有 100 100100 种取法
第二个集合取 1 11 个数 , 有 100 100100 种取法
第三个集合取 1 11 个数 , 有 100 100100 种取法
总共有 10 0 3 100^3100
3
种取法 ;
最终的取法 , 使用加法法则 :
3 C ( 100 , 3 ) + 10 0 3 = 1485100 3C(100, 3) + 100^3 = 1485100
3C(100,3)+100
3
=1485100
二、排列组合示例 2
1000 ! 1000!1000! 末尾 0 00 的个数 ?
这个数值使用乘法计算 , 非常大 , 基本无法计算 ;
列出因式 : 将 1000 ! 1000!1000! 看做
1000 × 999 × 998 × ⋯ × 2 × 1 1000 \times 999 \times 998 \times \cdots \times 2 \times 11000×999×998×⋯×2×1
因式 ;
原理说明 : 上述因式中有 1000 10001000 个因子 , 将这 1000 10001000 个因子分解 , 如果分解式中有 i ii 个 5 55 , j jj 个 2 22 , 则 i ii 和 j jj 中较小的值 min { i , j } \min\{ i,j \}min{i,j} 就是 0 00 的个数 ;
上述 1 11 ~ 1000 10001000 这 1000 10001000 个数字中统计分解出的 2 22 和 5 55 的个数
统计 2 22 的因子个数 : 肯定大于 500 ;
① 是 2 22 的倍数的数字有 500 500500 个
② 是 4 44 的倍数的数字有 250 250250 个 , 分解出 2 × 2 2\times22×2 , 其中一个 2 22 在之前已经统计过 , 这里在加上 250 250250 个 2 22 , 当前有 750 750750 个 2 22 ;
③ 是 16 1616 的倍数的数字有 62 6262 个 , 分解出 2 × 2 × 2 2\times2 \times 22×2×2 , 其中两个 2 22 在之前已经统计过 , 这里在加上 62 6262 个 2 22 , 当前有 812 812812 个 2 22 ;
④ 是 32 3232 的倍数的数字有 31 3131 个 , 分解出 2 × 2 × 2 × 2 2\times2 \times 2\times 22×2×2×2 , 其中三个 2 22 在之前已经统计过 , 这里在加上 31 3131 个 2 22 , 当前有 833 833833 个 2 22 ;
⋮ \vdots⋮
统计 5 55 的因子个数 : 249 249249 个 ;
① 是 5 55 的倍数的数字有 200 200200 个 , 统计有 1 11 个因子 5 55 的情况 , 其中肯定有的因子可以分解出 25 , 125 , 625 25, 125, 62525,125,625 等情况 , 下面逐渐细化剥离出没有统计的因子 ;
② 是 25 2525 的倍数的数字有 40 4040 个 , 分解出 5 × 5 5\times55×5 , 其中一个 5 55 在之前已经统计过 , 这里在加上 40 4040 个 5 55 , 当前有 240 240240 个 5 55 ;
③ 是 125 125125 的倍数的数字有 8 88 个 , 分解出 5 × 5 × 5 5\times5 \times 55×5×5 , 其中两个 5 55 在之前已经统计过 , 这里在加上 8 88 个 5 55 , 当前有 248 248248 个 5 55 ;
④ 是 625 625625 的倍数的数字有 1 11 个 , 分解出 5 × 5 × 5 × 5 5\times5 \times 5 \times 55×5×5×5 , 其中三个 5 55 在之前已经统计过 , 这里在加上 1 11 个 5 55 , 当前有 249 249249 个 5 55 ;
分解出的 2 22 的个数 i ii 肯定是大于 500 500500 的数 ;
分解出的 5 55 的个数 j jj 值为 249 249249 个 ;
因此1000 ! 1000!1000! 末尾 0 00 的个数 是 249 249249 个 ;
