柱体涂色与伯努利---欧拉的装错信封的问题
最近又与涂色问题干上了,我们看下一道题:
用四种不同颜色给三棱柱ABC-DEF六个顶点涂色,要求每个点涂一种颜色,且每条棱的两个端点涂不同颜色,则不同的涂色方法有多少种?
解法一:
对于涂色问题,我们按照颜色来分类,首先观察有哪些区域的颜色可以相同,至少需要多少颜色。
颜色可以相同的区域可以是AE,AF,BD,BF,CE,CD,显然至少需要三种颜色。
接下来分类:
第一类:需要三种颜色,由于有6个点,且着色点相同最多有两个,所以三个正整数和为6,且最大为2的情况只有2+2+2=6。
AE—BF—CD,AF—BD—CE,有2种。
有2×4×3×2=48。
第二类:需要四种颜色,由于有6个点,且着色点相同最多有两个,所以四个正整数和为6,且最大为2的情况只有2+2+1+1=6。
AE—BD—C—F,AE—BF—C—D,AE—CD—B—F,AF—BD—C—E,AF—CE—B—D,AF—CD—B—E,BD—CE—A—F,BF—CE—A—D,BF—CD—A—E,有9种。
有9×4×3×2×1=216。
共有48+216=264种。
解法二:
我们选择分步完成:
第一步:先涂上底面ABC,有4×3×2=24种。
第二步:在涂下底面DEF,有两类:
不选择第四种颜色,实际上变成了三种颜色排列,但是与以上颜色不同。
例如: 上面是1、2、3
下面只能是2、3、1
3、1、2,共两种。
选择第四种颜色,实际上变成了一种新颜色与以上三种颜色中的两个颜色,共有3种选法。接下来排列,但是与以上颜色不同。
例如:譬如选的是1、2。上面是1、2、3
下面只能是4、1、2
2、4、1
2、1、4,共三种。
有2+3×3=11种。
共有24×11=264种。
接下来我们来看解法二的第二步的第一类:
转化成下面问题:
将标有1、2、3号的小球放到编号为1、2、3的盒子中,要求每个盒子中有一个小球,且小球号码与盒子编号不同,有多少种放置方法?
利用穷举法很容易解出:
2——3——1;3——1——2,共2种。
对于四人各写一张贺年卡互相赠送的问题,我们也可以利用穷举法列出:
如果人数再加一人,即五人各写一张贺年卡互相赠送的问题,我们利用穷举法列出:
4人的错排问题只有9个,而5人的错排数有44个,可想而知,随着数的增大,错排数将愈来愈大,显然再用穷举法不再是最佳方案,为了解决这一问题,我们可以利用递推思想完成。
如果人数再加一人,即六人各写一张贺年卡互相赠送的问题,我们利用总体淘汰法分析:
当然,也可以利用递推思想来分析:
进而得到错位排列的两个递推公式:
我们还可以利用容斥原理解决这类问题:
对于最开始题目中的解法二的第二步的第一类,就相当于三个元素的错位排列,
我们有以下几种方式求出:
接下来我们来看解法二的第二步的第二类:
如果我们把4看做3的话,看以下穷举的情况,
转化成下面问题:
将标有1、2、3号的小球放到编号为1、2、3的盒子中,要求每个盒子中有一个小球,且1、2小球号码与盒子的编号不同,3号小球不受限制,则有多少种放置方法?
利用穷举法很容易解出:
3——1——2;2——3——1;2——1——3,共3种。
接下来,尝试完成下面著名的“夫妻舞会问题”与“夫妻入座问题”
【嗨!难以想象,当初想出这两道题目的人的思想有多龌龊!】
呵呵,笑谈而已!
一次苏东坡和佛印和尚在林中打坐,日移竹影,一片寂然,很久了,佛印对苏东坡说:“观君坐姿,酷似佛祖。”苏东坡心中欢喜,看到佛印的褐色袈裟透迄在地,对佛印说:“上人坐姿,活像一堆牛粪。”佛印和尚微笑而已。