程序员社区

【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )

文章目录

    • 1. 加法原则
      • ( 1 ) 加法原则 ( 不能叠加 的事件才能用 加法原则 | 适用于 分类选取 )
      • ( 2 ) 乘法法则 ( 相互独立 的 事件 才能用 乘法法则 | 适用于 分步选择 )
    • 2. 习题解析
      • ( 1 ) 习题 1 ( 加法原理 )
      • ( 2 ) 习题 2 ( 加法原则 乘法原则 综合运用 )
      • ( 3 ) 习题 3 ( 乘法原则 )

1. 加法原则

( 1 ) 加法原则 ( 不能叠加 的事件才能用 加法原则 | 适用于 分类选取 )

加法原则 :

  • 1.加法法则描述 : 事件

    A

    A

    A

    m

    m

    m 种 产生方式 , 事件

    B

    B

    B

    n

    n

    n 种 产生方式 , 则 " 事件

    A

    A

    A

    B

    B

    B " 有

    m

    +

    n

    m + n

    m+n 种产生方式 ;

  • 1.加法法则推广 :事件

    A

    1

    ,

    A

    2

    ,

    .

    .

    .

    ,

    A

    n

    A_{1} , A_{2} , ... , A_{n}

    A1,A2,...,An 分别有

    p

    1

    ,

    p

    2

    ,

    .

    .

    .

    ,

    p

    n

    p_{1} , p_{2} , ... , p_{n}

    p1,p2,...,pn 种 产生方式 , 若 其中 任何 两个 事件 产生的方式 都 不重叠 , 则 " 事件

    A

    1

    A_{1}

    A1

    A

    2

    A_{2}

    A2 或 … 或

    A

    n

    A_{n}

    An " 产生的方式 是

    p

    1

    +

    p

    2

    +

    .

    .

    .

    +

    p

    n

    p_{1} + p_{2} + ... + p_{n}

    p1+p2+...+pn ;

  • 2.注意点 : 这里的 事件

    A

    1

    ,

    A

    2

    ,

    .

    .

    .

    ,

    A

    n

    A_{1} , A_{2} , ... , A_{n}

    A1,A2,...,An 必须是 不能重叠的 , 即 只有 一件 事件 发生 , 如果有多个 事件 同时发生 , 就必须 使用 乘法原则 ;

  • 3.适用问题 : 分类选取 ;

( 2 ) 乘法法则 ( 相互独立 的 事件 才能用 乘法法则 | 适用于 分步选择 )

乘法原则 :

  • 1.乘法法则描述 : 事件 A 有 m 种 产生方式 , 事件 B 有 n 种 产生方式 , 则 " 事件 A 与 B " 有 mn 种产生方式 ;
  • 1.乘法法则推广 :事件

    A

    1

    ,

    A

    2

    ,

    .

    .

    .

    ,

    A

    n

    A_{1} , A_{2} , ... , A_{n}

    A1,A2,...,An 分别有

    p

    1

    ,

    p

    2

    ,

    .

    .

    .

    ,

    p

    n

    p_{1} , p_{2} , ... , p_{n}

    p1,p2,...,pn 种 产生方式 , 若 其中 任何 两个 事件 产生的方式 都 相互独立 , 则 " 事件

    A

    1

    A_{1}

    A1

    A

    2

    A_{2}

    A2 或 … 或

    A

    n

    A_{n}

    An " 产生的方式 是

    p

    1

    p

    2

    .

    .

    .

    p

    n

    p_{1} p_{2} ... p_{n}

    p1p2...pn ;

  • 2.注意点 : 这里的 事件

    A

    1

    ,

    A

    2

    ,

    .

    .

    .

    ,

    A

    n

    A_{1} , A_{2} , ... , A_{n}

    A1,A2,...,An 必须是 相互独立 的 ;

  • 3.适用问题 : 分步选取 ;

2. 习题解析

( 1 ) 习题 1 ( 加法原理 )

题目 :

汽车市场 有 卡车 15 辆 , 面包车 8 辆 , 轿车 20 辆 ;
从市场中只购买一辆车 , 有多少种购买方式 ?

解答 :

① 这里用到了 加法原则 , 如果只能 买 一辆车的话 , 三种车 只能买一种 , 三个事件 是不能重叠的 ;

