Question

用四种不同颜色给图中ABCDEF六个点涂色

用四种不同颜色给图中ABCDEF六个点涂色，每点涂一色，每条线段两端点颜色不同，共几种涂法？

求详细解答
回答者： cutmiss - 四级 2010-7-26 01:08
谢谢你，我把你的回答先打印下来看看。正确答案是168

Answer 1

先只考虑上面三个点都不同色，下面三个点也都不同色，那么有

P(4, 3)*P(4, 3)种方法。

下面要把"其中的"竖着的线段中有上下同色的去掉。

1. A,B同色(C,D同色，E,F同色，结果都一样)

C(4, 1)P(3, 2)P(3, 2)

2. A,B同色，且C,D同色 (其他的有两对同色的情况也一样)

A,B的色 与 C,D的色 必然不同，P(4, 2)P(2, 1)P(2, 1)；

3. A,B同色，且C,D同色, 且E,F同色,
因为他们的颜色都不同，P(4, 3)。

由容斥原理，"其中的"至少有竖着的一条线段上下同色的方法数为

3 C(4, 1)P(3, 2)P(3, 2) - 3 P(4, 2)P(2, 1)P(2, 1) + P(4, 3)
= 3*4*6*6 - 3*12*2*2 + 24 = 24*13.

(原回帖的这一行计算有错,更正如下)

所求的方法数为 P(4, 3)*P(4, 3) - 24*13 = 24*11 = 264。
(原回帖是：所求的方法数为 P(4, 3)*P(4, 3) - 24*13 = 24*9 = 216。错误)

-------------------------------------

换一种办法：不用容斥原理

上面一层三个点都不同色有P(4, 3) = 24种方法。
对上述的每一种给定的方法，
我们来数出下面一层要保证与上一层对应的不同色

设上一层A, D, E的颜色为分别为a, b, c

1. 下层可以是颜色a,b,c错排，有2种方法。

2. 下层包括第四种颜色d，但不包括abc中某颜色(例如a)
对于d对着a的情形，只有1种方法
对于d不对着a的情形(d对着b，或c)，有2种方法

那么1,2这两种情形共有2 + 3*3 = 11种方法.

所求方法数为 P(4, 3)* 11 = 264种方法.

---------------------------------

感谢鱼之冰的补充，使我重新检查找出计算错误．

不过，这两种方法的计算结果是一致的．却与鱼之冰所给出答案不同．

容我再思考．

Answer 2

解：
可以根据所涂得颜色的种类来分类，
B，D，E，F用四种颜色，则有A44×1×1=24种涂色方法；
B，D，E，F用三种颜色，则有A43×2×2+A43×2×1×2=192种涂色方法；
B，D，E，F用两种颜色，则有A42×2×2=48种涂色方法；
根据分类计数原理知共有24+192+48=264种不同的涂色方法

Answer 3

首先把可以相同的点全找出来：AF\BD\CE\DF\BE\AC 都可以相同
①涂三种颜色：AF/BD\CE 结合三种、还可以是：DF\BE\AC结合。
共有：（4*3*2）*2=48
②涂四种颜色：AF\BD AF\BE AF\CE DF\BE DF\CE DF\AC BD\CE BD\AC BE\AC
共有：（4*3*2*1）*9﹦216
总计：48+216﹦264