高中计数原理回顾

最近无意中看到一些概率题,看似简单,但就是算不对。细究起来,概率问题中有许多基于古典概型(等可能概型)的问题与排列组合之类的基础知识关系很大。而高中的计数原理恰好学得很糊涂。啊,出来混果然都是要还的。

概念


1. 加法原理 (分类计数原理)

如果完成一件事有$n$类方式,在第1类方式中有$m_1$种不同的方法,在第2类方式中有$m_2$种不同的方法, …, 在第$n$类方式中有$m_n$种不同的方法,那么完成这件事共有$N = m_1 + m_2 + … + m_n$种不同的方法。

2. 乘法原理 (分步计数原理)

如果完成一件事需要$n$个步骤,做第1步有$m_1$种不同的方法,在第2步有$m_2$种不同的方法, …, 在第$n$步有$m_n$种不同方法,那么完成这件事共有$N = m_1 \times m_2 \times … \times m_n$种不同的方法。

3. 排列

a. 定义: 从 $n$ 个不同的元素中取出 $m$ ($m \leq n$) 个元素,按照一定的顺序排成一列,叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列。

b. 特点: 有序性

c. 排列数公式
$$A_n^m = n (n-1) (n-2) … (n-m+1)$$

或者

$$A_n^m = \frac{n!}{(n - m)!}$$

其中$n, m \in N_+, 且m \leq n$

4. 组合

a. 定义: 从 $n$ 个不同的元素中取出 $m$ ($m \leq n$) 个元素,叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合。

b. 特点: 无序性

c. 组合数公式
$$C_n^m = \frac{A_n^m}{A_m^m} = \frac{n (n-1) (n-2) … (n-m+1)}{m!}$$

或者

$$C_n^m = \frac{n!}{m!(n - m)!}$$

其中$n, m \in N_+, 且m \leq n$

d. 组合数性质 $$C_n^m = C_n^{n-m}$$


例题


例1. 将一个四棱锥S - ABCD的每个顶点涂上一种颜色,使同一条棱的两端点异色,如果只有5种颜色可供使用,那么不同的涂色方法的总数是多少? Fig.

例2. 从0, 1, 2, 3, 4, 5这些数字中选出4个,问能形成多少无重复数字且能被5整除的四位数?

例3. 七名学生站成一排,下列情况各有多少种不同排法?(1) 甲乙必须排在一起 (2) 甲不在排头,乙不在排尾 (3) 甲乙丙互不相临 (4) 甲乙之间必须隔一人

例4. 把5件不同产品摆成一排,若产品A与产品B相邻,且产品A与产品C不相邻,则不同的摆法有多少种?

例5. 某次联欢会要安排3个歌舞类节目,2个小品类节目和1个相声类节目的演出顺序,则同类节目不相邻的排法总数是?

例6. 若一个三位数的十位数字比个位数字和百位数字都大,则称这个数为“伞数”. 现从1, 2, 3, 4, 5, 6 这6个数字中任取三个数,组成无重复数字的三位数,其中“伞数”有多少个?(不使用分类枚举)

例7. 将10个相同的小球随机放入3个盒内,求有多少种 (1) 不同的放法 (2) 每个盒内至少有1个球的放法

例8. 由两个1, 两个2, 两个3组成的6位数的个数是多少?


题解


通用解题思想: 分类、正繁则反

例1. 可以先分步再分类,也可以先分类再分步。我觉得前者更直观些。

按照S, A, B, C, D的顺序涂色。
第一步,给S涂色,有5种方法
第二步,给A涂色,有4种方法
第三步,给B涂色,有3种方法
第四步,给C涂色。这时C颜色的选择策略会影响D的颜色选择个数。
分类讨论
情况(1) C选择和A相同的颜色。那么C颜色确定(一种) D可选择3种颜色。颜色总个数为$5 \times 4 \times 3 \times 1 \times 3$
情况(2) C选择和A不同的颜色。那么C可选2种,D可选2种。颜色总个数为$5 \times 4 \times 3 \times 2 \times 2$
因此总数为情况(1)和(2)的总和,420


