柱体涂色与伯努利---欧拉的装错信封的问题

最近又与涂色问题干上了，我们看下一道题：

用四种不同颜色给三棱柱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种。

接下来，尝试完成下面著名的“夫妻舞会问题”与“夫妻入座问题”

【嗨！难以想象，当初想出这两道题目的人的思想有多龌龊！】

呵呵，笑谈而已！

一次苏东坡和佛印和尚在林中打坐，日移竹影，一片寂然，很久了，佛印对苏东坡说：“观君坐姿，酷似佛祖。”苏东坡心中欢喜，看到佛印的褐色袈裟透迄在地，对佛印说：“上人坐姿，活像一堆牛粪。”佛印和尚微笑而已。