【组合数学】排列组合 ( 排列组合示例 )

参考博客 :

• 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
• 【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )
• 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )

一、排列组合示例 1 ( 组合 | 乘法法则 | 加法法则 )

基本计数公式就是 加法法则 , 乘法法则 ;

从 1 1 1 ~ 300 300 300 中任意取出 3 3 3 个数 , 使得这三个数的和能被 3 3 3 整除 , 有多少种选取方法 ?

使用 分类 ( 乘法法则 ) , 分布 ( 加法法则 ) , 排列组合 的方法进行解决 ;

将上述 1 1 1 ~ 300 300 300 数字 , 按照除以 3 3 3 的余数分为以下三类 :

• ① 除以 3 3 3 余数为 1 1 1 : A = { 1 , 4 , ⋯   , 298 } A = \{ 1, 4, \cdots , 298 \} A={1,4,⋯,298}
• ② 除以 3 3 3 余数为 2 2 2 : B = { 2 , 5 , ⋯   , 299 } B = \{ 2, 5, \cdots , 299 \} B={2,5,⋯,299}
• ③ 除以 3 3 3 余数为 0 0 0 : C = { 3 , 6 , ⋯   , 300 } C = \{ 3, 6, \cdots , 300\} C={3,6,⋯,300}

组合问题 :

• 在 A A A 集合中任选 3 3 3 个数 , 三个数之和肯定是 3 3 3 的倍数 , 可以倍 3 3 3 整除 ; 选取方法有 C ( 100 , 3 ) C(100, 3) C(100,3) 种 ;

• 在 B B B 集合中任选 3 3 3 个数 , 三个数之和肯定是 3 3 3 的倍数 , 可以倍 3 3 3 整除 ; 选取方法有 C ( 100 , 3 ) C(100, 3) C(100,3) 种 ;

• 在 C C C 集合中任选 3 3 3 个数 , 三个数之和肯定是 3 3 3 的倍数 , 可以倍 3 3 3 整除 ; 选取方法有 C ( 100 , 3 ) C(100, 3) C(100,3) 种 ;

乘法法则 : 在 A , B , C A,B,C A,B,C 中每个集合各取一个数 , 三个数之和也是 3 3 3 的倍数 ,

• 第一个集合取 1 1 1 个数 , 有 100 100 100 种取法
• 第二个集合取 1 1 1 个数 , 有 100 100 100 种取法
• 第三个集合取 1 1 1 个数 , 有 100 100 100 种取法

总共有 10 0 3 100^3 1003 种取法 ;

最终的取法 , 使用加法法则 :

3 C ( 100 , 3 ) + 10 0 3 = 1485100 3C(100, 3) + 100^3 = 1485100 3C(100,3)+1003=1485100

二、排列组合示例 2

1000 ! 1000! 1000! 末尾 0 0 0 的个数 ?

这个数值使用乘法计算 , 非常大 , 基本无法计算 ;

列出因式 : 将 1000 ! 1000! 1000! 看做

1000 × 999 × 998 × ⋯ × 2 × 1 1000 \times 999 \times 998 \times \cdots \times 2 \times 1 1000×999×998×⋯×2×1

因式 ;

原理说明 : 上述因式中有 1000 1000 1000 个因子 , 将这 1000 1000 1000 个因子分解 , 如果分解式中有 i i i 个 5 5 5 , j j j 个 2 2 2 , 则 i i i 和 j j j 中较小的值 min ⁡ { i , j } \min\{ i,j \} min{i,j} 就是 0 0 0 的个数 ;

上述 1 1 1 ~ 1000 1000 1000 这 1000 1000 1000 个数字中统计分解出的 2 2 2 和 5 5 5 的个数

统计 2 2 2 的因子个数 : 肯定大于 500 ;

• ① 是 2 2 2 的倍数的数字有 500 500 500 个
• ② 是 4 4 4 的倍数的数字有 250 250 250 个 , 分解出 2 × 2 2\times2 2×2 , 其中一个 2 2 2 在之前已经统计过 , 这里在加上 250 250 250 个 2 2 2 , 当前有 750 750 750 个 2 2 2 ;
• ③ 是 16 16 16 的倍数的数字有 62 62 62 个 , 分解出 2 × 2 × 2 2\times2 \times 2 2×2×2 , 其中两个 2 2 2 在之前已经统计过 , 这里在加上 62 62 62 个 2 2 2 , 当前有 812 812 812 个 2 2 2 ;
• ④ 是 32 32 32 的倍数的数字有 31 31 31 个 , 分解出 2 × 2 × 2 × 2 2\times2 \times 2\times 2 2×2×2×2 , 其中三个 2 2 2 在之前已经统计过 , 这里在加上 31 31 31 个 2 2 2 , 当前有 833 833 833 个 2 2 2 ; ⋮ \vdots ⋮

统计 5 5 5 的因子个数 : 249 249 249 个 ;

• ① 是 5 5 5 的倍数的数字有 200 200 200 个 , 统计有 1 1 1 个因子 5 5 5 的情况 , 其中肯定有的因子可以分解出 25 , 125 , 625 25, 125, 625 25,125,625 等情况 , 下面逐渐细化剥离出没有统计的因子 ;
• ② 是 25 25 25 的倍数的数字有 40 40 40 个 , 分解出 5 × 5 5\times5 5×5 , 其中一个 5 5 5 在之前已经统计过 , 这里在加上 40 40 40 个 5 5 5 , 当前有 240 240 240 个 5 5 5 ;
• ③ 是 125 125 125 的倍数的数字有 8 8 8 个 , 分解出 5 × 5 × 5 5\times5 \times 5 5×5×5 , 其中两个 5 5 5 在之前已经统计过 , 这里在加上 8 8 8 个 5 5 5 , 当前有 248 248 248 个 5 5 5 ;
• ④ 是 625 625 625 的倍数的数字有 1 1 1 个 , 分解出 5 × 5 × 5 × 5 5\times5 \times 5 \times 5 5×5×5×5 , 其中三个 5 5 5 在之前已经统计过 , 这里在加上 1 1 1 个 5 5 5 , 当前有 249 249 249 个 5 5 5 ;

分解出的 2 2 2 的个数 i i i 肯定是大于 500 500 500 的数 ;

分解出的 5 5 5 的个数 j j j 值为 249 249 249 个 ;

因此 1000 ! 1000! 1000! 末尾 0 0 0 的个数 是 249 249 249 个 ;