科数网
数学题库
数学试卷
数学组卷
在线学习
电子教材
科数
试题
试卷
学习
教材
VIP
你好
游客，
登录
注册
在线学习
离散数学
第四章 组合数学与生成函数
基本计数原理
最后
更新:
2025-01-22 08:56
●
参与者
查看:
15
次
纠错
分享
参与项目
词条搜索
基本计数原理
定理 6.1 （加法原理）设 $A$ 和 $B$ 是有限集合 $S$ 的两个互不相交的子集，且 $A \cup B=S$ ，则 $|S|=|A|+|B|$ 。 证明：集合 $S$ 中的元素在子集 $A$ 中的个数有 $|A|$ 个，因为 $A$ 和 $B$ 互不相交，且 $A \cup B=S$ ，故 $S$ 中的元素不在 $A$ 中必在 $B$ 中，且 $B$ 中元素不在 $A$ 中，所以 $S$ 中不在 $A$ 中的元素有 $|B|$ 个，即 $|S|=|A|+|B|$ 。 以上的表述是从集合论的角度。从组合论角度来推广的话，如果针对一个任务，完成它有 $k$ 类办法，在第 $i$ 类办法中有 $m_i$ 种不同的方法，而且各个类别互不相干，那么完成这一任务共有 $\sum_{i=1}^k m_i$ 种不同的方法。 定理 6.2 （乘法原理）设集合 $A$ 和 $B$ 都是有限集，$|A|=p,|B|=q$ ，则 $|A \times B|=p q$ 。 证明极易，此处省略。同样可以从组合论的角度推广乘法原理，如果针对一个任务，完成它有 $k$ 个步骤，在第 $i$ 个步骤中有 $m_i$ 种不同的方法，那么完成这一任务共有 $\prod_{i=1}^k m_i$ 种不同的方法。 例 6.1 某学生从 2 门数学课和 4 门计算机课中任意选修一门，则有 $2+4=6$ 种选修方法。若他要选修数学课和计算机课各一门，则有 $2 \times 4=8$ 种选修方法。
上一篇：
鸽笼原理的加强形式
下一篇：
集合的排列
本文对您是否有用？
有用
(
0
)
无用
(
0
)
初中数学
高中数学
高中物理
高等数学
线性代数
概率论与数理统计
复变函数
离散数学
实变函数
数论
群论
纠错
题库
高考
考研
关于
下载
科数网是专业专业的数学网站。