计数原理

                     

贡献者: 零穹

预备知识 集合的基数

  1本节介绍组合学里两个一般性的原则——加法原则和乘法原则。

   以下假设 $A$ 和 $B$ 是两类不同、互不关联的事件。

1. 加法原则

   加法原则:设事件 $A$ 有 $m$ 种选取方式,事件 $B$ 有 $n$ 种选取方式,则选 $A$ 或 $B$ 共有 $m+n$ 种方式。

   用集合的语言可将加法原则描述成如下定理(定理 4 ):

定理 1 

   设 $A,B$ 为有限集,且 $A\cap B=\emptyset$,则

\begin{equation} \left\lvert A\cup B \right\rvert = \left\lvert A \right\rvert + \left\lvert B \right\rvert ~. \end{equation}

推论 1 

   设 $n$ 个有限集合 $A_1,\cdots,A_n$ 满足

\begin{equation} A_i\cap A_j=\emptyset,1\leq i\neq j\leq n~, \end{equation}
\begin{equation} \left\lvert \bigcup_{i=1}^n A_i \right\rvert =\sum_{i=1}^n \left\lvert A_i \right\rvert ~. \end{equation}

2. 乘法原则

   乘法原则:设事件 $A$ 有 $m$ 种选取方式,事件 $B$ 有 $n$ 种选取方式,那么选取 $A$ 以后再选取 $B$ 共有 $m\cdot n$ 种方式。

   同样,用集合的语言可将乘法原则描述成如下的定理:

定理 2 

   设 $A,B$ 为有限集,$ \left\lvert A \right\rvert =m, \left\lvert B \right\rvert =n$,则

\begin{equation} \left\lvert A\times B \right\rvert = \left\lvert A \right\rvert \times \left\lvert B \right\rvert =m\cdot n~. \end{equation}

   证明:若 $m=0$ 或 $n=0$,则式 4 的两边均为 0,故等式成立。

   设 $m>0,n>0$,并且记

\begin{equation} A=\{a_1,\cdots,a_m\}~,\quad B=\{b_1,\cdots,b_n\}~. \end{equation}
定义映射
\begin{equation} \varphi:(a_i,b_j)\rightarrow (i-1)n+j\qquad (1\leq i\leq m,1\leq j\leq n)~, \end{equation}
则 $\varphi$ 是 $A\times B$ 到集合 $\{1,2\cdots,mn-1,mn\}$ 上的一一映射(试证明),根据集合基数的定义(定义 1 ),式 4 成立。

   证毕!

   注:乘法原则之所以能用定理 2 描述,是因为在乘法原则的描述中,选取 $A$ 以后再选取 $B$,这意味着 $A$ 与 $B$ 是有顺序的,这便使得选取 $A$ 再选取 $B$ 的方式能用笛卡尔积 $A\times B$(子节 2 )来描述(即二者一一对应)。比如:选取 $A$ 得到 $a_i$,再选取 $B$ 得到 $b_j$ 这样一种选取,可记为 $(a_i,b_j)$;或将 $(a_i,b_j)$ 理解为选取 $A$ 得到 $a_i$,再选取 $B$ 得到 $b_j$ 这样一种选取。

推论 2 

   设 $A_1,\cdots,A_n$ 为 $n$ 个有限集合,则

\begin{equation} \left\lvert A_1\times A_2\cdots A_n \right\rvert = \left\lvert A_1 \right\rvert \times \left\lvert A_2 \right\rvert \times\cdots\times \left\lvert A_n \right\rvert ~. \end{equation}


1. ^ 许胤龙,孙淑玲。组合数学引论(第二版),中国科学技术大学出版社.2010.


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利