② 买卡车 有 15 种方式 , 买面包车 有 8 种方式 , 买轿车 有 20 种 , 三种方式只能选择一种 , 三者不能重叠 ( 同时存在 ) , 因此使用加法原则 进行计算 ;

③ 结果是 : 15 + 8 + 20 = 43 ;


( 2 ) 习题 2 ( 加法原则 乘法原则 综合运用 )

A

,

B

,

C

A , B , C

A,B,C 是 3 个城市 ,

A

A

A

B

B

B 有 3 条路 ,

B

B

B

C

C

C 有 2 条路 ,

A

A

A

C

C

C

4

4

4 条路 ,
问 从

A

A

A

C

C

C 有多少种不同的方式 ?

解 :

加法原则 :
① 直接从

A

A

A

C

C

C 与 ② 从

A

A

A 先到

B

B

B 再到

C

C

C 是 不能重叠的 , 方案 ① 与 方案 ② 需要 用家法原则 ,

乘法原则 :
方案 ② 内部需要使用 乘法原则 即

A

A

A

B

B

B 有 3 种 选择 ,

B

B

B

C

C

C 有 2 种选择 , 这两个选择是相互独立的 , 需要分步 选择 ,

3

2

=

6

3 * 2 = 6

32=6 ;

最终

N

=

3

×

2

+

4

=

10

N = 3 \times 2 + 4 = 10

N=3×2+4=10 ;


( 3 ) 习题 3 ( 乘法原则 )

题目 :

1000

1000

1000

9999

9999

9999 的 整数 中 :

① 含有5的数有多少个 ;
② 含有多少个 百位 和 十位数 均为 奇数 的 偶数 ;
③ 各位数 都不相同 的 奇数 有多少个;

解答 :

( 1 ) 含有 5 的数 的个数 :

① 设 数字 集合

{

0

,

1

,

2

,

3

,

4

,

5

,

6

,

7

,

8

,

9

}

\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}

{0,1,2,3,4,5,6,7,8,9}

② 直接求 含有

5

5

5 的数 , 比较麻烦 : 这里可以分成

1

1

1 位 含有

5

5

5 的数 , 此时又分成 个位 十位 百位 千位 四种情况 ,

2

2

2 位 或

3

3

3 位 含有

5

5

5 更加复杂 ;

③ 这里 可以 转换一下思路 , 求 不含 5 的个数 :

  • 1> 千位 : 千位数 不能 取

    0

    0

    0

    5

    5

    5 , 只能取值

    8

    8

    8 种情况 ;

  • 2> 百位 : 百位数 不能 取

    5

    5

    5 ,

    9

    9

    9 种 取值情况 ;

  • 3> 十位 : 百位数 不能 取

    5

    5

    5 ,

    9

    9

    9 种 取值情况 ;

  • 4> 个位 : 百位数 不能 取

    5

    5

    5 ,

    9

    9

    9 种 取值情况 ;

根据乘法原则 : 不含

5

5

5 的个数位为

8

×

9

×

9

×

9

=

5832

8 \times 9\times 9\times 9 = 5832

8×9×9×9=5832
含有 5 的个数为 :

9000

5832

=

3168

9000 - 5832 = 3168

90005832=3168 ;

( 2 ) 百位 和 十位数 均为 奇数 的 偶数 :

分析 四位 数 取值方案数 :

  • 1> 个位数取值方案数 : 考虑偶数的情况 : 如果为 偶数 , 那么 个位数 只能取值

    {

    0

    ,

    2

    ,

    4

    ,

    6

    ,

    8

    }

    \{0, 2, 4 , 6, 8\}

    {0,2,4,6,8}

    5

    5

    5 种情况 ;

  • 2> 十位数 和 百位数 取值 方案数 : 十位数 百位数 都是 奇数 , 那么 其 取值

    {

    1

    ,

    3

    ,

    5

    ,

    7

    ,

    9

    }

    \{1 , 3 , 5 , 7 , 9 \}

    {1,3,5,7,9} , 也是

    5

    5

    5 种方案 ;

  • 3> 千位数 取值 方案数 :

    {

    1

    ,

    2

    ,

    3

    ,

    4

    ,

    5

    ,

    6

    ,

    7

    ,

    8

    ,

    9

    }

    \{1 , 2, 3, 4, 5, 6, 7, 8, 9\}

    {1,2,3,4,5,6,7,8,9} , 有

    9

    9

    9 种方案 ;

