参考博客 :

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

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

---

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

从

1

1

1 ~

300

300

300 中任意取出

3

3

3 个数 , 使得这三个数的和能被

3

3

3 整除 , 有多少种选取方法 ?

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

将上述

1

1

1 ~

300

300

300 数字 , 按照除以

3

3

3 的余数分为以下三类 :

• ① 除以 $3$

  1 :

  A

  =

  {

  1

  ,

  4

  ,

  ⋯
   

  ,

  298

  }

  A = \{ 1, 4, \cdots , 298 \}

  A={1,4,⋯,298}

• ② 除以 $3$

  2 :

  B

  =

  {

  2

  ,

  5

  ,

  ⋯
   

  ,

  299

  }

  B = \{ 2, 5, \cdots , 299 \}

  B={2,5,⋯,299}

• ③ 除以 $3$

  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$

总共有

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$

  500 个

• ② 是 $4$

  250 个 , 分解出

  2

  ×

  2

  2\times2

  2×2 , 其中一个

  2

  2

  2 在之前已经统计过 , 这里在加上

  250

  250

  250 个

  2

  2

  2 , 当前有

  750

  750

  750 个

  2

  2

  2 ;

• ③ 是 $16$

  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$

  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$

  200 个 , 统计有

  1

  1

  1 个因子

  5

  5

  5 的情况 , 其中肯定有的因子可以分解出

  25

  ,

  125

  ,

  625

  25, 125, 625

  25,125,625 等情况 , 下面逐渐细化剥离出没有统计的因子 ;

• ② 是 $25$

  40 个 , 分解出

  5

  ×

  5

  5\times5

  5×5 , 其中一个

  5

  5

  5 在之前已经统计过 , 这里在加上

  40

  40

  40 个

  5

  5

  5 , 当前有

  240

  240

  240 个

  5

  5

  5 ;

• ③ 是 $125$

  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$

  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 个 ;