一个排列组合问题

qiaoyisi

公冶暖荷

哈哈，我们正学着数学选修2-3呢，也做过这种类型的题，可你这也忒难了吧。

至尊达哥

初中的跪了。。。。。。。。

啊对吧

这得分多少类。。

基本粒子

四千多万种。
字母的顺序是关键。
将图分为四块，ABCD,EFK,GHL,IJM。其中EFK,GHL,IJM之间互不影响。
ABCD共有A(4,5)+A(3,5)x3+A(2,5)=120+60x3+20种情况。式中A(4,5)表示从5种颜色中选4种进行有序排列，等于5！/(5-4)！。(手机党表示打不出来更好的效果，也没想起来实际应该怎么打)。
ABCD中A与BCD都相邻，BCD互不相邻。分三种情况:1.ABCD共有四种颜色，从五种颜色中选四种进行有序排列；2.ABCD共有三种颜色，从五种颜色中选三种进行有序排列，其中同色两块有BC,BD,CD三种情况；3.ABCD共有两种颜色，只能是BCD同色。(式子不打了)
情况1:EF共有16种情况涂颜色，同色3种，异色13种，EF同色时K有4种颜色可涂，EF不同色时K有3种颜色可涂。所以EFK大块共有3x4+13x3=51种涂法。同理GHL和IJM分别有51种涂法。一共有51x51x51x120=15918120种涂法。
情况3:EF共有16种情况涂颜色，同色4种，异色12种，EF同色时K有4种颜色可涂，EF不同色时K有3种颜色可涂。所以EFK大块共有4x4+12x3=52种涂法。同理GHL和IJM分别有52种涂法。一共有52x52x52x20=2812160种涂法。
情况2:假设BC同色，BD,CD时同理，直接乘3即可。EFK同情况3，GHL和IJM同情况1。一共有52x51x51x60x3=24345360种涂法。
三种情况加一起有43075460种涂法。

qiaoyisi

分析的对的，方法差不多。请看此问题的强化：

基本粒子

qiaoyisi 发表于 2015-5-17 23:39
分析的对的，方法差不多。请看此问题的强化：

说说你的方法吧，有点难算。

qiaoyisi

