[原创]有关圆形排列的分类及理解推导

2BLidr

这是我在做费费数学的时候对圆圈排列（环形排列）的一些个人理解，可能有点不同于linlin的解释，也有可能有其他xdjm曾经发表过类似的总结我没看到，如果有雷同和错误，请指正。

本人觉得应该对标成橙色字体的题目进行仔细分类，明确原理，挖掘根本区别和思考方法。环形排列不是只有一种方法或公式就能通解所有题的。

下面分楼层给出我的总结

这是我在做费费数学的时候对圆圈排列（环形排列）的一些个人理解，可能有点不同于linlin的解释，也有可能有其他xdjm曾经发表过类似的总结我没看到，如果有雷同和错误，请指正。

本人觉得应该对标成橙色字体的题目进行仔细分类，明确原理，挖掘根本区别和思考方法。环形排列不是只有一种方法或公式就能通解所有题的。

下面分楼层给出我的总结

2BLidr

1.       基本型：从n个元素中挑选出k个的组合方式有C(k,n)种，排列方式有P(k,n)种；

如从5个橘子中任意挑3个出来，有C(3,5)=10个组合，排列方式就有P(3,5)=60个

2.       填空型：把k个元素放入n个空位中（ABC+12345è1A3BC,…）

a)         n个空位无排列（相对次序无要求）：

组合方式有C(k,n)，如把水果随便装到5个空果篮中的3个，就有C(3,5)种挑选组合。

b)        n个空位有排列（相对次序有要求）：

                        i.              直线排列

1.         排列次序有P(k,n)种；

例子：用3个不同字母（A，B，C）来代替字符串11111中的任意3个字符，组成P(3,5)个新字符串。

2.         一些涉及固定位置的环形排列其实是直线排列

如（下面的例子三，来自费费数学）如果是5个人分别坐到桌子旁5张不同凳子上时，坐法就有P(5,5)种（直线排列）。同样的例子还有例四。

                      ii.              环形排列

排列有P(k-1,n-1)种。推导过程如下：

1.       先不考虑圆的旋转对称性^注（即只考虑直线排列），有P(k,n)个排列；

2.       考虑圆的旋转对称性的影响，有多少个空位就有多少个“对称位置”-也就是说任何一个排列次序都有n-1个与他“对称”的排列，所以最终总的排列次序数为P(k,n)/n=P(k-1,n-1)。

例子：圆桌旁有5个凳子，3个人坐到任意的3个凳子上，那就有P(3,5)种坐法（直线排列），而排列数（三人的相对次序）只有P(2,4)种。

例子：（下面的例子二，来自费费数学）5个人坐到桌子边上，就有P(4,4)种排列方式；（下面的例子三，来自费费数学）但是如果是5个人分别坐到桌子旁5张不同凳子上时，坐法就有P(5,5)种（直线排列）。

个人看法：并不是环形排列比线性排列少一个，而是本身的“对称性”使有些排列相互“对称”一致

注：这里之所以可以引入圆的旋转对称性是因为这里讨论的所有题目我们都不要求放在圆上的物体之间有固定的间距，但是要保持个体之间的相对前后关系（圆弧上的排列），也就是所在圆弧上排好的某个排列，如果把整个排列全部平移一个位置，如果还是按平移前的起始位置来看，他就是一个新的排列，但是其实它和原排列是一模一样的，如此类推，它有n个copy（算上自己），这跟圆上平均分布的n个点的对称关系是一致的，即n次对称。

 

 

3.       插入型：把k个元素插入n个元素的已有排列中（ABC+12345èA1B23C45,…）

a)         n个元素排列为直线型：

每插入1个元素到排列中，可允许插入元素的位置都会多1个，如12345有n+1=6个位置可以插入A，B或C，如果把A随意放入一个位置变成12A345，那就有n+1+1=7个位置可以插入B，所以如此类推：

排列方式数量为P(1,n+1)*P(1,n+2)*P(1,n+3)…*P(1,n+k)=P(k,n+k)

例子：如把3个不同的字母（A，B，C）放到字符串12345中的任意位置，组成P(3,8)个不同的字符串

b)        n元素排列为环形（不计较具体位置，只计较相对排列）：