根据 乘法 原则 : 百位 和 十位 均为 奇数 的 偶数 有

9

×

5

×

5

×

5

=

1125

9 \times 5 \times 5 \times 5 = 1125

9×5×5×5=1125 个 ;

( 3 ) 各位数 都不相同 的 奇数 个数 :

逐位分析 :

  • 1> 分析 个位数 取值 : 个位数 如果不做限制的话 , 有

    10

    10

    10 种方案数

    {

    0

    ,

    1

    ,

    2

    ,

    3

    ,

    4

    ,

    5

    ,

    6

    ,

    7

    ,

    8

    ,

    9

    }

    \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}

    {0,1,2,3,4,5,6,7,8,9} , 要求 是 奇数 , 因此 个位数 只有

    5

    5

    5 中方案 , 只能从

    {

    1

    ,

    3

    ,

    5

    ,

    7

    ,

    9

    }

    \{1,3,5,7,9\}

    {1,3,5,7,9} 中取值 ;

  • 2> 分析 千位 的取值 : 千位数 不做限制的话 有

    9

    9

    9 种方案

    {

    1

    ,

    2

    ,

    3

    ,

    4

    ,

    5

    ,

    6

    ,

    7

    ,

    8

    ,

    9

    }

    \{1, 2, 3, 4, 5, 6, 7, 8,9\}

    {1,2,3,4,5,6,7,8,9} , 如果要求 与 个位数不同 , 那么有

    8

    8

    8 种方案 ;

  • 3> 分析 百位 数取值 : 百位数 如果不做限制的话 , 有

    10

    10

    10 种方案数

    {

    0

    ,

    1

    ,

    2

    ,

    3

    ,

    4

    ,

    5

    ,

    6

    ,

    7

    ,

    8

    ,

    9

    }

    \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}

    {0,1,2,3,4,5,6,7,8,9} , 千位 与 个位 各自 取了 一位数 , 那么只能下

    8

    8

    8 种 方案数 ;

  • 4> 分析 十位 数取值 : 十位数 如果不做限制的话 , 有

    10

    10

    10 种方案数

    {

    0

    ,

    1

    ,

    2

    ,

    3

    ,

    4

    ,

    5

    ,

    6

    ,

    7

    ,

    8

    ,

    9

    }

    \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}

    {0,1,2,3,4,5,6,7,8,9} , 千位 , 个位 与 百位 各自 取了 一位数 , 那么只能下

    7

    7

    7 种 方案数 ;

根据乘法原则 :

1000

1000

1000

9999

9999

9999 的整数中 , 各个位数 都 不相同的 奇数 有

5

×

8

×

7

×

7

=

2240

5 \times 8 \times 7 \times 7 = 2240

5×8×7×7=2240 ;

每一位分析的先后顺序很有讲究 , 一般先分析 条件限制比较苛刻的 选择 , 在分析 比较宽松的选择 ;

关于一一对应 的说明 :
如果 性质

A

A

A 的 计数 比较困难 , 性质

B

B

B 的计数比较容易 , 性质

A

A

A 和 性质

B

B

B 存在一一对应 , 那么对性质

A

A

A 的计数 , 可以转化为 对 性质

B

B

B 的计数 ;
这里用到了 一一对应 , 如 上述 , 计数 含有

5

5

5 的整数个数 , 如果正面计数比较困难 , 可以反过来 计算 不含有

5

5

5 的整数个数 , 这样就比较好计数了 ,

1000

1000

1000

9999

9999

9999 一共有

9000

9000

9000 个数 ,

9000

5

9000 - 不含5的整数个数

90005 与 含有

5

5

5 的整数个数 是一一对应的 ;

常用的一一对应 :
① 选取问题
② 不定方程非负整数解问题
③ 非降路径问题
④ 正整数拆分问题
⑤ 放球问题


赞(0) 打赏
未经允许不得转载:IDEA激活码 » 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )

相关推荐

  • 暂无文章

一个分享Java & Python知识的社区