我们首先不管区域N、O、P，并按区域K、L、M的不同情况进行分类：
1.K、L、M同色：
1.1  区域A与区域K、L、M同色，则区域B有4种颜色可取，区域E、G在此基础上，均有3种颜色可取。区域C、F、J和区域D、H、I染色同区域B、E、G，故此类有5×（4×3×3）^3种；
1.2  区域A与区域K、L、MA不同色，则区域A有4种颜色可取，区域B显然与区域A不同色，若区域B与区域K、L同色，则区域B、E、G共有4×4种；若区域B与区域K、L不同色，则区域B、E、G共有3×3×3种。区域C、F、J和区域D、H、I染色同区域B、E、G，故此类有5×4×（4×4+3×3×3）^3种；
故1类共有5×（4×3×3）^3+5×4×（4×4+3×3×3）^3=1823420（种）。
2.K、L、M其中两个同色（与哪两个同色有关，故此类最后应×3，先考虑K、L同色情况）：
2.1  区域A与区域K、L同色，则区域B有4种颜色可取，区域E、G在此基础上，均有3种颜色可取。区域C显然与区域A不同色，若区域C与区域M同色，则区域F有4种颜色可取，区域J有4种颜色可取；若区域C与区域M不同色，则区域F有3种颜色可取，区域J有3种颜色可取。区域D、H、I染色同区域C、F、J，故此类有5×4×（4×3×3）×（4×3+3×3×3）^2种；
2.2  区域A与区域K、L不同色，与区域M同色，若区域B与区域K、L同色，则区域E、G在此基础上，均有4种颜色可取；若区域B与区域K、L不同色，则区域B有3种颜色可取，区域E、G在此基础上，均有3种颜色可取。区域C显然与区域A不同色，若区域C与区域K同色，则区域F有4种颜色可取，区域J有3种颜色可取；若区域C与区域K不同色，则区域C有3种颜色可取，则区域F有3种颜色可取，区域J有3种颜色可取。区域D、H、I染色同区域C、F、J，故此类有5×4×（4×4+3×3×3）×（4×3+3×3×3）^2种；
2.3  区域A与区域K、L不同色，与区域M也不同色，则区域A有3种颜色可取，若区域B与区域K、L同色，则区域E、G在此基础上，均有4种颜色可取；若区域B与区域K、L不同色，则区域B有3种颜色可取，则区域E、G在此基础上，均有3种颜色可取；区域C显然与区域A不同色，若区域C与区域K同色，则区域F有4种颜色可取，区域J有3种颜色可取；若区域C与区域M同色，则区域J有4种颜色可取，区域F有3种颜色可取；若区域C与区域K、M不同色，则区域C有2种颜色可取，则区域F、J在此基础上，均有3种颜色可取。区域D、H、I染色同区域C、F、J，故此类有5×4×3×（4×4+3×3×3）×（4×3+4×3+2×3×3）^2种；
故2类共有[5×4×（4×3×3）×（4×3+3×3×3）^2+5×4×（4×4+3×3×3）×（4×3+3×3×3）^2+5×4×3×（4×4+3×3×3）×（4×3+4×3+2×3×3）^2]×3=20862900（种）。
3.K、L、M颜色互不相同：
3.1  区域A与区域K、L、M中的其中一个颜色相同，故最后应×3。不妨设区域A与区域K颜色相同，若区域B与区域L同色，则区域G有4种颜色可取，则区域E有3种颜色可取；若区域B与区域L不同色，则区域B有3种颜色可取，则区域G、E在此基础上，均有3种颜色可取；若区域C与区域M颜色相同，则区域J有4种颜色可取，则区域F有3种颜色可取；若区域C与区域M不同色，则区域C有3种颜色可取，则区域F、J在此基础上，均有3种颜色可取；区域D显然与区域A不同色，若区域D与区域L同色，则区域H有4种颜色可取，则区域I有3种颜色可取；若区域D与区域M同色，则区域I有4种颜色可取，则区域H有3种颜色可取；若区域D与区域L、M均不同色，则区域D有2种颜色可取，则区域H有3种颜色可取，则区域I有3种颜色可取。故此类有5×4×3×（4×3+3×3×3）^2×（4×3×2+2×3×3）×3种；
3.2   区域A与区域K、L、M颜色均不相同，则区域A有2种颜色可取。此时区域A、K、L，区域A、K、M，区域A、L、M颜色均各不相同，故只需考虑一组。区域B显然与区域A不同色，若区域B与区域K同色，则区域E有4种颜色可取，则区域G有3种颜色可取；若区域B与区域L同色，则区域G有4种颜色可取，则区域E有3种颜色可取；若区域B与区域K、L均不同色，则区域B有2种颜色可取，则区域E有3种颜色可取，则区域G有3种颜色可取。故此类有5×4×3×2×（4×3×2+2×3×3）^3种；
故3类共有5×4×3×（4×3+3×3×3）^2×（4×3×2+2×3×3）×3+5×4×3×2×（4×3×2+2×3×3）^3=20389320种。
接下来考虑区域N、O、P，1类条件下，区域N、O、P均有4种颜色可取；2类条件下，区域K、L、M同色一侧有4种颜色可取，异色一侧各有3种颜色可取；3类条件下，区域N、O、P各有3种颜色可取。故最终得到，共有4^3×1823420+4×3×3×20862900+3×3×3×20389320=1418274920种不同的染色方案。

tm__xk

反正都是简单的暴力活儿就能搞定的..

1L..
5*(4*(4*4+4*3*3)^3+3*4*3*(4*4+4*3*3)*(3*4+4*3+3*3*3)^2+4*3*2*(3*4+4*3+3*3*3)^3)=43075640
刚好和5L反了两位呢..

6L..
A=4*3^2
B=4^2+3*3^2
C=4*3+3*3^2
D=2*4*3+2*3^2
5*4^3*(A^3+4*B^3)+3*5*4*(4*3^2)*(A*C^2+B*C^2+3*B*D^2)+5*4*3*3^3*(3*C^2*D+2*D^3)=1418274920

解释什么的就算了..个人认为这种东西没什么解释的必要..

qiaoyisi

tm__xk 发表于 2015-5-21 09:23
反正都是简单的暴力活儿就能搞定的..

1L..

这个解法非常厉害!不过太简略，估计我看也得看半天才能理解。