令人目眩的排列组合（包含部分涂色问题）

走走看看

求满足条件的方法数（每个盒子不空）：
1、5个相同的球，放入4个相同的盒子；
2、5个不同的球，放入4个相同的盒子；
3、5个相同的球，放入4个不同的盒子；  C(4,3)
4、5个不同的球，放入4个不同的盒子。  C(5,2)*A(4,4)

现有9名同学参加实验：
(1)平均分三组，参加不同实验，有多少种分法？  C(9,3)*C(6,3)
(2)平均分三组，参加相同实验，有多少种分法？

请大师们给出上面未有答案的题的答案，最好同时给出解释。

走走看看

1 是否就1种方法？
2 是否是C(5,2)种方法？
本人没有把握。

走走看看

6个不同的球放入4个相同的盒子，要求盒子非空，有多少种方法？
ask.kuakao.com/question/onquestion.action?questionId=14663

你好，欢迎来到跨考教育咨询。本题有C62乘以C42乘以C21种排法。感谢你的提问，欢迎再次关注跨考教育，祝复习顺利。|

我觉得这个回答也不靠谱。

只考虑给球分4个组，分组后装入4个相同盒子，没有区别，有多少种分组就有多少种情况。
6个球虽然不同，但由于装入的盒子都相同，所以是组合而非排列。
如果这个想法是正确的。6可以分为1、1、1、3和2、2、1、1这两种大组，然后考虑分成小组的情况。
共有C(6,3)+C(6,2)*C(4,2)/A(2,2)组，也就是共有C(6,3)+C(6,2)*C(4,2)/A(2,2)方法。
我有点头昏。

走走看看

下面的这个链接验证了我的想法。

cache.baiducontent.com/c?m=9d78d513d9c756ae28 … 8e0002335a&p1=20

走走看看

还发现圆形图形涂色问题，因为是对称的，找不到切口。

如图所示，一个图形分为5个区域，现给图形着色，要求相邻区域不得使用同一颜色．现有4种颜色可供选择，则不同的着色方法共有________种．


答案是240，但没有过程。查遍网络也没有看到解答。

走走看看

在做了下面这道题后，还是做不出上面这道题。

zhidao.baidu.com/question/177021162001434684. … true&newAnswer=1
如图，用4种不同的颜色对图中5个区域涂色（ 4种颜色全部使用 ），要求每个区域涂一种颜色，相邻的区域不能涂相同的颜色，则不同的涂色方法有______ 种．

解析：
4色：四色只能是1、2、3、4，或者1、2、4、5，或者1、3、4、5，或者2、3、4、5四种情况，1、2、3、5不符要求。
再看1、2、3、4，则5同1或2或3，有3种，
或者1、2、4、5，则3同1,1种，
或者1、3、4、5，则2同5，与第一种情况重复
或者2、3、4、5，则1同3，与第二种情况重复，
共4种，4*A(4,4)=96种。

刚刚才看清楚，题目要求四种颜色全用，所以，三种颜色的弃用。

更多的是这样的题目：
如图，矩形广告牌分为5个不同的区域，现给广告牌着色，要求相邻区域不得使用同一颜色．现有4种颜色可供选择，则不同着色方法共有    种．
1010jiajiao.com/gzsx/shiti_id_c182b3930312c130f88c69620b5ab89f
前后两题的区别就在于  前者有个限定，后者则没有。
奇怪的是，这两道题给出的答案都是96。

kuing

还发现圆形图形涂色问题，因为是对称的，找不到切口。

如图所示，一个图形分为5个区域，现给图形着色，要 ...
走走看看 发表于 2017-9-25 09:39

这种用递推就可以了，你百度“染色问题 递推”就能找到相关资料

走走看看

这样的问题我有点糊涂。
谢谢！

走走看看

回复 5# 走走看看

先涂1，有4种涂法，再涂2，有3种方法，涂3时分两类，
一类是3与1同，则4有3种涂法，5有2种涂法；
另一类是3与1不同，则3有2种涂法，4要分类，4与1同，5有3种，4与1不同，4有2种涂法，5有2种涂法，
根据乘法原理和加法原理，共有4*3*（1*3*2+2*（1*3+2*2））=240种。

根据通项公式有 $3*(-1)^5+3^5=240$。

走走看看

回复 6# 走走看看

不限定时，96算错了，应该是144。

“区域5涂第四种颜色”这句话不对，可以涂三种颜色，包括与1、2相同的颜色和第四种颜色。这就是它的错误根源。
所以总共应为4*3*2*（1*3+1*3）=144种。

让人困惑的是，所有的答案都是96。
如果考试中遇到这道题，考生给出正确答案，还会被老师判错。该怎么办？

tommywong

相邻异色问题可用色多项式Chromatic polynomial解决

5#题目

$P(C_n,t)=(t-1)^n+(-1)^n (t-1)$

$P(C_5,4)=3^5+(-1)^5 3=240$

6#题目

$P(G,t)=tP(G-v_4,t-1)=tP(G-v_4-v_5,t-1)P(v_5,t-1)$

$P(v_5,t-1)=t-1,P(G-v_4-v_5,t-1)=P(T_3,t-1)=(t-1)(t-2)^2$

$P(G,t)=t(t-1)^2 (t-2)^2$

$P(G,4)=144$

走走看看

看不懂大师的公式，但很佩服大师的知识技能！