排列组合问题
出题人补充有点不清楚,为什么是“有的”排列顺时针和逆时针其实对应的是相同的排列? 我猜是所有排列反过来写都认为没有区别,即只有相邻关系是重要的。先前的解答基本思路不需要改变,只是对称群增大了,答案变成了171,具体如下:
对于两个1间距是1,2,3的情况,两个1定义了一个对称轴(它们连线的中垂线),一般的填法镜像反射过去会改变,依题意应算为一种,所以算重了。 镜像对称的填法有3! 种,所以不等价的有 3! + (6!/ 2^3 - 3!)/2 = 48种。
对于两个1间距是4的情况,由于它们占据了对径点,除了中心对称,还有两个镜像反射对称(分别以两个1的连线及其中垂线为对称线),一般的情...全部
出题人补充有点不清楚,为什么是“有的”排列顺时针和逆时针其实对应的是相同的排列? 我猜是所有排列反过来写都认为没有区别,即只有相邻关系是重要的。先前的解答基本思路不需要改变,只是对称群增大了,答案变成了171,具体如下:
对于两个1间距是1,2,3的情况,两个1定义了一个对称轴(它们连线的中垂线),一般的填法镜像反射过去会改变,依题意应算为一种,所以算重了。
镜像对称的填法有3! 种,所以不等价的有 3! + (6!/ 2^3 - 3!)/2 = 48种。
对于两个1间距是4的情况,由于它们占据了对径点,除了中心对称,还有两个镜像反射对称(分别以两个1的连线及其中垂线为对称线),一般的情况4个填法等同1个,但分别有3!种情况具有中心对称和两个镜像对称,而且它们各不相同,所以不等价的填法有
(3! + 3! + 3!) / 2 + (6!/ 2^3 - 3! - 3! - 3!) / 4 = 27
(说明:前面除以2是因为每个具有一个对称性的排列只与另一个等价,比如12341234与14321432,123214341与14341232),
总之,不等价的填法共有 3 * 48 + 27 = 171 种。
=================================
先选两个位置给1,剩下的就好填了。
由于旋转对称性,两个1的距离(间隔)才是有意义的。
两个1的距离有1,2,3,4四种可能,
对于前三种可能中的任一种,剩下的6个数有6!/ 2^3 = 90种不同的填法。
但对于间隔为4,即两个1在对径点,的情况,稍微有一点不同,比如12341432和14321234其实是一样的。这样的重复排列共有3!= 6对,所以共有 90 - 6 = 84种不同的填法。
总共有 3 * 90 + 84 = 354 种不等价的填法。
------------------------
以上是最开始的解答,与楼下用群论的结果不一样,赶紧查错,原来间隔是4的情况想错了。如果abc与efg不相等,则1abc1efg 和 1efg1abc是一样的。
像这样的共有(90 - 6!)/2 = 42对,所以总共有
3 * 90 + (90 - 42) = 318
还是群论强大。收起