魔方吧·中文魔方俱乐部

标题: 一个排列组合问题 [打印本页]

作者: qiaoyisi 时间: 2015-5-17 10:20:59 标题: 一个排列组合问题

QQ图片20150517101903.png

附件: QQ图片20150517101903.png (2015-5-17 10:20:50, 36.35 KB) / 下载次数 172
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjUwNzk4fDExYWM1N2NjfDE3NjEzMTgxMjV8MHww

作者: 公冶暖荷 时间: 2015-5-17 10:30:12

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

作者: 至尊达哥 时间: 2015-5-17 12:50:23

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

作者: 啊对吧 时间: 2015-5-17 14:10:28

这得分多少类。。

作者: 基本粒子 时间: 2015-5-17 17:49:48

四千多万种。
字母的顺序是关键。
将图分为四块，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 时间: 2015-5-17 23:39:53

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

附件: 123.png (2015-5-17 23:39:48, 59.98 KB) / 下载次数 183
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjUwODAzfDQwMTc4NDI1fDE3NjEzMTgxMjV8MHww

作者: 基本粒子 时间: 2015-5-19 10:31:23

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

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

作者: qiaoyisi 时间: 2015-5-21 01:15:04

我们首先不管区域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 时间: 2015-5-21 09:23:50

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

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 时间: 2015-5-21 16:16:24

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

1L..

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

作者: tm__xk 时间: 2015-5-21 22:27:56

qiaoyisi 发表于 2015-5-21 16:16
这个解法非常厉害!不过太简略，估计我看也得看半天才能理解。

这么写本来就不是拿来看的..

这种问题就是暴力活而已..又不是有明显的可以归纳的结构..仅仅略带点对称性而已..计算过程也没简单什么..
(我的意思是..比方说长长的2xN用骨牌覆盖的方案数那样的fibonacci..递推的计算已经算是..呃..复杂度比穷举简单的..
而这种..就算是稍微利用下对称性..顶多也就优化个常数而已..)
总之就是我觉得真没啥好说的..所以就不多作解释了..
反正方法无非是穷举..别算错就行了..唯一有得选择的只是穷举的顺序罢了..我觉得不值得对这种问题的这种顺序选择作解释..

ps.你觉得"解法非常厉害"?为什么会这么觉得(除了故意只写式子不作解释让人不明觉厉外)?
我觉得吧..如果有意识的去稍微利用下对称性可以算得上"厉害"的话..那什么都不优化只是最笨的暴力的如果能算得下去算到最后算出正确结果的话也算得上是同样程度的"厉害"了....
ps2.9L对6L的那个计算过程..跟你在8L说的是完全一样的..吧..

作者: 双子流星 时间: 2015-5-21 23:49:47

谁然数学刚交过排列组合问题，但这也太难了，看半天没看懂。

作者: 基本粒子 时间: 2015-5-22 19:37:56

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

1L..

第1题和我的解法差不多，只是我把结果打错了，三种情况之和确实是43075640

作者: tm__xk 时间: 2015-5-22 23:34:35

基本粒子发表于 2015-5-22 19:37
第1题和我的解法差不多，只是我把结果打错了，三种情况之和确实是43075640

我猜也是..这么弄反俩数字的不出意外都是手误..

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)