参考博客 :

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

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

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

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

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

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

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

组合问题 :

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

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

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

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

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

总共有 $100^3$ 种取法 ;

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

$$3C(100,3)+100^3=1485100$$

二、排列组合示例 2

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

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

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

$1000\times 999\times 998\times \cdots \times 2\times 1$

因式 ;

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

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

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

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

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

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

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

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

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

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/109113338