排列组合问题中的错解剖析
关于排列组合的应用问题,由于思考方法的偏差,往往导致结论的错误. 然而,一个更应该值得注意的问题是,有时思考方法是错误的,得出的结果却巧合正确,这种隐蔽性的错误,对学习更有危害.请看下面的问题!
问题1:用1,2,3,4,5,6这六个数字组成无重复数字的六位数,其中首位数字大于末位数字,且3和4不在相邻两个数位的六位数共有多少个?
分析与解答:
分三步考虑.
第一步,首先将1,2,5,6排在四个位置(用方格□表示)上,有A种排法
△□△□△□△□△
第二步,1,2,5,6排好之后产生5个空隙(用记号△表示),将3,4插入这5个空隙中,有A种排法.
由分步计数原理可知,一共有A·A=480种不同的排法.
第三步,将这480个数分为两类(每个数与3,4都不相邻).
1. 首位数字大于末位数字;
2. 首位数字小于末位数字.
有一个首位数字大于末位数字的六位数,将首末两个数字对调,得到一个首位数字小于末位数字的六位数;反之也对. 因此,符合条件的六位数共有=240个.
上述解法正确吗?从分析过程看,似乎每一步都有道理,找不出什么破绽,但仔细分析,思考方法确有错误之处,错在哪里?
有错在第三步的分析方法上.一个符合条件的六位数,对调首末两个数字之后,未必能够得到一个首位数字小于末位数字且3,4不相邻的六位数. 例如,631524是一个符合条件的六位数,对调首位数字6和末位数字4,得六位数431526. 这个六位数4与3相邻了,它不是3,4不相邻的480个数中的一个. 因此,在3,4不相邻的六位数中,首位数字大于末位数字与首位数字小于末位数字的六位数不能通过只对调首末两个数字来实现一一对应关系.
正确的解答应该修改上述解法第三步的分析方法,有一个符合条件(首位数字大于末位数字且3,4不相邻)的六位数,如631524,将这个六位数反序倒写,可得到一个3,4不相邻,首位数字小于末位数字的六位数425136;反之也对,因此,首位数字大于末位数字且3,4不相邻的六位数,通过反序对调,可以实现首位数字小于末位数字且3,4不相邻的六位数构成一一对应关系.所以,符合条件的六位数共有=240个.
问题2:把n+1本不同的书全部分给n个人,每人至少得1本,共有多少种不同的分法?
分析与解答:分两步考虑.第一步,先从n+1本不同的书中任取n本分给n个人,有C·A种分法.
第一步,将余下的1本书分给n个人,有n种分法,由分步计数原理可知,共有nCA=n(n+1)!种不同的分法.
这个解法对吗?从分析过程看,没什么问题. 下面我们来分析一下具体过程:
将n个人依次编号为1,2,3,…,n,假定第一步第k号人分得的书号为ik,对应的分法依次为(1,i1),(2,i2),…,(k-1,ik-1),(k,ik),(k+1,ik+1),…(n,in),其中,i1,i2,…,in是1,2,3,…,n的一个排列,记号(k,ik)的第1个数码表示人的编号,第2个数码表示书号.
第二步,将余下的一本书in+1分给第k人,于是,得到一种符合条件的分法:
(1,i1),(2,i2),…,(k-1,ik-1),(k,ik,in+1),(k+1,ik+1),…,(n,in).
另一方面,第一步的分法为:(1,i1),(2,i2),…,(k-1,ik-1),(k,in+1),(k+1,ik+1),…,(n,in)时,第二步,将余下的1本书ik分给第k人,于是,所得到的分法为:
(1,i1),(2,i2),…(k-1,ik-1),(k,in+1,ik),(k+1,kk+1),…,(n,in).
这种分法是n(n+1)!种分法中的一种,然而,这种分法与第一种的分法完全相同. 这表明,按照上述解法所给的分法,的每一种分法都对应着一种与它完全相同的分法,因此,这种解法对每一种符合条件的分法都重复计算了一次,故符合条件的分法应该是种.
这个问题的一般解法是:先将n+1本书分成n堆,有C种分法,然后将这n堆分给n个人,有A种分法,由分步计数原理可知,共有C·A= 种不同的分法.
一般地,关于分配的应用问题,较好的方法是先分堆,再分给人,这样计算既没有重复,也不会遗漏.
问题3:用红、黄、蓝、白、黑五种颜色涂在“田”字形的4个小方格内,每格涂一种颜色,相邻两格涂不同的颜色,如果颜色可以反复使用,共有多少种不同的涂色方法?
分析与解答:
将4个小方格依次编号为:1,2,3,4,第一个小方格可以从5种颜色中任取一种涂上,有5种不同的涂法,由于相邻两格颜色不可相同,因此,第2个,第3个小方格各有4种不同的涂法,第4个小方格的颜色与第2个,第3个小方格不可同色,因此,只有3种不同的涂法,根据分步计数原理可知,共有5×4×4×3=240种不同的涂法.
上述分析方法是错误的.错在当第2、3小格颜色相同时第4个小方格有4种不同的涂法,而不是3种.
下面给出这个问题的正确解答.
如上所述,可将4个小方格依次编号为1,2,3,4,第1个小方格可以从5种颜色中任取一种颜色涂上,有5种不同的涂法;
当第2第3个小方格涂不同颜色时,有A种不同的涂法,第4个小方格也3种不同的涂法. 由分步计数原理可知,有5A·3=180种不同的涂法;
当第2个第3个小方格涂相同颜色时,有4种涂法,由于相邻两格同色,因此,第4个小方格也有4种不同的涂法,由分步计数原理可知. 有5×4×4=80种不同的涂法.
由分类计数原理得,共有180+80=260种不同的涂法.
【说明】有关涂色问题,如果是封闭型(最后一块与第一块相连),在考虑最后一块的涂法时,一定要分情况考虑,才不会造成遗漏或重复.
问题4:将一个圆面分成n块,各部份分别记为S1,S2,…Sn. 用红、黄、蓝三种颜色涂这n个部分,要求两两不同色,共有多少种不同的涂法?
分析与解答:
首先涂S1,有3种涂法;然后涂S2,S3,…,Sn-1,各有两种涂法;最后涂Sn要求两两不同色,即Sn与S1,Sn-1不可同色,因此,Sn只有1种涂法,由分步计数原理可知,共有3·2n-2种不同的涂法.
这个解法是错误的. 错在Sn的涂法上. 当Sn-1与S1同色时,Sn的涂法有2种,不是1种.
下面,我们给出这个问题的正确解法(略). 答案为:共有2n+2·(-1)n种不同的涂法.
[1]