“组合数论”的一个妙题———“装错信封问题”在高考中的实际应用

◇ 甘肃 丁小强

“装错信封问题”作为组合数论中非常经典的一个问题,在日常教学和高考中经常出现.本文将拓展思路,探讨该问题与其他问题结合的考查方法.

1 装错信封问题的来源

“装错信封问题”是由17世纪至18世纪世界上著名的数学家约翰·伯努利(Johann Ber noulli,1667—1748)的儿子丹尼尔·伯努利(Daniel Ber noulli,1700—1782)提出来的,原题大意如下:

某个人写了n封互不相同的信件,与信件一一对应的有n个互不相同的信封,他要求这n封信必须都装错信封,也就是每封信件都不可以装到与之对应的信封里,问这样的装法有多少种.

这个问题也被约翰·伯努利的学生,著名的数学家欧拉称为“组合数论”的一个妙题.该问题也被称为全错位排列问题.

2 “装错信封问题”常规考法

例1某学校高三年级有4个班,学校举行的摸底考试要求4名班主任分别监考4个班,并且每名班主任都不可以监考自己班,请问有多少种安排方案.

解析

1)顶针法:4个班级1,2,3,4班对应的班主任称为一、二、三、四.若先排一,有3种排法(即2,3,4),若排到2班,则接下来排班主任二也有3种排法(即1,3,4),最后排班主任三、四,两人都只有1种排法,因此由分步计数原理可计算出共有3×3×1×1＝9种排法.

2)公式法:将n＝4代入中,即可计算出为9种.

也可用列举法,列举法与顶针法应对错位元素较少的题型实践性较高,应对错位元素较多的题型则太过复杂且容易重复或遗漏.公式法中由于该公式不是高中课程内容的基本公式,故高考考查的错位元素不会太多,因此我们只需要记住2～5个元素的全错位数即可:A2＝1,A3＝2,A4＝9,A5＝44.

3 装错信封问题与考题结合的新思路

“装错信封问题”作为排列组合中的经典问题,可以与其他的知识点相结合,更新颖、更灵活地考查学生的能力.

1)“装错信封问题”与涂色问题的结合

例2用3种不同的颜色给正三棱柱的6个顶点涂色,则相连接的顶点都不同色的涂法有多少种?

解析

正三棱柱ABC-A1B1C1的两个底面都为正三角形,已知三角形的3个顶点之间互相连接,所以两个三角形都必须使用3种颜色涂色才能满足题中相连接的顶点不同色的要求.上下两个面的点通过正三棱柱的3条侧棱相连接,AA1,BB1,CC1形成了一一对应关系,符合全错位的基本形式,所以上下两个面需要全错位涂色.

先涂A,B,C这3个点,再涂A1,B1,C1这3个点,且上下两个面的点全部错位,故共有A33×2＝3×2×1×2＝12种.

2)“装错信封问题”与分布列结合

例3某实验小组由4名同学组成,老师要求实验结束后必须要整理好实验器材并且打扫实验室卫生.小明想到了一个方式,在4张完全相同的卡片上写上每个人名字然后随机抽取,若抽到自己名字则留下,反之则不用留下.请列出留下打扫卫生人数的分布列.并且说明这种方法的合理性.

解析

该题是“装错信封问题”与分布列的结合,留下来的总人数X＝0,1,2,4(注意1个元素是没有全错位的,所以不可能留下3人).一共有A44＝4×3×2×1＝24种抽取情况,若没有人留下则为4人与4张卡片全错位,共有9种情况,所以P(X＝0)＝;若1人留下来则先选出留下的1人,剩下的3人全错位,共有种情况,所以若2人留下来则先选出留下的2人,剩下的2人全错位,共有种情况,所以若4人留下来则全不错位,所以这样我们就可以得到留下打扫卫生人数的分布列.

“装错信封问题”作为组合数论中的经典问题,不仅与实际问题结合紧密,并且灵活多变,从全部装错到局部装错,思路逐渐深入.该问题难度适中,若与其他知识点有机结合,定会成为高考命题中经典的题型.