例2. 先分类再分步比较方便。若要能被5整除,则个位需是0或5.

第一类,个位为0
  _     _     _    0
  $5 \times 4 \times 3 = 60$
  |
千位

第二类,个位为5
  _     _     _    5
  $4 \times 4 \times 3 = 48$
  |
千位

因此总数为$48 + 60 = 108$


例3.
(1) 典型相邻问题,捆绑法,把甲乙看成一个整体,与剩余元素全排列$A_6^6 A_2^2$
(2) 解法一,直接法,分类讨论第一种,甲在排尾, 则剩余元素全排列 $A_6^6$. 第二种,甲不在队尾,则甲有选择 $A_5^1$种,乙有选择 $A_5^1$种,其余人 $A_5^5$. 总共$A_6^6 + A_5^1 A_5^1 A_5^5 = 3720$
解法二,间接法,正繁则反。所有排列可能为 $A_7^7$, 甲在排头有 $A_6^6$种,乙在排尾同样有$A_6^6$种,两者有重复情况,即甲在排头且乙在排尾,这种情况占$A_5^5$, 因此总数为$A_7^7 - 2 A_6^6 + A_5^5 = 3720$
(3) 要不相邻,插空法。将剩下四名学生排队,有$A_4^4$种排法。将甲乙丙插入四名学生产生的五个空,有$A_5^3$种排法,因此有$A_4^4A_5^3=1440$
(4) 首先在剩下的人中选一个插在甲乙中间,然后捆绑法将这三人看成一个整体,与剩下四个人全排列,共$5A_2^2A_5^5 = 1200$


例4. 解法一,间接法,正繁则反 首先因为AB相邻,将两者捆绑,与剩下所有产品一起全排列,共有$A_2^2A_3^3$种。其中将ABC捆绑在一起并且A在中间(也就是满足AB相邻,但不满足AC不相邻)有$A_2^2A_3^3$种。两者相减,36
解法二,捆绑+插空. 将AB捆绑,并将其与除C之外的两个产品全排列,有$A_3^3$种,然后将C插入这三者形成的可插空隙(共有4个,A边上的不可以),有$A_3^1$种。故共有$A_2^2 A_3^3 A_3^1$种


例5. 这题略复杂。先基于小品和相声的排列分类讨论。
第一种,小品1 小品2 相声。然后将歌舞插空。因为不能有相邻的相同节目,所以歌舞必须插在小品1和小品2之间。然后,剩下的两个歌舞可插三空, $A_2^2 C_3^1 A_3^2$

第二种,小品1 相声 小品2. 这种情况,三个歌舞可对四空任意插空, $A_2^2 A_4^3$

第三种,相声 小品1 小品2. 这种情况和第一种类似

总数120.


例6. 参考书答案里的一个十分巧妙的思路:6个数中任取3个有$C_6^3$种情况,每一种将最大一个数放在中间,可以组成两个不同的三位数。故共有$2 \times C_6^3 = 40$种


例7

(1) 和17 Spring CS2800的hw4 1(b) 类似。与其安排球,不妨反过来安排盒子的位置。有三个盒子,那么一共有四个盒子边缘,其中有两个固定在两边。接下来安排剩余两个边缘。将球和边缘都看作是0,一共有12个0. 在这12个0中选两个作为1 (边缘),共$C_{12}^2$种选法

(2) 要确保至少每个盒子有一个球,那就是不能有相邻边缘。插空,在10个球中形成的9个空隙选取两个位置,共有$C_9^2$种选法


例8. 相当于在六个位置中选两个填上一种数字,然后在四个位置种选两个填上另一种数字,以此类推。有$C_6^2 C_4^2 C_2^2$个不同的数字


小结


计数问题的重点在于不同目标的区分:有时是选取元素,有时是选取位置;有的又在总体讲求顺序的情况下个别不需要考虑顺序。


参考用书


薛金星, 中学教材全解(配套江苏版教材), 高中数学选修2-3, 山西人民教育出版社

comments powered by Disqus