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

韩曙亮

发布于 2023-03-28 18:14:34

2.4K0

发布于 2023-03-28 18:14:34

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

参考博客 :

一、排列组合示例 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\times2

, 其中一个

2

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

250

个

2

, 当前有

750

个

2

;

③ 是

16

的倍数的数字有

62

个 , 分解出

2\times2 \times 2

, 其中两个

2

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

62

个

2

, 当前有

812

个

2

;

④ 是

32

的倍数的数字有

31

个 , 分解出

2\times2 \times 2\times 2

, 其中三个

2

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

31

个

2

, 当前有

833

个

2

;

\vdots

统计

5

的因子个数 :

249

个 ;

① 是

5

的倍数的数字有

200

个 , 统计有

1

个因子

5

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

25, 125, 625

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

② 是

25

的倍数的数字有

40

个 , 分解出

5\times5

, 其中一个

5

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

40

个

5

, 当前有

240

个

5

;

③ 是

125

的倍数的数字有

8

个 , 分解出

5\times5 \times 5

, 其中两个

5

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

8

个

5

, 当前有

248

个

5

;

④ 是

625

的倍数的数字有

1

个 , 分解出

5\times5 \times 5 \times 5

, 其中三个

5

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

1

个

5

, 当前有

249

个

5

;

分解出的

2

的个数

i

肯定是大于

500

的数 ;

分解出的

5

的个数

j

值为

249

个 ;

因此

1000!

末尾

0

的个数是

249

个 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-16，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度