这里就无所谓“对称”了，与所谓直线型不同在于具有相同数量(n)的元素的排列，直线型有n+1个位置可以插入新元素，而环形的只有n个。因为在环形排列中首位相接，有两个位置重叠了。所以公式就变成：

排列方式数量为P(1,n)*P(1,n+1)*P(1,n+2)…*P(1,n+k-1)=P(k,n+k-1)

例子（下面的例一，来自费费数学）：把2根钥匙串进已经有5根钥匙的钥匙圈里，就有P(2,6)种排列；如果问那2根钥匙是相邻的排列数是多少，应该是这2根钥匙的排列数×往有5根钥匙的钥匙圈里放入1根钥匙（把2根看作一个整体）的排列数，即P(2,2)*P(1,5+1-1)，他的概率为P(2,2)*P(1,5+1-1)/P(2,6)=2*5/(6*5) = 2/6

[此贴子已经被作者于2008-8-15 18:32:19编辑过]

2BLidr

以下是从《费费数学宝典》原文直接引用：

例一、在已有5个钥匙的钥匙环中放入2个钥匙,这2个钥匙相邻的概率？
                

我的思路：第一种解法：题目可以转化为先将其中一把钥匙A放入钥匙链种，这样key chain 中就有6把钥匙了！然后再放另一把钥匙B，求钥匙B和钥匙A相邻的概率。六把钥匙六个位置，所以分母是6（因为是圆）分子要求B和A相邻的话只有两个位置。所以是2/6

第二种解法：利用这个规律

本题直线排列是：2C(1,6)/P(2，7）

所以换成环形的话就应该是：2C(1,5)/p(2,6)=2/6

所以本题的答案是2/6

例二、五个人站成一个圈的那道题：利用规律很容易得p(4,4)

例三、5个点（其中有一红点）排成一个圆圈，5个人A、B、C、D、E，其中A必须站在红点上，问有多少种不同的站法

因为A点的位置是固定的，所以我们先排其他4个点。按环形排要少一个元素，所以这四个点排成一个圆形的话就是P(3,3)

他们排好后有4个位置可以放A，所以是4

因而我认为答案应该是P(4,4)

例四、6个盘子，一蓝5白，摆成一圈。五种坚果，其中有N和R，别的不知。如果N或R之一必须放在蓝盘子中，其他盘子各放一个坚果，共有几种摆法。
                

[确认] 240

[思路] 2*P(5, 4)=240

首先6个盘子5白一蓝排成一个圈的排法只有一种，所以只需考虑坚果的方法！

放入蓝盘子的坚果有N或R所以有两种。

其他五个盘子放4中坚果，与要考虑排列所以是P(5,4)

所以最后答案是240

Sunsnowing87

顶啊！！！ 今天也在看这类环形排列题 对费费的解释有点疑问 LZ帮了大忙了

sionocean

很详细啊，谢谢~

ada3063

谢谢

晚点再来详细看

2BLidr

忘了顶自己一个

mac_bobo

请教楼主：

    环形排列
   

排列有P(k,n-1)种，k<n。推导过程如下：
   

1.       先不考虑圆的旋转对称性^注（即只考虑直线排列），有P(k,n)个排列；
   

2.       考虑圆的旋转对称性的影响，有多少个空位就有多少个“对称位置”-也就是说任何一个排列次序都有n-1个与他“对称”的排列，所以最终总的排列次序数为P(k,n)/n=P(k,n-1)。
   

如果说任何一个排列次序都有n-1个与他“对称”的排列，为什么是除以n,而不是除以n-1?

P(k,n)=n!/(n-k)!

P(k,n-1)=(n-1)!/(n-1-k)！

P(k,n)/n=(n-1)!/(n-k)! 岂不是不等于P(k,n-1)？

是不是我有什么基本的知识没掌握啊？

麻烦解释一下!谢谢！

如果说任何一个排列次序都有n-1个与他“对称”的排列，为什么是除以n,而不是除以n-1?

P(k,n)=n!/(n-k)!

P(k,n-1)=(n-1)!/(n-1-k)！

P(k,n)/n=(n-1)!/(n-k)! 岂不是不等于P(k,n-1)？

是不是我有什么基本的知识没掌握啊？

麻烦解释一下!谢谢！

[此贴子已经被作者于2008-8-10 1:45:01编辑过]

梵尘

谢谢！

mac_bobo

没有人帮忙解惑？